2024 December Bronze · "Walking the Cows"

← All past problems · Official statement

The premise

Farmer John has N cows, each scheduled to be walked at a specific time. Cows can be walked in groups, but a group can only contain cows whose appointment times are within K minutes of each other. Each group takes a fixed amount of time. Compute the minimum number of groups needed to walk every cow on time.

(Wording paraphrased — see official PDF for the exact statement, constraints, and sample inputs.)

Constraints

1 ≤ N ≤ 10⁵
0 ≤ K ≤ 10⁹
Times fit in a 32-bit signed integer
Time limit: 2 seconds, memory: 256 MB

Key idea

Sort, then greedy-sweep. Once times are sorted, the optimal grouping always extends a group as far as it can go before starting a new one. Each cow either fits in the current group's [start, start+K] window or starts a new group.

Why greedy works: any cow you delay would only fit into a later group, never an earlier one, so extending the current group is always safe.

Pseudocode

read N, K, t[1..N]
sort(t)
groups = 0
start = -INF
for i in 1..N:
    if t[i] > start + K:
        groups += 1
        start  = t[i]
print(groups)

Complexity

Sorting dominates at O(N log N). The sweep is O(N). Trivially fast at N = 10⁵.

Pitfalls

Off-by-one on the window. Is the window t[i] - start ≤ K or strictly less? Re-read the statement.
Initial group. Don't set groups = 1 and then skip cow 0 — easier to start at 0 and let the first cow trigger the first group.
Overflow. start + K can overflow 32-bit if both are near 10⁹. Use long long or compare as t[i] - start > K.

What to take away

"Sort then sweep" is the single most common Bronze pattern.
The hardest part of Bronze is convincing yourself the greedy is correct — write the 2-line proof on paper.
Always double-check inclusive vs. exclusive window endpoints before submitting.