These are the notes for Competitive Programming episode 6. Two people can solve the same problems and finish hundreds of places apart. This episode shows why with real numbers: how ranking and penalty time work, a brute force over every solving order (live, with next_permutation) that proves shortest-first is best, a calculator that shows why one wrong submission costs more than a minute of testing, and a plan for contest day: reading order, the standings, the 20-minute stuck rule, and upsolving with a log. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
How ranking works
Real-life example: an inter-school quiz.
| At a school quiz | In a contest |
|---|---|
| Most correct answers wins | Ranked first by problems solved (or total score) |
| A tie? The faster team wins | Ties broken by penalty time |
| A wrong buzzer press costs a mark | Each wrong attempt adds a penalty |
ICPC-style penalty (ICPC is the International Collegiate Programming Contest; many online rounds copy its rules):
penalty = Σ over solved problems of (solve minute + 20 × wrong attempts on that problem)
- Minutes are counted from the start of the contest, not from when you opened the problem.
- Wrong attempts only count for problems you eventually solve.
- The per-attempt cost differs: 20 minutes in ICPC, smaller on many online platforms (AtCoder Beginner Contests use 5 minutes), and some rounds use points that shrink over time instead. Always read the contest's rules page. The lessons below hold for all of them.
Which order to solve in
Three problems; you estimate how long each will take you:
| Problem | A | B | C |
|---|---|---|---|
| Minutes needed | 50 | 10 | 25 |
In printed order you finish at minutes 50, 60, 85: penalty 50 + 60 + 85 = 195. Is another order better? Three problems have only 3! = 6 orders, so brute-force them.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> need = {50, 10, 25}; // minutes for A, B, C
vector<int> order = {0, 1, 2};
string name = "ABC";
do {
int clock = 0, penalty = 0;
for (int p : order) {
clock += need[p]; // solved at this minute
penalty += clock;
}
for (int p : order) cout << name[p];
cout << " penalty = " << penalty << '\n';
} while (next_permutation(order.begin(), order.end()));
return 0;
}
Real output:
ABC penalty = 195
ACB penalty = 210
BAC penalty = 155
BCA penalty = 130
CAB penalty = 185
CBA penalty = 145
next_permutation rearranges a range into the next arrangement in sorted order and returns false after the last one, so starting from a sorted {0, 1, 2} the do … while visits all 6 orders.
The best order is B, C, A = 130: shortest first. Same problems, 80 penalty minutes less than the worst order.
Why shortest first wins
Write each solve minute as a sum:
| Order | Solve minutes | Penalty |
|---|---|---|
| A → B → C | 50, 50+10, 50+10+25 | 3·50 + 2·10 + 1·25 = 195 |
| B → C → A | 10, 10+25, 10+25+50 | 3·10 + 2·25 + 1·50 = 130 |
The first problem's time is counted in every later solve minute, so it is multiplied by the most. Put the shortest there. If a longer job ever comes right before a shorter one, swapping them lowers the total: that reasoning is an exchange argument, and episode 14 uses it to prove greedy algorithms. (In scheduling theory this is the "shortest processing time first" rule.)
On contest day: solve what's fastest for you first. Problems on Codeforces and AtCoder are usually sorted roughly by difficulty, so printed order is close, but your strengths matter. Skim the first few problems for a minute or two, estimate, then pick.
The cost of a wrong submission
Two contestants solve the same three problems in the same order:
| B | C | A | |
|---|---|---|---|
| Rushed Ravi (minute, wrong attempts) | 8, 2 WA | 30, 1 WA | 80, 0 |
| Careful Kavya | 12, 0 | 37, 0 | 87, 0 |
#include <bits/stdc++.h>
using namespace std;
int main() {
int k;
cin >> k; // problems solved
long long penalty = 0;
for (int i = 0; i < k; i++) {
int minute, wrong;
cin >> minute >> wrong;
penalty += minute + 20 * wrong;
}
cout << "solved " << k << ", penalty " << penalty << '\n';
return 0;
}
| Input | Output |
|---|---|
38 230 180 0 |
solved 3, penalty 178 |
312 037 087 0 |
solved 3, penalty 136 |
Kavya was slower on every problem and still wins by 42 minutes: her testing cost 4 + 7 + 7 = 18 minutes, Ravi's three wrong attempts cost 60.
Pre-submit checklist
- All samples pass?
- Edge cases: n = 1, all equal, maximum values, minimum values.
- Overflow: does any sum or product need
long long? - Does the complexity fit the constraints (episode 3)?
- Debug prints removed? Right file, right language?
One minute of checking is cheaper than one wrong attempt.
Reading order and the standings
Real-life example: a board exam.
| In a board exam | In a contest |
|---|---|
| Read the whole paper first, then start | Skim A, B, C: story, constraints, samples |
| Classmates finishing a question fast: it's easy | The live standings: many solved D? Try D next |
| Stuck? Move on, come back later | The 20-minute rule |
The standings (scoreboard) show how many contestants solved each problem so far. A problem with many solves is usually easier than its letter suggests.
The 20-minute stuck rule
- No new idea for about 20 minutes → switch to another problem.
- Before switching, write your current idea in a comment so you don't restart from zero.
- A wrong answer you can't find is different: build a stress test (episode 5).
- In the last 15 minutes, don't open a new problem; finish the one you're closest to.
- Never let one problem eat the whole contest.
Upsolving
Upsolving means solving, after the contest, the problems you couldn't solve during it. It is where most improvement comes from.
- Contest ends. Try the next unsolved problem again the same day, without a clock.
- Still stuck after a real attempt? Read the editorial (the official solution write-up the setters publish after the round).
- Close the editorial and code it yourself until it's accepted.
- Write one line in your upsolve log: the idea you missed.
date | contest | problem | idea I missed
28 Oct | Round X | C | reset globals per test
28 Oct | Round X | D | best must start at LLONG_MIN
Aim to upsolve at least one problem beyond the last one you solved. Read the log before every contest.
Common mistakes
| Mistake | Result | Why | Fix |
|---|---|---|---|
| Always solving in printed order | higher penalty | a slow problem first is counted many times | fastest-for-you first |
| Submitting as soon as samples pass | +20 min (ICPC) per wrong attempt | samples are weak tests | edge cases + checklist |
| 60 minutes stuck on one problem | easier problems unsolved | sunk-cost feeling | 20-minute rule, check standings |
| Closing the tab after the contest | the same mistake next week | no learning loop | upsolve + a one-line log |
| Not reading the rules page | surprises in scoring | rules differ by contest | read penalties and scoring first |
Mini project: a contest planner
Extend the order program: read k problems with estimated minutes, sort them, and print the best order with each solve minute and the total penalty. Then add an optional "wrong attempts so far" per problem.
#include <bits/stdc++.h>
using namespace std;
int main() {
int k;
cin >> k;
vector<pair<int, char>> p(k);
for (int i = 0; i < k; i++) { cin >> p[i].first; p[i].second = 'A' + i; }
sort(p.begin(), p.end()); // shortest first
long long clock = 0, penalty = 0;
for (auto [mins, name] : p) {
clock += mins;
penalty += clock;
cout << name << " solved at minute " << clock << '\n';
}
cout << "penalty " << penalty << '\n';
}
Input 3 / 50 10 25 prints B at 10, C at 35, A at 85 and penalty 130, matching the brute force.
The same planner in Java and Python:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
int[][] p = new int[k][2];
for (int i = 0; i < k; i++) { p[i][0] = sc.nextInt(); p[i][1] = i; }
Arrays.sort(p, (x, y) -> x[0] - y[0]); // shortest first
long clock = 0, penalty = 0;
for (int[] q : p) {
clock += q[0];
penalty += clock;
System.out.println((char) ('A' + q[1]) + " solved at minute " + clock);
}
System.out.println("penalty " + penalty);
}
}
k = int(input())
mins = list(map(int, input().split()))
order = sorted(range(k), key=lambda i: mins[i]) # shortest first
clock = penalty = 0
for i in order:
clock += mins[i]
penalty += clock
print(f"{chr(65 + i)} solved at minute {clock}")
print(f"penalty {penalty}")
Practice
-
Problems need 40, 15, 15 and 30 minutes. What is the smallest penalty with no wrong attempts?
Answer
Order 15, 15, 30, 40: solve minutes 15, 30, 60, 100. Penalty = 205. -
You solved B at minute 12 after 1 wrong attempt and A at minute 40 after none. You also tried C three times and never solved it. ICPC penalty?
Answer
(12 + 20) + 40 = 72. Wrong attempts on unsolved C don't count. -
How many orders does
next_permutationvisit for 5 problems?Answer
5! = 120, when started from a sorted order. -
Is "solve the highest-scoring problem first" right when ranking is by points that shrink with time? Discuss.
Answer
Not automatically: points lost per minute and the time each problem takes both matter. Estimate the points you lose by delaying each problem, and still avoid wrong attempts.
Quick quiz
Three problems need 30, 5 and 15 minutes. With no wrong attempts, what is the smallest penalty?
A) 50 · B) 75 · C) 80 · D) 110
Answer
B. Shortest first: B at 5, C at 20, A at 50. Penalty = 5 + 20 + 50 = 75.
Interview questions
- How is ICPC ranking computed? By problems solved, then by penalty: the sum of solve minutes plus 20 minutes per wrong attempt on solved problems.
- You have n jobs with durations; minimise the sum of completion times. Which order? Shortest first (sort ascending). Proof by exchange argument.
- What does
next_permutationdo and what does it return? Rearranges into the next lexicographic permutation; returnsfalseafter the last one (and wraps to the first). - What is upsolving? Solving problems after a contest that you couldn't solve during it, usually with the editorial's help after a real attempt.
Glossary
| Term | Meaning | Example |
|---|---|---|
| ICPC | International Collegiate Programming Contest; its rules are widely copied | 20-minute penalty |
| Penalty time | Tie-breaker: solve minutes plus a cost per wrong attempt | 195 vs 130 |
| Wrong attempt | A rejected submission on a problem | WA, TLE, RE |
| Standings / scoreboard | Live table of who solved what | 400 solved D |
next_permutation |
Turns a sequence into its next arrangement | ABC → ACB → BAC … |
| Permutation | One arrangement of items | B, C, A |
| Exchange argument | Proof that swapping two neighbours in a bad order improves it | long before short → swap |
| Editorial | The official solutions published after a round | read it after a real try |
| Upsolving | Solving unsolved contest problems afterwards | upsolve C after solving A, B |
| Upsolve log | One line per missed idea | "best must start at LLONG_MIN" |
| Time-boxing | Giving a task a fixed time budget | the 20-minute rule |
Summary
- Rank = problems solved, then penalty: solve minutes plus a cost per wrong attempt.
- Shortest-for-you first minimises penalty; the brute force over all 6 orders proved it on our example (130 vs 195).
- A wrong attempt costs more than a minute of testing: use the checklist.
- Skim the first problems, use the standings, and switch after 20 stuck minutes.
- Upsolve every contest and keep a one-line log.
Next episode: prefix sums and difference arrays: two lakh range questions answered instantly.