Lab 09 — ICPC Contest Simulation

Goal

Simulate a 5-hour ICPC-style contest: 6–10 problems of varying difficulty, single team, no internet, paper and pen allowed. Practice contest strategy: problem selection, time management, debugging under pressure.

Background

ICPC contests are the gold standard for competitive programming practice:

• 5 hours
• ~10 problems sorted A–J in roughly increasing difficulty (but not strictly)
• Penalty per wrong submission (20 minutes)
• Final ranking by # problems solved, then total time

This lab is a meta-lab: rather than teach an algorithm, it builds the contest operating system of the candidate.

Interview Context

ICPC training transfers to:

• Quant hiring (Jane Street, Citadel value ICPC experience)
• Google L6+ research interviews (sometimes)
• General algorithmic confidence under time pressure (transferable)

Direct application of contest mode to industry interviews: low. But the training effect is high.

When to Skip This Topic

Skip if any of these are true:

• You’re not interviewing at competitive-friendly firms
• You have less than a month for this phase
• You haven’t done Phase 11 mocks at your target level — those are higher leverage

If you do this lab, do it only after exhausting Phase 11.

Problem Statement

Run a 5-hour contest. Sources of problem sets:

• Codeforces Educational rounds
• Codeforces Div 2 (rounds 600+)
• ICPC regional sets on UVa Online Judge or DOMjudge replays
• Atcoder Beginner Contest (ABC) — easier, 100 min
• Atcoder Regular Contest (ARC) — medium, 120 min
• Kattis archive

Required mix for a 5-hour set:

• 2 trivial problems (sanity / warm-up; should solve in 15 min each)
• 3 medium problems (1 hour each)
• 2 hard problems (1.5+ hours, often unsolved)
• 1 problem-killer (often unsolved by anyone except top teams)

Constraints

• Time: 5 hours, single uninterrupted block
• No internet (except for the problem statements)
• Programming language of your choice (typically C++ for competitive)
• Penalty: simulate the 20-minute penalty per WA
• No external help / collaboration

Clarifying Questions (to yourself before starting)

1. Which 2 problems will I attempt first? (Decision in 5 min of reading.)
2. What’s my “hard problem cutoff” — at what point do I move on?
3. What’s my time budget for debugging vs writing?
4. How will I track time per problem?

Examples (suggested contest sets)

• Beginner: ABC 250 (8 problems, 100 min, but extend to 3 hours for practice)
• Intermediate: Codeforces Round 800, Div 2 (4–5 problems, 2 hours; extend with a Div 1 problem)
• Advanced: Any ICPC regional set on Kattis

Brute Force / Naive Strategy

• Read problems A → J in order
• Attempt in order
• Stuck on B → keep grinding

This is the wrong strategy. All experienced contestants read every problem in the first 30 minutes.

Brute Force Complexity

Linear-strategy ranking is in the bottom half. The optimization is meta: contest strategy.

Optimization Path

Phase 1 (0–30 min): Reading and triage

• Read all problems. Categorize each as: trivial (T) / medium (M) / hard (H) / unknown (?)
• Note any problem you immediately know how to solve
• Estimate time-to-solve for each known problem
• Decide which 2 problems to start with (lowest-risk T or known-M)

Phase 2 (30 min – 3 hours): Bulk solving

• Solve the T’s first (lock in points)
• Tackle M’s one at a time
• Time-cap each: 45 min to first attempt; if no insight at 60 min, switch
• Submit only when you’ve tested at least 2 cases (penalty hurts)
• Track submitted vs accepted on a paper grid

Phase 3 (3–4.5 hours): Hard problem attack

• Attempt your best H candidate
• If stuck for 30 min, switch to another M or H
• Don’t sink the last hour on one H if no progress

Phase 4 (last 30 min): Last-chance and verification

• Verify your AC submissions (any bugs you noticed but didn’t fix?)
• Submit any partial solutions
• Hand-test edge cases on solved problems

Final Expected Approach

Run the contest, then write a post-mortem:

• Problems solved: ___
• Penalty time: ___
• Problems unread: ___ (should be 0)
• Problems where you knew the approach but couldn’t implement: ___
• Problems where you couldn’t find the approach: ___
• Wasted time on (problem X): ___
• Bug that cost you (problem Y): ___

Data Structures (the contestant uses)

• Templates file (.h for C++ or snippets): segment tree, DSU, FFT, Dijkstra, BFS, mod arithmetic
• Paper grid: problem letter | reading time | first-attempt time | submissions | AC time
• Stack-rank: priority order updated as problems are read

Correctness Argument

Strategy correctness is empirical: track your own performance over 5–10 contests. Adjust based on:

• Where did I spend too long?
• Which problems did I misclassify?
• Which problem types do I consistently miss?

Complexity

Contest itself: 5 hours. Post-mortem: 1 hour. Per-week investment: ~1 full contest + a few targeted upsolves = 8–12 hours.

Implementation Requirements

• Pre-built template file (start with KACTL or your own)
• Local judging setup: compile + run + diff against expected output
• Stress-testing harness (Lab 05 from Phase 10 applies directly)
• A timer / phone alarm for the 5 hours

Tests

This is the test. The contest is the test.

Self-evaluation rubric:

• problems solved

• Time per problem
• WA-to-AC ratio
• Quality of stress-tests during contest

Follow-up Questions (post-mortem)

• Which problem could I have solved with 30 more minutes? → Drill that topic.
• Which problem did I solve in time that I should have submitted faster? → Bug-hunt training.
• Which problem did I skip that I should have attempted? → Misclassification — calibrate.
• Did I run out of time or run out of ideas? → Different fixes.

Product Extension

• Long-term: ICPC-style training builds engineering reflexes that transfer to:
  • Performance debugging under deadline
  • Triage of multiple bugs simultaneously
  • Estimation of task duration (notoriously hard for engineers)

Language/Runtime Follow-ups

• C++: dominant in competitive. Compile-time templates pay off.
• Python: acceptable for problems with N ≤ 10^5; risk TLE on tight problems.
• Java: middle ground; some teams use it.
• Rust: rising; some teams use; standard library less batteries-included than C++.

Common Bugs (contest-specific)

1. Submitted without testing. Penalty bug.
2. Submitted with debugging prints still in code. WA.
3. Forgot to read a problem. Discovered 2 hours later you had a free solve.
4. Spent 90 minutes on one problem you couldn’t solve. Sunk-cost trap.
5. Submitted brute force expecting partial credit. ICPC has no partial; only full AC.
6. Wrong I/O format. Read the spec carefully — especially expected output line endings.

Debugging Strategy (during contest)

• 5-min rule: if not finding a bug in 5 min, write a stress test (Lab 05)
• Random small inputs vs brute force is a contest superpower
• If stuck on WA, re-read the problem statement entirely — often the bug is misunderstanding, not code

Mastery Criteria

• Complete 5 contests; track scores
• Post-mortem each one and act on findings
• Solve at least 3 problems consistently in a 5-hour Div 2 contest
• Solve at least 1 D-level (Codeforces) problem in 2 hours
• Build a personal template file with ≥ 15 commonly-used snippets
• After 10 contests, identify your top 3 weakness topics; drill them

Suggested Contest Schedule (4 weeks)

Post-mortem after each. Drill weakness topics between contests.