A Torus, and a Product Too Big for 64 Bits
An r by c grid is a torus: walking off the right edge arrives back at column
0, walking off the bottom arrives back at row 0, and likewise in the other two
directions. n particles sit on it. Particle k starts at (i, j), heads in
direction d, which is 0 for north, 1 for east, 2 for south or 3 for
west, and moves sp cells in that direction every tick. North decreases the
row.
Particles do not interact at all. They pass through each other and through the
same cell freely. After exactly t ticks, print two integers: how many cells
hold two or more particles, and the largest number of particles on any single
cell.
``` r = 3, c = 3, t = 1, one particle at (0,0) heading south at speed 1 and one at (2,0) heading north at speed 1
the first goes to (1,0). The second goes from row 2 north to row 1, so (1,0) as well. One cell holds two particles. -> 1 2 ```
``` r = 1, c = 1, t = 5, two particles, any speeds
the torus has a single cell, so both particles are on it whatever they do. -> 1 2 ```
## What most people try first
Computing the distance travelled as sp * t and reducing afterwards. That is
the natural thing to write and it is the trap this problem exists for:
sp reaches 10^9 and t reaches 10^18 so sp * t reaches 10^27
A signed 64 bit integer holds about 9.22 * 10^18. So sp * t does not merely
overflow a 32 bit integer, it overflows a 64 bit one, and in C and C++ that is
undefined behaviour rather than a defined wrap. This is a different situation
from #2139, which walks one robot through a command string on a wrapping grid
and never multiplies anything.
## Reduce before multiplying
The row of a north or south mover changes by sp * t modulo r, and
(sp * t) mod r = ((sp mod r) * (t mod r)) mod r
With r at most 1000, each factor on the right is below 1000 and the product is
below 10^6, which fits anywhere. The same holds for the column with c.
## Why that identity is true
Write sp = a*r + x and t = b*r + y, where x = sp mod r and
y = t mod r. Then
sp * t = (a*r + x)(b*r + y) = a*b*r^2 + a*r*y + b*r*x + x*y
The first three terms are each a multiple of r, so they vanish modulo r, and
sp * t is congruent to x * y modulo r. Reducing x * y modulo r again
gives the same residue as reducing sp * t, which is the identity. Nothing in
the argument needs sp or t to be small, which is exactly the point.
## The sign, which is the other half of the problem
A north mover decreases the row, so its row is i - step where step is the
reduced distance. That can be negative, and in C, C++, Java and JavaScript the
% operator keeps the sign of the left operand, so -1 % 3 is -1 and not
2. The correct form is ((i - step) % r + r) % r. Python's % already
returns a non-negative result for a positive modulus, so a Python solution can
write it in one step and a port of it cannot.
## Counting the crowded cells
Turn each final (row, col) into the single number row * c + col, sort the
n of them, and walk the sorted list counting equal runs. A run of length 2 or
more is a crowded cell, and the longest run is the second answer. That needs no
hash map, which matters in C, and it is O(n log n).
If every cell holds at most one particle the first answer is 0, and the second is 1 whenever there is at least one particle.
## Overflow
Covered above, and it is the point of the problem rather than a footnote.
sp * t reaches 10^27 and must never be formed. The reduced product is below
10^6. The key row * c + col is below 10^6. Two declared tests use a speed
of about 10^9 with t near 10^18 precisely so that a solution forming the
product gives a different answer.
## Cost
O(n log n) time for the sort and O(n) memory, with no dependence on t.