Lcb Doctest

LCB Doctest-Driven Skill

Triggers: competitive programming · code generation · algorithm

Architecture: Spec → Solve → Verify → Recover

PHASE 1 — Read and classify (30 seconds, no code)

Identify:

• TYPE B: starter_code has class Solution: → complete exact class, exact method name
• TYPE A: no starter_code → complete stdin/stdout program

Read the constraints. Write:

N = <largest input size>
Time limit implication: N=10^5 → O(N log N) max. N=10^6 → O(N) max.

PHASE 2 — Build 3 doctests as specification (before any implementation)

Write exactly 3 doctests. These are your contract — your code must pass all of them.

Doctest 1 — Happy path: trace through the first public sample step by step. Show intermediate states. Verify your trace matches the expected output.

Doctest 2 — Edge case: minimum input (N=1, empty, all-same, k=0). Trace it.

Doctest 3 — Adversarial: an input where a greedy or off-by-one approach fails. Think: what assumption would a naive solution make that is wrong? Construct an input that violates it. Derive the expected output by tracing.

Trace rule: write trace: [show steps] → result X. If X ≠ expected, your algorithm understanding is wrong — re-read the problem before writing code.

TYPE B format:

class Solution:
    def exactMethodName(self, args):  # exact name from starter_code
        """
        # trace: [step 1] → [step 2] → result
        >>> Solution().exactMethodName(sample_1)
        expected_1

        # trace: edge case → result
        >>> Solution().exactMethodName(edge_input)
        expected_2

        # trace: adversarial → naive gives X but correct gives Y
        >>> Solution().exactMethodName(adversarial_input)
        expected_3
        """

TYPE A format: wrap in solve(data):

def solve(data):
    """
    # trace: sample → result
    >>> solve("line1\\nline2")
    'output'

    # trace: edge → result
    >>> solve("edge_input")
    'edge_output'

    # trace: adversarial → result
    >>> solve("adversarial_input")
    'adversarial_output'
    """
    lines = data.strip().split("\\n")
    idx = 0
    def inp():
        nonlocal idx; v = lines[idx]; idx += 1; return v
    # implementation using inp()
    return str(result)

if __name__ == "__main__":
    import sys
    print(solve(sys.stdin.read()))

PHASE 3 — Implement

Write your best solution. Apply these guards automatically:

• Recursion/DFS detected → add import sys; sys.setrecursionlimit(300000) first line
• N ≥ 10^5 → verify no nested loops over N. Count using arithmetic, not iteration over all pairs.
• Multiple days/groups → trace the pointer arithmetic on a 3+ group example before finalizing

PHASE 4 — Verify against doctests AND public test cases

Run each doctest mentally. Then run against all public sample inputs from the problem.

Doctest 1: input → my code returns X | expected Y | PASS/FAIL
Doctest 2: input → my code returns X | expected Y | PASS/FAIL  
Doctest 3: input → my code returns X | expected Y | PASS/FAIL
Public sample 1: input → my code returns X | expected Y | PASS/FAIL
Public sample 2: input → my code returns X | expected Y | PASS/FAIL

If ALL pass → emit immediately. Do not modify.

If any FAIL → go to Phase 5.

PHASE 5 — Recovery loop (up to 5 attempts)

For each failure:

1. Name the bug in one sentence. Be specific: "pointer advances by 1 instead of 2 on even days" not "logic error".

2. Classify the failure:

   • Single test fails, others pass → minimal fix (change only the failing lines)
   • Multiple tests fail → algorithmic error, rewrite from scratch
   • Doctest 3 (adversarial) fails → your core assumption is wrong, rewrite

3. Apply fix and re-verify ALL doctests and ALL public samples.

4. If still failing after fix, repeat from step 1. Max 5 total attempts.

5. After 5 failed attempts → emit best version with comment # NOTE: some tests failing after 5 recovery attempts.

Do not modify a passing test's expected value to make it pass — fix the code instead.

PHASE 6 — Emit

Plain Python only. No markdown fences. No explanation text.

# AUDIT: type=A/B | doctests=3 | recovery_attempts=N | final=PASS/PARTIAL