Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 63 ยท Real-World Projects

Project: An ICPC Scoreboard

Build a contest scoreboard: ICPC penalty rules, ranking with ties, and incremental updates with bisect, checked against a full recomputation.

Every contest you have joined ends with a table: teams in rows, problems in columns, and a rank that everyone argues about. In this project you build that table yourself. The rules are those of the ICPC (the programming contest for university teams): teams are ranked by the number of problems solved, and ties are broken by a penalty time.

The scoreboard is a good project for three reasons. The rules are small but full of traps (wrong runs count only sometimes). Ranking with ties needs care. And a live scoreboard must update after every single submission, which makes it a nice exercise in incremental updates instead of recomputing everything. You will use sorting from sorting, events and sweeps and the checking habits from stress testing.

The rules

A scoreboard is fed a stream of runs. Each run says: at what minute of the contest, which team, which problem, and the verdict. We only care about three verdicts: OK (accepted), WA (a real wrong answer or other judged failure) and CE (compilation error).

The ranking rules are these:

  1. A team that solved more problems is ranked higher.
  2. Among teams with the same number of solved problems, the team with the smaller total penalty is higher.
  3. The penalty of one solved problem is the minute of the accepted run plus 20 minutes for every earlier wrong run on that problem.
  4. Wrong runs on a problem that is never solved cost nothing.
  5. Runs submitted after a problem is already solved are ignored.
  6. A compilation error does not count as a wrong run.
  7. Teams with equal solved count and equal penalty share a rank.

Rule 4 is the one that surprises people: a team that fails problem C five times and never solves it loses no points. Because of that, a wrong run never changes the standings at the moment it happens; only an accepted run does. We will use that fact later to make updates fast.

flowchart TD
  R["New run"] --> S{"Problem already solved by this team?"}
  S -- "yes" --> I["Ignore the run"]
  S -- "no" --> V{"Verdict"}
  V -- "CE" --> I
  V -- "WA" --> W["Count one more wrong run"]
  V -- "OK" --> A["Solve the problem:<br/>penalty = minute + 20 * wrong runs"]

What happens to one run. Only the OK branch changes a team's score.

Step 1: a team and its score

Each team remembers two small dictionaries: the number of wrong runs per problem, and the minute at which each problem was solved. Everything else (solved count, penalty) is computed from them.

The ranking key of a team is the tuple (-solved, penalty, last_solve). Negating solved makes "more problems first" work with Python's ascending sort. The third element is the minute of the team's last accepted run. Real contests often use it as an extra tie-breaker, and we include it because it is a small, realistic detail: with equal solved count and equal penalty, the team that finished earlier ranks higher.

Python Teams, runs and a sorted table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the table by hand. Ants solved A at minute 12 and B at minute 70 after two wrong runs, so the penalty is 12 + (70 + 40) = 122. The wrong run on A at minute 95 is ignored because A was already solved. Bees: A costs 25 + 20 = 45, C costs 100, total 145. Crows solved two problems with no wrong runs: 30 + 80 = 110. The Dogs have a wrong run but no solved problem, so they have 0 penalty and sit last. Crows beat Ants and Bees on penalty even though all three solved two problems.

The PENALTY constant is a rule of the contest, not of the algorithm. Keeping it in one place lets you adapt the scoreboard to other rule sets, such as 10-minute penalties or contests with a CE penalty.

Step 2: ties

Two teams that cannot be separated by the key must show the same rank, and the next rank skips the numbers in between. This is called competition ranking (1, 2, 2, 4), the same style used in sports tables. The code above already does it: the variable rank only changes when the key changes, and then it is set to the position i, not to the previous rank plus one.

Python Competition ranking with ties

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bees, Crows and Dogs share rank 2, and Eels are rank 5, not 3. The wrong version prints [1, 2, 2, 2, 3], which hides that three teams are ahead of Eels. Printing both versions next to each other is a quick way to convince yourself, and a good test to keep.

Step 3: incremental updates

A real scoreboard receives thousands of runs, and viewers refresh it all the time. Sorting all teams after every run costs O(T log T) per run for T teams. We can do better with the observation from the rules: only an accepted run changes a team's key, and it changes only that one team's key.

Keep a sorted list keys that holds the key of every team (duplicates allowed, because tied teams have equal keys). Then:

  • The rank of a team is 1 + (number of keys strictly smaller than its own). That is bisect_left(keys, key) + 1, found in O(log T).
  • An accepted run removes the team's old key from the list and inserts the new one. Both use binary search. The list shift costs O(T) in memory moves, but it is a very fast C operation, and for thousands of teams it is far cheaper than a full sort.
  • A wrong run only increments a counter: O(1).

This is the same idea as keeping a sorted structure instead of re-sorting, which you saw in Fenwick and segment trees in a stronger form. Here the plain bisect module is enough.

Python A scoreboard that updates incrementally

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The assert is the important line. It plays the role of the brute force in stress testing: slow_ranks is simple and obviously right, and the incremental board has to agree with it after every run. If you break submit (for example by forgetting to delete the old key), the assertion fires at the first bad step.

Step 4: the display

Printing a scoreboard is mostly formatting, and a small amount of care makes it readable: fixed column widths, a column per problem, and a + or - marker as on the real contest screens. A cell can show +2 (solved after 2 wrong runs), -3 (3 wrong runs, unsolved) or stay empty. You can build it from the two dictionaries in Team, and printing f"{cell:>5}" for each problem letter gives aligned columns.

Ideas to extend it

  • Freezing. Real contests freeze the board for the last hour. Keep two boards: the public one stops updating at minute 240 while the real one continues, and a reveal step copies results over team by team.
  • First solve. Mark the first team to solve each problem with a special symbol. A dictionary first[problem] that stores the earliest accepted minute is enough.
  • Different rules. IOI-style contests score by points per problem, and Codeforces by decaying points. Replace _key and keep the same bisect skeleton.
  • Stability. If two teams are fully tied, sort them by name so the display does not flicker between refreshes.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A team submits three wrong runs on problem C and never solves it. How much penalty does C add?

    Wrong runs are only charged when the problem is eventually solved. An unsolved problem adds no penalty.
  2. 2. Four teams have keys that sort as A < B = C < D. What are their ranks with competition ranking?

    Tied teams share the rank equal to the position of the first of them (2), and the next team gets its own position (4).
  3. 3. Which run actually changes a team's position in the standings?

    Wrong runs are only counted when the problem is solved later, so only OK runs change the key. That is what makes the update cheap.
  4. 4. What does bisect_left(keys, key) + 1 compute when keys is a sorted list of all team keys?

    bisect_left returns how many keys are strictly smaller than the given key. Adding 1 gives the shared rank for tied teams.
  5. 5. Why does the incremental test compare against slow_ranks after every run?

    It is the stress-testing idea: a slow, simple reference checks the clever version on many random runs.

Summary

  • ICPC ranking: more solved problems first, then smaller penalty, where a solved problem costs its minute plus 20 per earlier wrong run.
  • Wrong runs on unsolved problems are free, runs after a solve are ignored and compilation errors do not count.
  • Use a key tuple such as (-solved, penalty, last_solve) so Python's sort and bisect do the work.
  • Competition ranking gives tied teams the position of the first of them: 1, 2, 2, 4.
  • Only accepted runs change a key, so keep a sorted key list and update it with bisect_left and insort.
  • Always test an incremental structure against a simple full recomputation.

Next: Project: A Training Plan Tracker