The Standings On a Circular Track
A circular track has n cells, numbered 0 to n - 1. Cell 0 is the start.
p tokens all begin on cell 0 having completed 0 laps.
There are k rolls, taken in order. Roll i, counting from 0, belongs to
token i mod p. A roll of r advances that token r cells forward along the
circle. Every time a token arrives at cell 0, it has completed one more lap,
including when it arrives there by passing the start several times in one roll.
Print the standings: one line per token, ordered by laps completed from most to fewest; ties broken by the higher cell number; remaining ties broken by the lower token number. Each line holds the token number, its laps and its cell.
``` n = 5, p = 2, rolls 1 2 3 4 5 6
token 0 takes rolls 1, 3 and 5, a total of 9 cells: 1 lap and cell 4 token 1 takes rolls 2, 4 and 6, a total of 12 cells: 2 laps and cell 2
1 2 2 0 1 4 ```
## What most people try first
Keeping only the current cell and adding a lap when the new cell is smaller than the old one. That is right for rolls shorter than the track and wrong as soon as a roll is longer: a token on cell 4 of a track of 5 that rolls 11 ends on cell 0 having passed the start three times, and "the cell went down" counts one of those.
## Total distance, then divide once
Keep each token's TOTAL distance travelled rather than its cell. Then:
laps = total / n integer division
cell = total mod n
One division at the end, nothing to get wrong per roll, and arbitrarily long rolls handled for free.
## Why that is the same thing
Define the token's position after travelling total cells as the cell it sits
on, and a lap as an arrival at cell 0. Advancing one cell at a time from cell 0,
the cell after t single steps is t mod n, since the sequence of cells is
0, 1, ..., n - 1, 0, 1, ..., which is exactly the remainder cycle. An arrival
at cell 0 happens precisely at those t that are positive multiples of n, and
the number of positive multiples of n that are at most total is
total / n rounded down. So laps and cell are the quotient and the remainder of
the same division, and the step-by-step count agrees with it. That equivalence
is what the two implementations verifying this problem check, one walking
single cells and one subtracting whole laps in doubling chunks, neither using
the division operator.
## Overflow
A roll reaches 10^9 and there are up to 50000 rolls, so one token can
travel as far as 5 * 10^13 cells. The signed 32 bit limit is 2147483647, so
the running total must be held in a 64 bit type; 5 * 10^13 is comfortably
inside signed 64 bit, which reaches about 9.2 * 10^18. In JavaScript a plain
Number is exact below 2^53, which is about 9.007 * 10^15, so 5 * 10^13
is exact as a Number and no BigInt is needed; what must be avoided there is
any bitwise operator on the total, since those truncate to 32 bits.
A declared test sends one token three rolls of 10^9, a total of exactly
3 * 10^9. A 32 bit accumulator wraps that to -1294967296 and reports
-129496729 laps on cell -6 instead of 300000000 laps on cell 0.
## Order is part of the answer
The three-key ordering is stated because any other reading gives a different set of lines, and a program cannot guess it. Note the middle key runs the other way from the last: higher cell beats lower, then LOWER token number beats higher.
## Cost
O(k) to accumulate and O(p log p) to sort, so O(k + p log p), with
O(p) memory.