vi. Contest Strategy

How to read, think, code and spend time, for individual rounds (Codeforces, AtCoder) and team contests (ICPC).

Reading

1. Read the whole statement twice. Work the first sample by hand. If your understanding doesn’t reproduce it, your understanding is wrong.
2. Rewrite it as a mathematical contract: objects, operations, objective, constraints, required output. Story text hides the real problem.
3. Look at every distinction: subsequence vs substring, exactly $k$ vs at most $k$, path vs walk vs simple path, inclusive endpoints, whether zero operations are allowed, distinct vs not.
4. Look for the strange guarantee. “The graph is a tree”, "$\sum n\le 2\cdot 10^5$", ”$a_i$ is a permutation”, "$k\le 20$", “answer exists”: an unusual guarantee is almost always the key.
5. Read the constraints and the time limit, and derive the target complexity (Complexity).

Solving

1. Brute force first. It shows the structure and gives you a stress-test oracle.
2. Find the redundancy. Which part of the brute force recomputes the same thing?
3. Look for structure: monotonicity (binary search, two pointers), independence (per-bit, per-prime, per-component), a tree or DAG, convexity, small answer, small alphabet.
4. Try the standard reformulations (Attacking a Problem): binary search the answer, count contributions, complement, go offline or reverse time, sort by a clever key, fix one variable and optimise the rest, think about the final state.
5. Solve a special case: $n$ small, one query, no updates, all values distinct, a path instead of a tree. Then generalise.
6. Brute force tiny cases and stare at the output for constructive and counting problems. Search OEIS for integer sequences.
7. Prove it or stress test it before writing the full solution. A greedy without an exchange argument is a guess.

Coding

• Write the plan first: state and transitions for a DP, invariants for a greedy, which structure stores what.
• Use tested library code (Templates) and don’t rewrite a segment tree under pressure.
• Use ll by default for values, int for indices.
• Name things by meaning. dp[i][j] with a comment beats single letters you’ll misread at 2 a.m.
• Estimate the memory before writing the structure, not after an MLE.
• Test the samples, then edge cases, before submitting.

After a wrong answer

Don’t resubmit a tweak. Re-read the statement, test the edges, then stress test (Debugging). Each blind resubmit costs penalty and rarely helps.

Spending time

Situation	Action
Start of round	read the first several problems; sort by your own estimate
Stuck 20+ minutes without an idea	switch problems; come back later with fresh eyes
Stuck on implementation, not on the idea	suspect the approach itself, not just the code — a correct idea rarely needs this much fighting
Idea needs 300 lines	look for a simpler formulation; a long solution is usually not intended
A problem would eat more than ~25% of the remaining time	consider abandoning it for now; two medium problems usually beat one hard one
Two WAs	stress test before a third submit
Last 20-30 minutes	secure what you have, check the risky solutions, write down ideas
Codeforces with hacks	lock only when sure; check your solution against anti-hash and anti-SPFA tests

Codeforces scoring decays with time, so solve in increasing difficulty. ICPC penalty is time plus 20 minutes per wrong try, so the easy problems must be fast and correct. AtCoder has no partial credit and a 5-minute penalty per WA, which rewards careful first submissions. Implementation-heavy but conceptually easy problems are worth doing regardless of length — they are reliable points, unlike a short but conceptually hard one.

Team contests (ICPC)

• Split the problem set by reading. Each member summarises the problems they read in two sentences, with an estimated difficulty.
• Only one person types. The others think, write code on paper, or debug from a printout. A free machine is the scarce resource.
• Agree on the approach and data format before someone claims the keyboard.
• Keep a board with each problem’s state: unread, read, idea, coding, WA, AC, and who owns it.
• Divide topics in advance (geometry person, strings/maths person, graphs/DP person) and keep a 25-page team notebook (Templates).
• In the last hour, pair up on the most likely problem rather than spreading out.
• Watch the scoreboard: a problem many teams solve early is easier than it looks.

Practice

Goal	How
Rating	virtual contests at or slightly above your level, then upsolve every problem within reach
Speed	many problems slightly below your level, timed
Depth	hard problems from AtCoder AGC, Codeforces Div 1 D-F, ICPC finals; think 1-2 hours before reading the editorial
Breadth	the topic list on this site; pick the topics you avoid
Reliability	stress test, count wrong submissions, keep a mistake log

Upsolving is where most improvement happens. After reading an editorial, write down the key idea in one sentence. Recognising that idea next time is the skill.

ICPC team strategy in depth

Phase	What the team does
first 15 minutes	split the set into three parts; each member reads their part and reports difficulty; the fastest typist codes the easiest problem immediately
triage	sort problems by (scoreboard solves, own estimate); everyone keeps a list: unread / understood / idea / coding / accepted
assignment	one owner per problem; a second person checks the idea before it reaches the computer
the computer	only typing and running; think and debug on paper; announce before taking the keyboard
avoiding duplicate work	a shared paper board with the status of each problem
abandoning	if a problem has no progress after ~30–40 minutes of one person, or the idea is unproven and the scoreboard says it is hard, switch; come back with fresh eyes
penalty	each wrong submission costs 20 minutes: test samples and edge cases first, but do not delay an accepted solution for polishing
last hour	freeze: decide which 1–2 problems are realistic, put everyone on them; submit risky solutions only when time is running out

Proof: why easy problems first minimizes penalty

Penalty is the sum of the acceptance times. For problems with solving times $t_1,\dots ,t_k$ done in that order, the penalty is ${\sum }_i(k-i+1)t_i$ plus wrong-attempt costs; by the rearrangement inequality this is minimized when the $t_i$ are sorted increasingly (shortest first), exactly as in scheduling to minimize total completion time.

Contest practice sets

Source	What it offers
ICPC World Finals problem sets	the hardest team sets; many are on Kattis and in the Codeforces Gym
European regionals: NWERC, SWERC, CERC, NEERC (and its successor NERC)	strong 5-hour team sets, archives in the Codeforces Gym; NWERC also on Kattis
subregionals: GCPC (Germany), NCPC (Nordic)	slightly easier, good warm-up; on Kattis
ICPC Asia regionals and ICPC Latin America regional	many sets in the Codeforces Gym
NAC and North American regionals	on Kattis
Codeforces, AtCoder (ABC / ARC / AGC)	individual rounds; AtCoder for clean math and constructive problems
CSES, Library Checker	standard-technique practice and library verification

How to use them: run a full 5-hour virtual contest as a team (same rules as the real one), then upsolve every problem solved by more than a few teams, and write down the missing idea for each in an upsolving log (Problem Set shows the format).