[CodeChef] Starters 78 — Solve More: the last problem doesn't pay for its break

Published 1 October 2026

Problem: CodeChef — Solve More (Starters 78, difficulty 1993).

Chef has \(N\) problems. Problem \(i\) takes \(A_i\) minutes to solve, followed by a \(B_i\)-minute break. With \(K\) minutes, choosing problems and order freely, what’s the most he can solve? A problem counts if it’s finished by minute \(K\), even if its break runs past \(K\).

Constraints: \(N \le 2 \cdot 10^5\) (summed over tests), \(K, A_i, B_i \le 10^8\).

The greedy itself came quickly. What cost me was the usual greedy story: two edge cases at the boundary, one after the other, for a 42/100 along the way.

The observation

In any chosen set, every problem except the last one costs \(A_i + B_i\). The last one costs only \(A_i\) — its break can spill past \(K\) for free.

So fix the last problem \(i\). Its budget for everything before it is \(K - A_i\), and to fit as many problems as possible into that budget you take the ones with the smallest \(A_j + B_j\) (other than \(i\)). Try every \(i\) as the last problem and take the best.

Making it fast

• Sort all problems by \(A + B\) once and build prefix sums over that order.
• Remember each problem’s position \(p\) in the sorted order.
• For a candidate last problem \(i\), binary-search the largest \(x\) such that the \(x\) cheapest other problems fit in \(K - A_i\).

The only fiddly part is excluding \(i\) itself from the prefix. With zero-based positions, the first \(x\) sorted entries are positions \(0 \ldots x-1\):

• if \(x \le p\), they don’t include \(i\), so the cost is \(\text{prefix}[x]\);
• if \(x > p\), they do, so take one more and subtract \(i\): \(\text{prefix}[x+1] - (A_i + B_i)\).

I second-guessed whether that should be x < p. It shouldn’t — position \(p\) is in the first \(x\) entries exactly when \(p \le x - 1\), i.e. \(x > p\).

\(O(N \log N)\) overall.

What I missed

1. The last problem has to fit on its own. My first version started the binary search at lo = 0, treating “zero other problems” as always feasible, and then added \(1\) for the last problem. But if \(A_i > K\), problem \(i\) can’t be solved at all, even alone. Sample 3 catches this: every \(A_i\) exceeds \(K = 20\), so the answer is \(0\), not \(1\). Fix: skip \(i\) when \(K - A_i < 0\).

2. Then I got the boundary wrong in the fix. I wrote

if budget <= 0:
    continue

which also skips \(A_i = K\) — a problem that finishes exactly at minute \(K\), which the statement explicitly allows. That’s the 42/100: subtasks 0–2 correct, wrong answer on subtask 3. The condition has to be budget < 0; with budget \(0\), \(x = 0\) is valid and the candidate still contributes \(1\).

The lesson. The greedy idea was fine; the boundaries weren’t. With “pick a special element, fill the rest greedily”, check that the special element is feasible by itself, and when the statement says “by minute \(K\)”, the equality case is allowed — < vs <= is the whole bug.

Code

Checked against a brute force over all orderings on small random cases.

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    problems = sorted(
        (a[i] + b[i], a[i], i)
        for i in range(n)
    )

    prefix = [0] * (n + 1)
    sorted_position = [0] * n

    for p, (total, solve_time, original_index) in enumerate(problems):
        prefix[p + 1] = prefix[p] + total
        sorted_position[original_index] = p

    best = 0

    for i in range(n):
        p = sorted_position[i]
        budget = k - a[i]

        if budget < 0:
            continue

        # Maximum number of other problems that fit before problem i.
        lo, hi = 0, n - 1

        while lo < hi:
            x = (lo + hi + 1) // 2

            # Sum the x cheapest A+B values, excluding problem i.
            if x <= p:
                cost = prefix[x]
            else:
                cost = prefix[x + 1] - problems[p][0]

            if cost <= budget:
                lo = x
            else:
                hi = x - 1

        best = max(best, lo + 1)

    print(best)


tc = int(input())
for _ in range(tc):
    solve()