The Buses

Solution Approach

Backtracking with Pruning

The small time range (0--59) makes backtracking feasible:

1. Maintain a frequency array $\mathtt{cnt}[0..59]$ of unassigned arrival times.

2. Find the smallest unassigned time $t_{\min}$. This time must be the start of some route, so we try all routes beginning at $t_{\min}$.

3. For each interval $d \in [1, 59]$, check the maximum number of evenly spaced arrivals $t_{\min}, t_{\min}+d, t_{\min}+2d, \ldots$ that are all available. For each valid count $c \ge 2$ (tried largest first to cover more arrivals per route), subtract the route from $\mathtt{cnt}$ and recurse.

4. Prune: if the current number of routes already equals the best found, stop.

Correctness

The key invariant is that the smallest unassigned time must start some route. By trying all possible intervals and counts for that starting time, we enumerate all valid decompositions. The pruning condition ensures we find a minimum-route solution.

C++ Solution

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int n;
int cnt[60]; // available count for each arrival time
int bestRoutes;

struct Route {
    int start, interval, count;
};
vector<Route> bestSolution, currentSolution;

bool canUse(int s, int d, int c) {
    for (int i = 0; i < c; i++) {
        int t = s + i * d;
        if (t > 59 || cnt[t] <= 0) return false;
    }
    return true;
}

void applyRoute(int s, int d, int c, int delta) {
    for (int i = 0; i < c; i++)
        cnt[s + i * d] += delta;
}

int remaining() {
    int r = 0;
    for (int i = 0; i < 60; i++) r += cnt[i];
    return r;
}

void solve() {
    if (remaining() == 0) {
        if ((int)currentSolution.size() < bestRoutes) {
            bestRoutes = (int)currentSolution.size();
            bestSolution = currentSolution;
        }
        return;
    }

    // Prune: cannot improve on current best
    if ((int)currentSolution.size() + 1 >= bestRoutes) return;

    // Find first unassigned time (must be the start of some route)
    int first = -1;
    for (int i = 0; i < 60; i++)
        if (cnt[i] > 0) { first = i; break; }

    // Try all routes starting at 'first'
    for (int d = 1; d <= 59; d++) {
        // Count maximum consecutive multiples present
        int maxc = 0;
        for (int t = first; t <= 59; t += d) {
            if (cnt[t] > 0) maxc++;
            else break;
        }
        if (maxc < 2) continue;

        // Try from largest count downward (greedy: cover more with fewer routes)
        for (int c = maxc; c >= 2; c--) {
            if (canUse(first, d, c)) {
                applyRoute(first, d, c, -1);
                currentSolution.push_back({first, d, c});
                solve();
                currentSolution.pop_back();
                applyRoute(first, d, c, +1);
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        cnt[t]++;
    }

    bestRoutes = n; // upper bound
    solve();

    printf("%d\n", bestRoutes);
    for (auto& r : bestSolution)
        printf("Start: %d, Interval: %d, Count: %d\n",
               r.start, r.interval, r.count);

    return 0;
}

Complexity Analysis

• Time complexity: Exponential in the worst case, but heavily pruned. At each recursion level, we fix the smallest unassigned time and try $O(59)$ intervals, each with $O(59)$ possible counts. The pruning bound on the number of routes limits the recursion depth. In practice, for $n \le 300$ and times $\le 59$, the search terminates quickly.

• Space complexity: $O(n)$ for the route stack and the frequency array.