HARDAtCoderLiveCodeBenchFail → Pass

LCB-03: Art Gallery on Graph

Baseline: FAIL
Augmented: PASS
Injection: 3,081 chars

The Task

There is a simple undirected graph with N vertices and M edges, where vertices are numbered from 1 to N, and edges are numbered from 1 to M. Edge i connects vertex a_i and vertex b_i. K security guards numbered from 1 to K are on some vertices. Guard i is on vertex p_i and has a stamina of h_i. All p_i are distinct. A vertex v is said to be guarded when the following condition is satisfied: - there is at least one guard i such that the distance between vertex v and vertex p_i is at most h_i. Here, the distance between vertex u and vertex v is the minimum number of edges in the path connecting vertices u and v. List all guarded vertices in ascending order. Input The input is given from Standard Input in the following format: N M K a_1 b_1 a_2 b_2 \vdots a_M b_M p_1 h_1 p_2 h_2 \vdots p_K h_K Output Print the answer in the following format. Here, - G is the number of guarded vertices, - and v_1, v_2, \dots, v_G are the vertex numbers of the guarded vertices in ascending order. G v_1 v_2 \dots v_G Constraints - 1 \leq N \leq 2 \times 10^5 - 0 \leq M \leq \min \left(\frac{N(N-1)}{2}, 2 \times 10^5 \right) - 1 \leq K \leq N - 1 \leq a_i, b_i \leq N - The given graph is simple. - 1 \leq p_i \leq N - All p_i are distinct. - 1 \leq h_i \leq N - All input values are integers. Sample Input 1 5 5 2 1 2 2 3 2 4 3 5 1 5 1 1 5 2 Sample Output 1 4 1 2 3 5 The guarded vertices are 1, 2, 3, 5. These vertices are guarded because of the following reasons. - The distance between vertex 1 and vertex p_1 = 1 is 0, which is not greater than h_1 = 1. Thus, vertex 1 is guarded. - The distance between vertex 2 and vertex p_1 = 1 is 1, which is not greater than h_1 = 1. Thus, vertex 2 is guarded. - The distance between vertex 3 and vertex p_2 = 5 is 1, which is not greater than h_2 = 2. Thus, vertex 3 is guarded. - The distance between vertex 5 and vertex p_1 = 1 is 1, which is not greater than h_1 = 1. Thus, vertex 5 is guarded. Sample Input 2 3 0 1 2 3 Sample Output 2 1 2 The given graph may have no edges. Sample Input 3 10 10 2 2 1 5 1 6 1 2 4 2 5 2 10 8 5 8 6 9 6 7 9 3 4 8 2 Sample Output 3 7 1 2 3 5 6 8 9

Scroll to read full problem statement

The Code

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

Baseline

FAIL1191ch / 11s
import sys
from collections import deque

def main():
    input = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    M = int(input[idx]); idx += 1
    K = int(input[idx]); idx += 1

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = int(input[idx]); idx += 1
        b = int(input[idx]); idx += 1
        adj[a].append(b)
        adj[b].append(a)

    # Multi-source BFS with remaining stamina
    # For each vertex, track the max remaining stamina when reached
    best = [0] * (N + 1)  # best remaining stamina at each vertex
    dq = deque()

    for _ in range(K):
        p = int(input[idx]); idx += 1
        h = int(input[idx]); idx += 1
        if h > best[p]:
            best[p] = h
            dq.append((p, h))

    # BFS: propagate stamina
    while dq:
        v, rem = dq.popleft()
        if rem < best[v]:
            continue
        if rem == 0:
            continue
        for u in adj[v]:
            nr = rem - 1
            if nr > best[u]:
                best[u] = nr
                dq.append((u, nr))

    guarded = [i for i in range(1, N + 1) if best[i] > 0]
    print(len(guarded))
    print(*guarded)

main()

Scroll to read full code

Augmented

PASS1282ch / 125s
import sys

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

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = int(data[idx]); idx += 1
        b = int(data[idx]); idx += 1
        adj[a].append(b)
        adj[b].append(a)

    remaining = [-1] * (N + 1)
    max_h = 0
    guards = []
    for _ in range(K):
        p = int(data[idx]); idx += 1
        h = int(data[idx]); idx += 1
        guards.append((p, h))
        if h > max_h:
            max_h = h

    buckets = [[] for _ in range(max_h + 1)]
    for p, h in guards:
        if h > remaining[p]:
            remaining[p] = h
            buckets[h].append(p)

    for r in range(max_h, 0, -1):
        for v in buckets[r]:
            if remaining[v] != r:
                continue
            for u in adj[v]:
                nr = r - 1
                if nr > remaining[u]:
                    remaining[u] = nr
                    if nr > 0:
                        buckets[nr].append(u)

    result = []
    for v in range(1, N + 1):
        if remaining[v] >= 0:
            result.append(str(v))

    sys.stdout.write(str(len(result)) + '\n' + ' '.join(result) + '\n')

solve()

Scroll to read full code

Blind Evaluation

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

Augmented 43, Baseline 22

DimensionBaselineAugmented
Correctness210
Efficiency78
Code Structure68
Readability68
Robustness19
Blind Analysis

Both solutions use multi-source BFS with a "remaining stamina" model: seed each guard's position with its stamina value, then propagate outward, decrementing by 1 per edge. The critical difference lies in initialization and the guarded-vertex predicate. The baseline initializes best to 0 and collects guarded vertices as best[i] > 0. The augmented solution initializes remaining to -1 and collects as remaining[v] >= 0. The defect in The baseline is fatal.

Blind Observation

The bug in The baseline is a classic sentinel collision: using 0 to mean both "unreached" and "reached with zero remaining" collapses two distinct states into one. This is the kind of off-by-one that survives local reasoning ("stamina 0 means you can't go further, so skip") but fails global reasoning ("can't go further does not mean wasn't reached").

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

Back to Use CasesStart Building