All Falls Somewhere

For fixed distinct vertices $a$ and $b$, consider Alice's score minus Bob's score. A piece ending at $a$ contributes $+1$, a piece ending at $b$ contributes $-1$, and every other piece contributes $0$.

Let $f_{a,b}(i)$ be the final contribution of one piece currently on vertex $i$. Suppose it is moved to a neighbor $j$ on turn $i$.

• If $j<i$, turn $j$ has already passed. The contribution is $+1$ if $j=a$, $-1$ if , and otherwise.

For odd $i$, Alice chooses the maximum available value. For even $i$, Bob chooses the minimum. Thus these values can be computed from $N$ down to $1$.

This argument does not assume that pieces on one vertex can be moved separately. If $c$ pieces have gathered on vertex $i$, the part of the score difference affected by the chosen neighbor is multiplied by $c$. We always have $c>0$, and the contributions of pieces on other unprocessed vertices are unaffected. Therefore, the maximizing or minimizing neighbor is independent of $c$, and the contribution can be applied linearly to every piece.

Running this DP separately for all pairs $(a,b)$ would be too slow. We use the fact that every contribution is one of $-1,0,+1$.

Let $P_a(i)$ indicate whether $f_{a,b}(i)=+1$. Choosing neighbor produces if when , or if is true when . Therefore:

• for odd $i$, $P_a(i)$ is true if at least one neighbor satisfies the condition;
• for even $i$, $P_a(i)$ is true if every neighbor satisfies the condition.

This recurrence does not contain $b$. Hence the number of pieces contributing $+1$,

$$X_a=\sum_{i=1}^{N}[P_a(i)],$$

depends only on $a$.

Similarly, let $Q_b(i)$ indicate whether $f_{a,b}(i)=-1$. At an odd vertex every neighbor must produce , while at an even vertex one such neighbor is enough. This recurrence does not contain , so

$$Y_b=\sum_{i=1}^{N}[Q_b(i)]$$

depends only on $b$.

The score difference after optimal play for pair $(a,b)$ is exactly $X_a-Y_b$. Compute $$ and by scanning the vertices in decreasing order for every target vertex.

Finally, sort all values $Y_b$. For each $a$, use binary search to count values satisfying $Y_b<X_a$, and subtract one if the counted choices include .

The total time complexity is $O(N(N+M)+N\log N)$. Since a connected graph has $M\geq N-1$, this can also be written as . The space complexity is .

Solution written by GPT6