A Diagonal Folded in a Box
A single point moves inside an r by c box, on the cells with rows 0 to
r - 1 and columns 0 to c - 1. It starts at (i, j) and moves
diagonally: every tick it changes its row by di and its column by dj, where
each of di and dj is 1 or -1.
The walls reflect, and each axis reflects on its own. One tick, in order:
if the row would leave the box, di flips sign first
if the column would leave the box, dj flips sign first
then the row changes by di and the column changes by dj
After exactly t ticks, print the row and the column, separated by a single
space.
``` r = 3, c = 3, start (0,0), direction (1,1), t = 4
ticks: (1,1), (2,2), then both axes reflect, giving (1,1), (0,0) -> 0 0 ```
r = 3, c = 4, start (2,3), direction (-1,-1), t = 10^18 -> 2 1
## What most people try first
Stepping the ticks. t runs to 10^18, so that is out, and the second worked
example is the one that says so.
The next instinct is to notice the whole thing repeats and look for the period
of the pair. That works, but it is more than the problem needs, because the two
axes do not interact at all: the rule flips di using only the row, and dj
using only the column. So the row after t ticks depends on i, di, t and
r, and nothing else. Solve the two axes separately and print both.
## One axis, folded
A point bouncing between 0 and m with unit steps traces a triangle wave:
0, 1, ..., m, m-1, ..., 1, 0, 1, ..., which has period 2m. The axis of a box
with r rows runs from 0 to r - 1, so its m is r - 1, and likewise the
column axis has m = c - 1.
Unroll the walls. With no walls the coordinate after t ticks would be
u = i + di * t. Folding that back in is one modulo:
m = r - 1
f = u mod 2m, taken non-negative
row = f if f <= m
2m - f otherwise
## Why the fold is the same as the reflection rule
Let g(x) be the folded value of an unrolled coordinate x. The sequence
g(0), g(1), g(2), ... is 0, 1, ..., m, m-1, ..., 1, 0, 1, ... by the
definition above. Walking that sequence one entry at a time changes the value by
exactly +1 while climbing and -1 while descending, and it turns around
exactly at 0 and at m, which is where the statement says the direction
flips. So stepping the unrolled coordinate by one and folding gives the same
move as applying the rule, and by induction over t the two agree for every
t.
This also explains why the direction never has to be tracked: it is recoverable
from where u sits in its period, and the question does not ask for it.
## The boundary that breaks a careless implementation
r and c are at least 2, so m is at least 1 and the modulus 2m is never
zero. A box one cell wide would be a different problem, since a point there
cannot move along that axis at all, and the constraints rule it out rather than
leaving it unsettled.
t may be 0, in which case the answer is the start.
## Overflow
u = i + di * t reaches 10^18 in magnitude. That is far outside a signed 32
bit integer, whose top is 2147483647, so u and the modulus must be 64 bit.
A declared test uses 10^18 ticks for exactly this reason.
Watch the sign of the remainder. In C, C++, Java and JavaScript, % keeps the
sign of the left operand, so -1 % 6 is -1 and not 5. A negative direction
makes u negative, so add 2m back when the remainder comes out below zero.
## Cost
O(1) time and O(1) memory, with no dependence on t, r or c.