Production of Snowmen

We need count triples $(i,j,k)$ such that all $n$ produced snowmen satisfy

$a < b < c.$

At first glance this smells like $O(n^3)$: pick starts on all three conveyors and simulate. That is obviously dead. $n=5000$ means $n^3$ is a brick wall, not a challenge.

The trick is to stop caring about the absolute starting indices and care about relative shifts.

Relative Shifts

Suppose we pick starts $(i,j,k)$. During production, snowman number $s$ uses

$a_{i+s},\quad b_{j+s},\quad c_{k+s}$

with indices taken cyclically.

Define

$x = j-i \pmod n$

as the shift from conveyor $A$ to conveyor $B$.

Then whenever conveyor $A$ is at position $p$, conveyor $B$ is at position $p+x$. So the first inequality for all snowmen is exactly:

$a_p < b_{p+x} \quad \text{for every } p \in [0,n-1].$

That means a shift $x$ is either valid for the whole $A \to B$ comparison, or it is not.

Now define

$y = k-j \pmod n$

as the shift from conveyor $B$ to conveyor $C$.

The second inequality becomes:

$b_q < c_{q+y} \quad \text{for every } q \in [0,n-1].$

And here is the whole problem cracking open: this condition depends only on $y$, not on $x$ or $i$.

So the two parts are independent:

• count valid shifts $x$ where $A$ is pointwise smaller than shifted $B$;
• count valid shifts $y$ where $B$ is pointwise smaller than shifted $C$.

Let those counts be $X$ and $Y$.

Why Multiply by $n$?

For every valid pair $(x,y)$, we can choose any starting position $i$ on conveyor $A$.

Then $j$ is forced by

$j = i+x \pmod n,$

and $k$ is forced by

$k = j+y \pmod n.$

There are exactly $n$ choices for $i$, so each valid pair of shifts contributes $n$ triples.

Therefore:

$\text{answer} = n \cdot X \cdot Y.$

That’s it. The factory looked complicated, but it was just two cyclic shift checks in a trench coat.

Computing Valid Shifts

To count valid shifts from array $u$ to array $v$, test every shift $s$ from $0$ to $n-1$:

$u_i < v_{(i+s) \bmod n} \quad \forall i.$

If all comparisons pass, this shift is valid.

This is $O(n^2)$ per pair of conveyors. We do it twice, so total complexity is:

$O(n^2)$

per test case. Since the sum of all $n$ is at most $5000$, this is totally fine.

Correctness Proof

We prove the algorithm outputs the number of valid triples $(i,j,k)$.

Consider any triple $(i,j,k)$. Let

$x = j-i \pmod n, \qquad y = k-j \pmod n.$

For every produced snowman, if the $A$ index is $p$, then the $B$ index is $p+x$. Thus all first inequalities $a<b$ hold if and only if

$a_p < b_{p+x}$

for every position $p$. Therefore $x$ must be one of the valid $A \to B$ shifts counted by the algorithm.

Similarly, if the $B$ index is $q$, then the $C$ index is $q+y$. Hence all second inequalities $b<c$ hold if and only if

$b_q < c_{q+y}$

for every position $q$. Therefore $y$ must be one of the valid $B \to C$ shifts counted by the algorithm.

So every valid triple corresponds to one choice of:

• a valid shift $x$,
• a valid shift $y$,
• a starting index $i$.

Conversely, take any valid $x$, valid $y$, and any starting index $i$. Set $j=i+x$ cyclically and $k=j+y$ cyclically. By validity of $x$, every produced snowman satisfies $a<b$. By validity of $y$, every produced snowman satisfies $b<c$. Therefore every snowman is stable.

This correspondence is one-to-one: $(i,x,y)$ uniquely determines $(i,j,k)$, and $(i,j,k)$ uniquely determines $(i,x,y)$.

There are $n$ choices for $i$, $X$ choices for $x$, and $Y$ choices for $y$, so the answer is

$nXY.$

Thus the algorithm is correct.