Thanks to Kevin Bodurtha for creating this problem! As a sidenote - systems
based on this are found in many other competitions, even in competitive programming sites, like Codeforces.
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 if 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.
The first official CodeAbbey Chess Tournament 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 the
Linear Congruential Generator from problem 25
(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 1210 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 1210 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.