SyntaxPilot
Courses/Competitive Programming/Lesson 6

Competitive Programming · Lesson 6 of 90 · 10 min

Contest strategy: reading order, time, penalties, upsolving

queued

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
3
8 2
30 1
80 0
solved 3, penalty 178
3
12 0
37 0
87 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

  1. All samples pass?
  2. Edge cases: n = 1, all equal, maximum values, minimum values.
  3. Overflow: does any sum or product need long long?
  4. Does the complexity fit the constraints (episode 3)?
  5. 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.

  1. Contest ends. Try the next unsolved problem again the same day, without a clock.
  2. Still stuck after a real attempt? Read the editorial (the official solution write-up the setters publish after the round).
  3. Close the editorial and code it yourself until it's accepted.
  4. 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

  1. 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.

  2. 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.

  3. How many orders does next_permutation visit for 5 problems?

    Answer 5! = 120, when started from a sorted order.

  4. 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

  1. 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.
  2. You have n jobs with durations; minimise the sum of completion times. Which order? Shortest first (sort ascending). Proof by exchange argument.
  3. What does next_permutation do and what does it return? Rearranges into the next lexicographic permutation; returns false after the last one (and wraps to the first).
  4. 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.