Greta's Game

Reframe The Game

In one round, participant $i$ and participant $i+1$ both get a point exactly when the directed edge

$(i,i+1)$

“fires”, meaning the chosen numbers satisfy $x_i>x_{i+1}$.

So forget the actual numbers for a second. What sets of edges can fire in one round?

The only impossible set is all edges. If all edges fired, we would need

$x_1>x_2>\cdots>x_n>x_1,$

which is a strict cycle, aka mathematical clownery.

Every proper subset is possible. For example, assign numbers while walking around the cycle; as long as at least one edge is not strict, there is no strict contradiction around the whole loop.

So each round is just: choose any subset of edges except the full set.

Edge Counts

Let $b_i$ be the number of rounds in which edge $(i,i+1)$ fires.

Participant $i$ receives points from exactly two adjacent edges:

• edge $(i-1,i)$,
• edge $(i,i+1)$.

Therefore the final scores satisfy

$a_i=b_{i-1}+b_i.$

Indices are cyclic, so $b_0=b_n$.

Now the problem is split into two parts:

1. Find valid nonnegative integer edge counts $b_i$ satisfying $b_{i-1}+b_i=a_i$.
2. Given those $b_i$, compute the minimum number of rounds $R$ needed.

When Do Edge Counts Fit Into $R$ Rounds?

Suppose we already have edge counts $b_i$.

Clearly each edge can fire at most once per round, so

$b_i\le R$

for every $i$.

Also, every round must leave at least one edge unfired, because the full set of edges is impossible. Across $R$ rounds, there are $nR$ total edge-slots, and edge $i$ is used $b_i$ times. So the number of unused slots is

$nR-\sum b_i.$

We need at least one unused slot in each round:

$nR-\sum b_i\ge R,$

which is equivalent to

$\sum b_i\le (n-1)R.$

These conditions are also sufficient. Think of the unused slots as zeros in an $R\times n$ binary table. Column $i$ needs $R-b_i$ zeros, and each row needs at least one zero. Since no column needs negative zeros and the total number of zeros is at least $R$, we can place one zero in each row first, then dump the rest wherever capacity remains. Done.

So for fixed $b$, the answer is

$R=\max\left(\max_i b_i,\left\lceil\frac{\sum_i b_i}{n-1}\right\rceil\right).$

Solving $b_{i-1}+b_i=a_i$

The cyclic equations are linear:

$b_{i-1}+b_i=a_i.$

From $b_n=x$, everything else is forced:

$b_1=a_1-x,$ $b_2=a_2-b_1=a_2-a_1+x,$ $b_3=a_3-b_2=a_3-a_2+a_1-x,$

and so on. Each $b_i$ is either $x+c_i$ or $c_i-x$.

Now parity matters.

Odd $n$

After walking all the way around, the final equation determines $x$ uniquely. So there is exactly one solution.

A clean way to compute it:

Set $b_n=0$ temporarily and generate $b_1,\dots,b_{n-1}$ using

$b_i=a_i-b_{i-1}.$

Then the last equation says

$b_{n-1}+b_n=a_n.$

For odd $n$, changing $b_n$ by $x$ changes $b_{n-1}$ by $x$, so the left side changes by $2x$. Thus

$x=\frac{a_n-b_{n-1}}{2}.$

The statement guarantees the scores are achievable, so this is an integer and all resulting $b_i$ are nonnegative.

Then compute the formula for $R$.

Even $n$

For even $n$, either there are no solutions or infinitely many integer solutions along one parameter. The statement guarantees at least one solution, so we only need optimize.

Again write each edge count as a function of $x=b_n$:

• odd-indexed $b_i$ have form $c_i-x$,
• even-indexed $b_i$ have form $c_i+x$,
• and $b_n=x$.

Nonnegativity gives an interval of valid $x$ values:

$L\le x\le U.$

For any valid $x$, the answer is

$f(x)=\max\left(\max_i b_i(x),\left\lceil\frac{\sum_i b_i(x)}{n-1}\right\rceil\right).$

For even $n$, $\sum b_i$ is actually constant, because each score contributes to exactly two edge equations and the alternating degree of freedom just shifts weight between odd and even edges. So the second term is constant.

That leaves minimizing

$\max_i b_i(x).$

This is the maximum of some increasing lines $x+c$ and decreasing lines $c-x$. It is convex over the valid integer interval. The best point is where the biggest increasing requirement and biggest decreasing requirement balance.

Let

$P=\max(c_i \text{ for terms } x+c_i),$

and

$Q=\max(c_i \text{ for terms } c_i-x).$

Then

$\max_i b_i(x)=\max(x+P, Q-x).$

The real-valued optimum is near

$x=\frac{Q-P}{2}.$

Clamp around that point into $[L,U]$ and test a few nearby integers. No need for fancy binary search; the function is tiny and convex. The brute force over five candidates is the least dramatic thing here, which is exactly what we want.

Complexity

For each test case we do one or two linear passes over the array.

$O(n)$

per test case, and

$O\left(\sum n\right)$

over the whole input. Memory is $O(n)$ if storing the temporary coefficients, or $O(1)$ aside from the input. Fast enough; 2400 rating, but no need to summon eldritch data structures.