DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

All Falls Somewhere

Back to problem

Editorial

For fixed distinct vertices aaa and bbb, consider Alice's score minus Bob's score. A piece ending at aaa contributes +1+1+1, a piece ending at bbb contributes −1-1−1, and every other piece contributes 000.

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

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

For odd iii, Alice chooses the maximum available value. For even iii, Bob chooses the minimum. Thus these values can be computed from NNN down to 111.

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

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

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

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

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

Xa=∑i=1N[Pa(i)],X_a=\sum_{i=1}^{N}[P_a(i)],Xa​=i=1∑N​[P

depends only on aaa.

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

Yb=∑i=1N[Qb(i)]Y_b=\sum_{i=1}^{N}[Q_b(i)]Yb​=i=1∑N​[Q

depends only on bbb.

The score difference after optimal play for pair (a,b)(a,b)(a,b) is exactly Xa−YbX_a-Y_bXa​−Yb​. Compute and by scanning the vertices in decreasing order for every target vertex.

Finally, sort all values YbY_bYb​. For each aaa, use binary search to count values satisfying Yb<XaY_b<X_aYb​<, and subtract one if the counted choices include .

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

Solution written by GPT6

−
1
j=bj=bj=b
000
  • If j>ij>ij>i, the piece moves again on turn jjj, so its contribution is fa,b(j)f_{a,b}(j)fa,b​(j).
  • +1
    jjj
    +1+1+1
    j=aj=aj=a
    j<ij<ij<i
    Pa(j)P_a(j)Pa​(j)
    j>ij>ij>i
    a
    ​
    (
    i
    )
    a​
    (
    i
    )]
    ,
    −
    1
    −1-1−1
    aaa
    b​
    (
    i
    )]
    XX
    X
    YYY
    Xa​
    b=ab=ab=a
    1
    O(NM)O(NM)O(NM)
    O(N+M)O(N+M)O(N+M)