CP Workflow

How to attack a problem, and how to spend a contest.

Reading a problem

1. Read it fully, twice. Do not start coding from the first paragraph.
2. Read the constraints. They pin down the intended complexity — see Problem Pattern Recognition.
3. Read the samples and work through the first one by hand. If your understanding does not reproduce it, your understanding is wrong.
4. Note the output format — precision, “impossible” sentinel, multiple test cases, 1-based or 0-based.
5. Look for the unused constraint. If the statement guarantees the graph is a tree, or that $\sum n\le 10^5$, that guarantee is the key.

Solving

1. What is the brute force? Establish a correct baseline, even if too slow.
2. What is the bottleneck? Which part of the brute force is redundant.
3. Look for structure — sortedness, monotonicity, a tree, a DAG, independence.
4. Try the standard reformulations — binary search the answer, count contributions instead of configurations, go offline, condense, dualise.
5. Solve a simpler version — smaller $n$, one query, no updates — then add the missing piece.
6. Verify the complexity against the constraints before writing anything.

Before coding

• Write the state and transition down (for a DP), or the invariant (for a greedy).
• Convince yourself it is correct. A greedy needs an exchange argument; a construction needs a check on small cases.
• Check the edge cases in your head: $n=1$, empty input, all equal, the maximum value.
• Estimate the memory.

Ten minutes of thinking here saves an hour of debugging. Most wrong submissions are wrong ideas, not wrong code.

While coding

• Write it straightforwardly first; optimise only if needed.
• Use long long by default when values can be large.
• Add asserts at the boundaries.
• Test the samples before submitting — every time.

After a wrong answer

Do not immediately resubmit a small tweak. Instead:

1. Re-read the statement.
2. Test the edge cases.
3. Stress test against a brute force.

A blind resubmit costs a penalty and rarely works.

Contest strategy

Phase	Action
First 5 minutes	read all the problems (or the first several), sort by apparent difficulty
Then	solve in increasing difficulty; the scoreboard is a useful signal
Stuck for 15+ min	switch problems; return with fresh eyes
Stuck on implementation	it may be the wrong approach
Last 30 min	secure what you have; stress test the risky ones
Any time	if you have an idea but no time, write it down before it evaporates

Reading all the problems first is the highest-value habit. Difficulty order on the statement is a suggestion, not a guarantee, and an easy problem later in the set is often the cheapest points available.

Time allocation

• If a problem takes more than ~25% of the remaining contest time, consider abandoning it.
• Prefer two medium problems over one hard one.
• Implementation-heavy but conceptually easy problems are worth doing — they are reliable points.
• If a solution needs 200 lines and you have 20 minutes, look for a simpler approach.

Team contests

• Divide by reading — each member reads a subset, then everyone summarises.
• One person codes while the others think; do not queue at the machine.
• Discuss the approach before claiming the keyboard.
• Print the code when debugging so the machine stays free.
• Agree in advance on who owns which topics.

Practice

Goal	How
Speed	solve problems slightly below your level, timed
Range	pick topics you avoid
Depth	upsolve — after a contest, solve what you could not
Reliability	stress test everything; count your wrong submissions
Templates	maintain and test a library

Upsolving is where most improvement comes from. Solving the problem you failed, without hints, teaches more than three easy problems.

Keeping a library

Maintain tested implementations of the structures you use (segment tree, DSU, flow, NTT, geometry primitives). Test each once, thoroughly, and never debug it again during a contest. See Templates.

See also: Contest Checklist · Problem Pattern Recognition · Debugging