1505. Turn Every Ring by k
An R by C grid is given, together with a number k. Turn every ring of the
grid k steps CLOCKWISE, independently of the other rings, and print the
result. A step moves each value to its clockwise neighbour on the same ring.
1 2 3 4 k = 1 5 1 2 3
5 6 7 8 -> 9 7 6 4
9 10 11 12 10 11 12 8
Ring 0 there holds 10 cells and ring 1 holds 2, so one k produces two
different wraps.
1 2 3 4 5 6 k = 2 -> 5 6 1 2 3 4
1 2 k = 3 -> 2 4
3 4 1 3
## What most people try first
Turning by one step, k times. That is correct and it is O(k R C), and k
runs to 10^18. Reducing k once for the whole grid is the next reflex and it
is also wrong: the rings have DIFFERENT lengths, so there is no single modulus.
In the first example, k = 10 leaves ring 0 exactly where it started while
ring 1, of length 2, is unmoved only because 10 is even.
## Read the ring out, write it back shifted
for each ring t:
cells = the ring's positions, clockwise from its top-left
n = len(cells)
vals = the values at those positions
s = k mod n
for i in 0 .. n-1:
grid[cells[(i + s) mod n]] = vals[i]
The remainder is taken PER RING, against that ring's own length.
## Why the write loop needs the values copied first
Writing grid[cells[(i + s) mod n]] = grid[cells[i]] in place overwrites cells
that have not been read yet, unless s happens to be 0. One ring's worth of
values is O(min(R, C)) extra at a time and there is no way around it short of
cycle-following, which for a shift by s means gcd(n, s) separate cycles.
## The degenerate ring, again
A ring that is a single row has n = w cells laid out in a LINE, not a loop of
2(h + w) - 4. Getting n wrong changes the modulus, so every value on that
ring lands in the wrong place. In the 1 by 6 example a wrong n of 10 would
give a shift of 2 mod 10 rather than 2 mod 6, which happens to agree; a k of
8 would not.
## Overflow
k reaches 10^18, far past the 2147483647 a signed 32 bit integer holds,
so it must be read into a 64 bit variable BEFORE the remainder is taken. The
remainder itself is smaller than n and fits anywhere.
## Cost
O(R C) time, since each cell is read and written once, and O(min(R, C))
scratch for the ring currently being rewritten.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `0 ≤ k ≤ 10^18` - `-10^9 ≤ each value ≤ 10^9` - `R` and `C` are independent; the grid need not be square
Input
The first line contains three integers R, C and k.
Each of the next R lines contains C integers.
Output
Print the grid after the turn: R lines of C integers each, separated by single spaces. The shape is unchanged.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.