Even If the World Turns — Deon Nicholas

Problem

You are given an $n \times n$ grid where each cell is either $\texttt{.}$ or $\texttt{\#}$ . It is guaranteed that $\gcd(w, n) = 1$ , where $w$ is the number of $\texttt{\#}$ cells. This is a "run-twice" interactive problem: your program plays both roles, and the two players may agree on a strategy beforehand.

Player 1 is given the grid and a target cell $(r_t, c_t)$ , and must communicate the target's location to Player 2. Their only move: swap the colors of any two cells (not necessarily involving the target; the two cells may be the same, making it a no-op). This doesn't move the target cell, though it may change its color.

Then an adversary performs any sequence of operations, in any order, zero or more times each:

Shift all rows down by one (the bottom row wraps to the top).
Shift all columns right by one (the rightmost column wraps to the left).
Rotate the grid clockwise by $90°$ .
Invert all colors.

Under operations 1–3 the target cell moves with the grid; under operation 4 its color flips but it doesn't move.

Player 2 is given the resulting grid and must output where the target cell now is.

Initial Observations

Binary.
$O(n^2)$ is fine, or $O(n^2 \sqrt{n})$ .
Groups / equivalence classes (all boards reachable by the operations are the same "class").
Extended Euclid ( $\gcd(n, w) = 1$ )... why?
[Generate and Test], [Examine Examples], [Work Backward], [Exploit the Constraints] — why $\gcd = 1$ ?
Xor of all the $\texttt{\#}$ 's?
Lexicographically least permutation?
Find an invariant?

IdeaSimplify and vary: one #, then two, then three, on a single row

To be honest, the problem initially seemed intractable. I didn't think it was possible to deduce the exact target in all cases. But it was clear that the first player, through their single swap, would have to encode information about the target cell's position somehow.

Examine Examples

To get a feel for the problem — because my brain wasn't really getting it yet — I immediately looked at Sample Case 1: $n = 5$ , target cell $(3, 4)$ :

# . . . .
. # . . .
. . . . .      target (3,4)
. . . . .
. . . . .

In the sample, Player 1 chooses to move the $\texttt{\#}$ at $(1,1)$ to $(4,1)$ . Why?

From here on, treat $\texttt{\#}$ as $1$ and $\texttt{.}$ as $0$ — the board is a binary matrix:

1 0 0 0 0
0 1 0 0 0
0 0 0 0 0      same board, as bits
0 0 0 0 0
0 0 0 0 0

One question: is there a way to encode the target's position in the binary representation of where the $1$ 's are? Treat each row and column as a binary number, or something? That didn't really lead anywhere yet, but it was giving me a feel for the problem.

Key Question

If you are given the exact same board but a different target cell, how would Player 1's move have to differ to convey the right information?

Observation.

There are $n^2$ possible targets, so the boards Player 1 can produce must land in $n^2$ distinguishable "equivalence classes" — where two boards are equivalent if the adversary's operations can turn one into the other. Whatever we encode has to be invariant under those operations.

Draw from Experience

Two lessons from upsolving Problem D of this same round came straight into play here. First: be strategic about how I examine examples — not just a representative one, but small variations of it, to learn how the boundary of the problem behaves. Second: the moment an idea involves characterizing something, write the question down EXACTLY and answer it, instead of letting it float. The Key Questions above and below are the direct product of trying that consciously.

Generate and Test

I figured the parity of the rows and columns (xor of the bits) might be useful, so I wrote a bit next to each row and column of the sample:

   1 0 0 0 0    row: 1
   0 1 0 0 0    row: 1
   0 0 0 0 0    row: 0      target (3,4)
   0 0 0 0 0    row: 0
   0 0 0 0 0    row: 0
 
   1 1 0 0 0    <- column parities

Then I started applying adversary operations — row shifts, column shifts, rotations, color flips — to see how the parities move. It didn't really pan out, but interesting.

The next breakthrough came from the "vary small examples to understand the boundaries" idea. I decided to play with very small cases.

Problem Simplification

What if the board has EXACTLY one $1$ ? Again it seems like it should be completely intractable — nowhere near enough information — but let's play with it.

Key Observation

With exactly one $1$ on the board and target $(r_t, c_t)$ , Player 1 can simply swap the $1$ into the target cell:

. . . . .        . . . . .
. 1 . . .        . . . . .
. . . . .   ->   . . . 1 .      (the single 1 now sits ON the target)
. . . . .        . . . . .
. . . . .        . . . . .

No matter how the adversary shifts or rotates, the single $1$ rides along with the target cell — they move together. If the adversary inverts colors, everything else becomes $1$ and the target becomes the lone $0$ . Either way there's a smoking gun.

That gave me an idea about the flips too.

Problem Simplification

Let's ignore the color flips for now, and just focus on the other operations. (I think...?) If there are more $1$ 's than $0$ 's on Player 1's board, Player 1 can just work with the $0$ 's — whichever color appears least. There's never a tie, because $\gcd(w, n) = 1$ makes $w = n^2/2$ impossible. So Player 2 can always assume Player 1 was focused on whichever color appears least, and this survives color swaps. (Admittedly this is kind of a long-winded / not-so-rigorous argument, but it seemed correct enough that I parked the color flips and assumed we're placing $1$ 's from here.)

OK, we are making real progress now, it seems. So if $w = 1$ , place the $1$ on the target and we're good, for any target.

What if $w = 2$ (just varying the example a bit)? We can't place both of them in the target cell.

Problem Simplification

Another temporary simplification: a $1 \times 5$ board instead of $5 \times 5$ — both $1$ 's in the same row. Now what?

What if we can "pinpoint" the target with the two $1$ 's — always place them around it? For example, with target $(1,2)$ , move the second $1$ one unit left:

1 0 0 1 0      target (1,2)
    <--
1 0 1 0 0      the target sits squeezed between the two 1's

No matter what transformations are done (excluding color swaps), the target stays squeezed between the two $1$ 's.

Observation.

With $w = 2$ , at least on a single-row board, we can always place the two $1$ 's so that the target cell is their mean.

The hard part — and one I spent some time on — is that the board is cyclic; we are playing modulo $n$ . What exactly is the "mean" of the two $1$ 's here?

column:  1 2 3 4 5
board:   1 1 0 0 0      directly between them is a half-cell...

But go the other way around: they're $4$ apart with wrap-around, and the true halfway point is cell $(1,4)$ — exactly two to the left of the first $1$ (wrapping) and two to the right of the second.

Write It Out

Let's write the "mean" of two items out clearly before moving on. For $1$ 's at columns $a$ and $b$ , the mean should be a cell $x$ equidistant from both (wrapping allowed): $x - a \equiv b - x \pmod n$ , i.e. $2x \equiv a + b \pmod n$ . That's just the normal mean $(a+b)/2$ — except the division by $2$ happens mod $n$ , by multiplying by $2^{-1}$ :

x \equiv (a + b) \cdot 2^{-1} \pmod n .

In the example: $2x \equiv 1 + 2 = 3 \pmod 5$ , and $x = 4$ works ( $2 \cdot 4 = 8 \equiv 3$ ).

So there might still be a well-defined "mean" in a cyclic space. I guess this works as long as $n$ is odd, so that $2^{-1}$ exists? (At least with $w = 2$ here.)

Let's try $w = 3$ , on a bigger single row, $1 \times 11$ :

1 0 0 1 0 0 0 0 0 0 1

Here I really needed to vary the examples carefully — what if the target is $(1,1)$ , or $(1,2)$ , and so on. Should I still take a "mean" of sorts?

After working it through: yes, it really does work, if you're very careful about defining the mean in a cyclic space. First, a quick transformation:

Problem Transformation

We're clearly going to be operating mod $n$ , so switch to $0$ -indexed cells: $(0,0)$ through $(n-1, n-1)$ .

Key Observation

With $w$ ones at positions $c_1, \ldots, c_w$ (single-row board), there is a unique cell that is their mean: $(c_1 + \cdots + c_w) \cdot w^{-1} \pmod n$ . We can avoid division entirely because $\gcd(w, n) = 1$ (!!!!) — from the constraints — so $w$ has a modular inverse $w^{-1}$ mod $n$ . The encoding is: Player 1 arranges the $1$ 's so that

(c_1 + c_2 + \cdots + c_w) \cdot w^{-1} \equiv c_t \pmod n .

This is really beautiful and uniquely defined. And if you play around with examples, you'll notice the mean stays "tucked in" as the adversary acts: shift every cell by one and both the target and the mean shift by one — still matched. (The same check works for rotations: the mean rotates along with the board.) The second player can always recover the target after any sequence of adversarial operations.

Key Question

Given an initial configuration of $w$ ones and a target $c_t$ , can Player 1 always move one cell to make the mean come out to exactly $c_t$ ?

Observation.

Shifting any single $1$ one cell over changes the total sum by $1 \pmod n$ ; do it repeatedly and the sum moves by any amount you like. So we can steer the sum to $w \cdot c_t \pmod n$ , and multiplying by $w^{-1}$ gives exactly $c_t$ . (Made rigorous on the full board below.)

Problem Generalization

We're making a ton of progress — but let's hope this still works on an $n \times n$ board, and we haven't addressed what happens when the spot you want to move a $1$ into already holds a $1$ . Good time to break for a fresh Idea.

IdeaGeneralizing to the full boardAC

From Idea 1: on a 1D board, the right thing to encode with is the mean of the $1$ -positions (Key Observation 2). To quickly recreate the idea, since Idea 1 was a long road: the mean has the two properties we need. It moves with the board — shift every cell one to the right and every position goes up by $1$ , so the mean does too, exactly like the target (and similarly for rotations). And Player 1 can steer it — moving a single $1$ by one cell changes the sum of the positions by $1$ , so a single move can set the sum, and hence the mean, to anything mod $n$ . Uniqueness of the mean comes from $\gcd(w, n) = 1$ . For example, with $w = 2$ on a $1 \times 11$ row ( $0$ -indexed):

1 0 0 0 0 0 1 0 0 0 0      sum = 0 + 6 = 6,   mean = 6 * 2^(-1) = 3  (mod 11)
0 1 0 0 0 0 0 1 0 0 0      sum = 1 + 7 = 8,   mean = 8 * 2^(-1) = 4  (mod 11)

After a shift right, the mean moved right along with the board — and with the target. So Player 1 can (generally speaking) move one of the $w$ ones so that their mean lands exactly on the target. Now generalize to $n \times n$ and handle the edge cases.

Key Observation

Handle the row-coordinates and column-coordinates separately. With ones at $(r_1, c_1), \ldots, (r_w, c_w)$ , let $S_r = \sum r_i$ and $S_c = \sum c_i$ . We want the mean $(S_r \cdot w^{-1},\ S_c \cdot w^{-1})$ to equal $(r_t, c_t)$ — equivalently, we want the sums to become $w \cdot r_t$ and $w \cdot c_t$ . So define

\Delta_r = w \cdot r_t - S_r \pmod n, \qquad \Delta_c = w \cdot c_t - S_c \pmod n .

Moving a single $1$ from $(r, c)$ to $(r + \Delta_r,\ c + \Delta_c)$ changes $S_r$ by exactly $\Delta_r$ and $S_c$ by exactly $\Delta_c$ — which lands the mean exactly on the target.

Write It Out

The modular arithmetic here is straightforward but not entirely trivial — get the details exactly right (in particular: the deltas live on the sums, not the averages).

What's nice is that this works for any $1$ we choose to move. So:

Key Question

Can we ALWAYS find at least one $1$ that we can move this way? When doesn't it work? We need a $1$ -cell $(r, c)$ such that $(r + \Delta_r,\ c + \Delta_c)$ is a $0$ — so the failure case is: every $1$ -cell has another $1$ exactly $(\Delta_r, \Delta_c)$ away.

Generate and Test

At this point I had a strong hunch it was always possible. In contest I would probably recommend just submitting here — but I wanted to prove it to myself.

Lemma.

For any fixed $(\Delta_r, \Delta_c) \neq (0, 0)$ , there exists a $1$ -cell $(r, c)$ such that $(r + \Delta_r,\ c + \Delta_c)$ is a $0$ -cell.

Proof.

Suppose by contradiction that every $1$ -cell has a $1$ at position $(r + \Delta_r,\ c + \Delta_c)$ . Then keep "hopping" by $(\Delta_r, \Delta_c)$ : starting from any $1$ -cell, the cells $(r, c),\ (r + \Delta_r, c + \Delta_c),\ (r + 2\Delta_r, c + 2\Delta_c), \ldots$ are all $1$ 's, and since the board is finite this "orbit" (the trajectory of cells the hopping visits) must eventually return to its start: $(r + k\Delta_r,\ c + k\Delta_c) = (r, c)$ for the minimal $k > 0$ with

k \cdot \Delta_r \equiv 0 \pmod n \quad\text{and}\quad k \cdot \Delta_c \equiv 0 \pmod n .

For example, on a $6 \times 6$ board with $(\Delta_r, \Delta_c) = (2, 2)$ , three $1$ 's hopping to each other:

1 . . . . .
. . . . . .
. . 1 . . .      hopping by (Δr, Δc) = (2, 2):
. . . . . .
. . . . 1 .      (0,0) -> (2,2) -> (4,4) -> (6,6) ≡ (0,0)
. . . . . .                        ...wraps back to the start

Here the orbit has size $k = 3$ .

This $k$ is the same for every starting cell, so the hopping partitions all the $1$ -cells into "orbits" of size exactly $k$ — hence $k \mid w$ . (The bar is number-theory shorthand: $k \mid w$ reads " $k$ divides $w$ ".)

But $k$ also divides $n$ : taking $k' = n$ satisfies both congruences (everything vanishes mod $n$ ), and the minimal such $k$ divides any other, so $k \mid n$ .

And $k > 1$ , because $k = 1$ would mean $\Delta_r \equiv \Delta_c \equiv 0$ , contradicting $(\Delta_r, \Delta_c) \neq (0,0)$ .

So $k > 1$ divides both $w$ and $n$ — contradicting $\gcd(w, n) = 1$ . Therefore some movable $1$ exists.

∎

So this is beautiful, and there's always a valid move. (If $\Delta_r = \Delta_c = 0$ , the mean is already on the target — Player 1 swaps a cell with itself, which the statement allows.)

Draw from Experience

An aside: the hopping argument was a fun use of some math from my number theory class — it reminded me of the Orbit-Stabilizer Theorem, which I completely forget now (and I haven't gone back to check whether that's even the right theorem to cite). What I actually remembered is the picture: take a group element $g$ and keep exponentiating it — $g^1, g^2, g^3, \ldots$ — and the cycle length always comes out to a factor of the group's size, which I always found magical / tricky. That general idea — cycles in a finite structure must break down as factors of it — is the same shape as the orbits of size $k$ dividing $w$ and $n$ above.

One last thing to come back to: the color flips. Everything so far says "the mean of the $1$ 's is the target" — but the adversary can invert all the colors, and then Player 2 is looking at the complement board: every $1$ that Player 1 placed is now a $0$ . To write out the little detail: every one of the $n^2$ cells gets its color inverted, so the count of $1$ 's goes from $w$ to $n^2 - w$ . The players can't communicate after the game starts, so they need to agree beforehand on which cells count as "the $1$ 's", in a way both of them compute identically no matter what the adversary did.

Back in Idea 1 I had hand-waved this: work with whichever color appears least. In contest that just sat well — it felt like some argument of this shape had to work — but it's not an obvious conclusion, so let's spell it out. The rule the players agree on: the " $1$ 's" are the minority color, whichever of $\texttt{\#}$ / $\texttt{.}$ appears fewer times on the board in front of you. The picture to have in mind is that inverting the colors changes which color is rare, but not which cells are rare:

1 0 0 0 0      0 1 1 1 1
0 1 0 0 0      1 0 1 1 1
0 0 0 0 0  ->  1 1 1 1 1      inverted: the two rare cells are
0 0 0 0 0      1 1 1 1 1      still the same two cells
0 0 0 0 0      1 1 1 1 1

Key Observation

Both players work with the positions of the minority color, and this rule is consistent:

"Minority" is always well-defined, because a tie is impossible: $w = n^2/2$ would make $w$ a multiple of $n$ (and note $n$ would have to be even for $n^2/2$ to even be an integer), contradicting $\gcd(w, n) = 1$ .
An inversion swaps which color is the rare one, but the rare cells are the same physical cells — see the diagram. Shifts and rotations don't change the counts at all; they just move the cells, and the mean moves along with them. So the positions Player 2 extracts are exactly the (transformed) positions Player 1 encoded with.
The mean machinery survives the canonicalization: if the minority color has $n^2 - w$ cells rather than $w$ , its modular inverse still exists, since $\gcd(n^2 - w,\ n) = \gcd(w, n) = 1$ (because $n^2 \equiv 0 \pmod n$ ).

At this point we're ready to write up the algorithm.

Algorithm

PLAYER 1  (given n, target (r_t, c_t), board):
  0. Zero-index everything: r_t -= 1, c_t -= 1. Cells are (0..n-1, 0..n-1).
  1. Canonicalize: assign 1 to every cell of the minority color ('#' or '.',
     whichever appears fewer times), 0 to every other cell.
     w = number of 1's.
  2. S_r = (sum of r over all 1-cells) mod n
     S_c = (sum of c over all 1-cells) mod n
  3. delta_r = (w * r_t - S_r) mod n         // deltas live on the SUMS,
     delta_c = (w * c_t - S_c) mod n         // and keep mods non-negative
  4. If delta_r = delta_c = 0: swap any cell with itself, output it. Done.
  5. Else scan the 1-cells for an (r, c) with a 0 at
     ((r + delta_r) mod n, (c + delta_c) mod n)        -- exists by Lemma 1
  6. Swap the colors of those two cells; output them, back in 1-indexing.
 
PLAYER 2  (given n and the transformed board):
  0. Zero-index; canonicalize the SAME way: 1's = minority color, w = count.
  1. S_r = (sum of r over all 1-cells) mod n;  S_c likewise.
  2. w_inv = w^{-1} mod n                     // extended Euclid: n is not
                                             // necessarily prime, but
                                             // gcd(w, n) = 1 so it exists
  3. Output ( (S_r * w_inv) mod n , (S_c * w_inv) mod n ), back in 1-indexing.

The modular mean rides along with every adversary operation, so this recovers the target's current position regardless of what the adversary did.

ACCEPTED

Review

Player 1 uses their single swap to place the mean of the $\texttt{\#}$ positions — computed mod $n$ — exactly on the target cell. That mean moves together with the board under all four adversary operations, so Player 2 recomputes it and reads off the target. The path:

First try a board with just one $\texttt{\#}$ . Player 1 can swap it right onto the target cell. Every shift and rotation moves the $\texttt{\#}$ and the target together, so Player 2 simply points at the lone $\texttt{\#}$ . [1]
Write down the positions. $0$ -index the board and let $(r_1, c_1), \ldots, (r_w, c_w)$ be the cells containing a $\texttt{\#}$ ; all arithmetic below is mod $n$ .
Then generalize to $w$ $\texttt{\#}$ 's by taking their mean. The goal is to arrange the $\texttt{\#}$ 's so that the average of their positions is the target: $\frac{c_1 + \cdots + c_w}{w} \equiv c_t \pmod n$ , and likewise for rows. Division by $w$ here means multiplying by $w^{-1}$ mod $n$ , which exists because $\gcd(w, n) = 1$ . Like the single $\texttt{\#}$ , this mean shifts and rotates together with the board. [2]
Land the mean on the target with one swap, by working on sums. Let $S_r = r_1 + \cdots + r_w$ and $S_c = c_1 + \cdots + c_w$ be the sums of the $\texttt{\#}$ 's row and column coordinates. Compute $\Delta_r = w \cdot r_t - S_r$ and $\Delta_c = w \cdot c_t - S_c$ (mod $n$ ); moving any single $\texttt{\#}$ by exactly $(\Delta_r, \Delta_c)$ makes the mean equal the target. [3]
Check that some $\texttt{\#}$ can actually make that move. If every $\texttt{\#}$ had another $\texttt{\#}$ exactly $(\Delta_r, \Delta_c)$ away, hopping by $(\Delta_r, \Delta_c)$ would split the $\texttt{\#}$ 's into cycles of one common size $k > 1$ , with $k$ dividing both $w$ and $n$ — impossible, since $\gcd(w, n) = 1$ . So there is always a valid move to make. [Lemma 1]
Last, handle color inversions by canonicalizing. Both players agree that "the $\texttt{\#}$ 's" above really means the cells of whichever color appears fewer times ( $\gcd(w, n) = 1$ rules out a tie). Inverting the colors changes which color is rare, but not which cells are rare — so both players extract the same positions. [4]

References

Problem-solving techniques used:

Examine Examples

Strategically varying my examples was really helpful here: changing the target on the same board, varying $w$ from one $\texttt{\#}$ to two to three, dropping to a single row. This rapidly generated hypotheses — much more than staring at one representative case would have.

Generate and Test

I had some incorrect hypotheses (the row/column parity idea) and a few correct ones. I think I did a good job of deciding when to move on versus when to stop and prove.

Problem Simplification

A smaller board, a single row, a single $\texttt{\#}$ , ignoring the color flips — every simplification paid off.

Problem Transformation

Small ones: $\texttt{\#}/\texttt{.}$ to $1/0$ , and $0$ -indexing to make the mods clean.

Learning points:

I was proud of solving this one. I recently got feedback that I often stall because I don't spend enough time writing down and characterizing things — this problem was a good conscious exercise in actually doing it.
The other recent lesson was to strategically vary examples so they teach me how the boundary of the problem space behaves. Both lessons came out of upsolving Problem D, and I think they're why this one fell.
It still took me 1 hour 25 minutes. I separately need to get faster — but in a contest, this would have been a very good solve for me.

Topics:

Modular arithmetic / modular inverses
Invariants / equivariant encodings
Orbits / group actions
Constructive & interactive problems