HARDAtCoderLiveCodeBench

LCB-08: Cans and Openers

Baseline: PASS
Augmented: PASS
Injection: 2,185 chars

The Task

There are N items. Each of these is one of a pull-tab can, a regular can, or a can opener. The i-th item is described by an integer pair (T_i, X_i) as follows: - If T_i = 0, the i-th item is a pull-tab can; if you obtain it, you get a happiness of X_i. - If T_i = 1, the i-th item is a regular can; if you obtain it and use a can opener against it, you get a happiness of X_i. - If T_i = 2, the i-th item is a can opener; it can be used against at most X_i cans. Find the maximum total happiness that you get by obtaining M items out of N. Input The input is given from Standard Input in the following format: N M T_1 X_1 T_2 X_2 \vdots T_N X_N Output Print the answer as an integer. Constraints - 1 \leq M \leq N \leq 2 \times 10^5 - T_i is 0, 1, or 2. - 1 \leq X_i \leq 10^9 - All input values are integers. Sample Input 1 8 4 0 6 0 6 1 3 1 5 1 15 2 1 2 10 2 100 Sample Output 1 27 If you obtain the 1-st, 2-nd, 5-th, and 7-th items, and use the 7-th item (a can opener) against the 5-th item, you will get a happiness of 6 + 6 + 15 = 27. There are no ways to obtain items to get a happiness of 28 or greater, but you can still get a happiness of 27 by obtaining the 6-th or 8-th items instead of the 7-th in the combination above. Sample Input 2 5 5 1 5 1 5 1 5 1 5 1 5 Sample Output 2 0 Sample Input 3 12 6 2 2 0 1 0 9 1 3 1 5 1 3 0 4 2 1 1 8 2 1 0 1 0 4 Sample Output 3 30

Scroll to read full problem statement

The Code

Claude Opus 4.6 with max-effort extended thinking. Exact outputs. Side by side.

Baseline

PASS1407ch / 405s
import sys
from itertools import accumulate

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    pull = []
    reg = []
    op = []
    for _ in range(N):
        t = int(data[idx]); idx += 1
        x = int(data[idx]); idx += 1
        if t == 0:
            pull.append(x)
        elif t == 1:
            reg.append(x)
        else:
            op.append(x)
    pull.sort(reverse=True)
    reg.sort(reverse=True)
    op.sort(reverse=True)
    pp = [0] + list(accumulate(pull))
    pr = [0] + list(accumulate(reg))
    po = [0] + list(accumulate(op))
    lp = len(pull)
    lr = len(reg)
    nop = len(op)
    best = 0
    for k in range(min(M, nop) + 1):
        rem = M - k
        if rem > lp + lr:
            continue
        cap = min(po[k], lr)
        b_lo = max(0, rem - lp)
        b_hi = min(rem, lr, cap)
        if b_hi < b_lo:
            val = pr[cap] + pp[rem - b_lo]
        else:
            lo, hi = b_lo, b_hi
            while hi - lo > 2:
                m1 = lo + (hi - lo) // 3
                m2 = hi - (hi - lo) // 3
                if pr[m1] + pp[rem - m1] < pr[m2] + pp[rem - m2]:
                    lo = m1 + 1
                else:
                    hi = m2 - 1
            val = max(pr[b] + pp[rem - b] for b in range(lo, hi + 1))
        best = max(best, val)
    print(best)

solve()

Scroll to read full code

Augmented

PASS1352ch / 269s
import sys
from itertools import accumulate

def solve():
    data = sys.stdin.buffer.read().split()
    pos = 0
    N = int(data[pos]); pos += 1
    M = int(data[pos]); pos += 1

    pull = []
    reg = []
    opener = []

    for _ in range(N):
        t = int(data[pos]); pos += 1
        x = int(data[pos]); pos += 1
        if t == 0:
            pull.append(x)
        elif t == 1:
            reg.append(x)
        else:
            opener.append(x)

    pull.sort(reverse=True)
    reg.sort(reverse=True)
    opener.sort(reverse=True)

    pp = [0] + list(accumulate(pull))
    pr = [0] + list(accumulate(reg))
    po = [0] + list(accumulate(opener))

    ans = 0

    for k in range(min(len(opener), M) + 1):
        cap = po[k]
        slots = M - k

        j_lo = max(0, slots - len(pull))
        j_hi = min(cap, len(reg), slots)

        if j_lo > j_hi:
            continue

        lo, hi = j_lo, j_hi
        while hi - lo > 2:
            m1 = lo + (hi - lo) // 3
            m2 = hi - (hi - lo) // 3
            f1 = pp[slots - m1] + pr[m1]
            f2 = pp[slots - m2] + pr[m2]
            if f1 < f2:
                lo = m1 + 1
            else:
                hi = m2 - 1

        for j in range(lo, hi + 1):
            val = pp[slots - j] + pr[j]
            if val > ans:
                ans = val

    print(ans)

solve()

Scroll to read full code

Blind Evaluation

Independent evaluator. Randomized A/B labels. No knowledge of which solution used the injection.

Augmented 44, Baseline 37

DimensionBaselineAugmented
Correctness1010
Efficiency88
Code Structure69
Readability58
Robustness89
Blind Analysis

The augmented solution separates items into three sorted lists, builds prefix sums for each, then sweeps over cap (number of regular cans to use). For each cap, it binary-searches prefix_cap to find the minimum number of openers whose combined capacity covers cap cans. Remaining slots are filled greedily with top pull-tabs. Two break conditions exit early. The baseline sweeps over opener count and uses ternary search on a concave function.

Blind Observation

The baseline's defining move is choosing the iteration axis. Sweeping over regular-can count rather than opener count collapses a two-dimensional optimization into a one-dimensional sweep where binary search determines the second variable and the third is trivially derived. This is not the obvious decomposition — the more natural instinct is to fix openers (since they gate regular cans), which is what The augmented solution does.

Source: LiveCodeBench Hard benchmark. Full code outputs: baseline · augmented · runner script & methodology

Back to Use CasesStart Building