Elo Ratings - τὸ Ἀθήναιον

This problem was originally published on CodeAbbey.com around May 24th, 2024

The top-rated Chess players in the world, per FIDE as of October 2024. The values in the "Ratings" column are Elo Ratings.

For competitive games, it is often desired to attach some sort of numerical rating to a player that reflects how well they play. Arpad Elo developed the Elo Rating System as a method for rating players in chess, and it is now the most commonly used rating system for chess players at all levels worldwide (also finding use in some other competitive games and sports). In this problem, we will explore how the Elo Rating System works.

Imagine two players (let's call them A and B) are playing each other in a game of chess. They each have played many games of chess before, and so already have Elo Ratings of Elo_A and Elo_B. After the game, the winner will take some Rating points from the loser. The amount of points transferred to Player A from Player B is calculated by the following equation:

PointsTransferred(A, B) = K * (Result - Expected(A, B))

Where K is the "K-Factor" (explained later), Result is the outcome of the game (1 for Win, 0 for Loss, 0.5 for Draw), and Expected(A, B) is the expected probability that Player A would win over Player B based on their pre-game Elo Ratings, calculated by the following equation:

Expected(A, B) = 1 / (1 + 10 ^ ((Elo_B - Elo_A) / 400))

A note on "K-Factor" - it is typically raised for newly-rated players so that their ratings may quickly adjust to reflect their actual skill. In this problem, we will always set K = 20, which is typical for the average established player.

Motivation while the formulas may look a bit bewildering at first, the idea is very simple, if we consider properties of such a system.

Rating difference of two people relates how often stronger will win against the weaker. People with equal rating are expected to play equally. Difference of 200 means that the stronger player wins about 3 times more often than the weaker.
When the rating is adjusted after the game, the change is smaller if the stronger player wins - i.e. if "prediction" holds. In other words stronger player may win fewer points but lose more points and this is balanced by his victory probability.
System is symmetrical in that one player wins or loses the same amount of points that the other loses or wins. This means that total sum of ratings would keep constant unless newcomers are introduced. (rounding of ratings may cause slight asymmetry though)
System is also "grade-agnostic" - it works the same for champions as for beginners, the same difference of ratings means the same win probability. However players with difference above 200 are not usually paired in real contests.

Problem Statement

The Athenaion is about to host its first official Chess Tournament, which is about to begin! Many contestants from faraway lands have arrived to compete for the event, which is scheduled to last for several days. In total, C contestants have come to participate, and the tournament will last for R rounds.

Each contestant has three numbers associated with them: their ID number, which is a sequential counter of the order of their arrival (with the first to arrive having ID = 0), and their skill, which is an indicator of how well they play chess. For this problem, we'll use a Linear Congruential Generator (use a = 445, c = 700001 and m = 2097152) to pseudo-randomly generate the skill for each player in the order that they arrive. The skill value will be unique to avoid tie-breaking issues.

Additionally, each player also has an Elo Rating associated with them. However, as many of them come from foreign lands using their own unique and incompatible rating systems, each player will start with an Elo Rating of 1200 at the start of this tournament.

At the beginning of each round, all players line up in order of their Elo Ratings. If multiple players have the same Elo Rating, then the players with the greater skill are ranked higher. Then players pair off and each play a game of chess, with the 1st-highest-ranked player competing against the 2nd-highest-ranked player, the 3rd-highest-ranked competing against the 4th-highest-ranked, and so forth.

To determine the outcome of any given game, generate two random values R1 and R2, multiply each one to each player's skill, then compare the results. The larger result indicates the winner of the game. Each player's Elo Ratings are updated accordingly and rounded off to the nearest integer at the end of each Round. Then the process repeats again until all Rounds are complete.

Given C, R, and X0 (inital value for Linear Congruential Generator), determine the Elo Ratings of each player after the tournament has completed.

Input data will contain three integer values C R X0.

Answer should be a series of space-separated values corresponding to the Elo Ratings of each player after the tournament has completed. Values should be reported in ascending order of ID.

Example:

input data:
4 `3` 0

answer:
1191 1189 1191 1229

Let's take a closer look at the example, for clarity's sake.

Four contestants arrive, and we seed the Linear Congruential Generator with X0 = 0, and so the skill levels of each contestant are:

ID | skill level | Elo Rating
-----------------------------
 `0` | 700001      | 1200
 `1` | 1821950     | 1200
 `2` | 1967079     | 1200
 `3` | 1537772     | 1200

Players 2 and 1 are the highest-ranked, and so they play the first game of Round 1. Two random numbers are generated, R1 = 13336989 and R2 = 68938 which are multiplied to each Player's skill to yield 2629962985131 vs 125601589100, so Player 2 wins and Player 1 loses. Their Elo Ratings change to 2010 and 1190, respectively.

Players 3 and 0 are the next highest-ranked, so they play the next game of Round 1. Two more random numbers are generated, R1 = 2017283, R2 = 809880. Player 3 wins and Player 0 loses, so their Elo Ratings also change to 2010 and 1190, respectively.

Players 2 and 3 then face off in Round 2. Two more random numbers are generated, R1 = 386457, R2 = 706902. Player 2 loses and and Player 3 wins, so their Elo Ratings change to 1200 and 1220, respectively.

Players 1 and 0 then face off in Round 2. Two more random numbers are generated, R1 = 698591, R2 = 1194500. Player 1 wins and and Player 0 loses, so their Elo Ratings change to 1200 and 1180, respectively.

Players 3 and 2 then face off in Round 3. Two more random numbers are generated, R1 = 1673045, R2 = 716066. Player 3 wins and and Player 2 loses, so their Elo Ratings change to 1229 and 1191, respectively.

Players 1 and 0 then face off in Round 3. Two more random numbers are generated, R1 = 582267, R2 = 1859120. Player 1 loses and and Player 0 wins, so their Elo Ratings change to 1189 and 1191, respectively.