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

Frogs

Back to problem

Editorial

Let B=XNB=X_NB=XN​. For i<Ni<Ni<N, define Gi=gcd⁡(∣Xi+1−B∣,…,∣XN−B∣)G_i=\gcd(|X_{i+1}-B|,\ldots,|X_N-B|)Gi​=gcd(∣Xi+1​−B∣,…,∣XN, and set GN=0G_N=0GN​=0 for convenience. Since all initial coordinates are distinct, GN−1=0G_{N-1}=0GN−1​=0, while Gi>0G_i>0Gi​>0 for i≤N−2i\le N-2i≤N−2.

Let SiS_iSi​ be the set of coordinates reachable by frog iii. Then SN={B}S_N=\{B\}SN​=. If , then . If , then is the set of all integers satisfying or . Moreover, every choice of pairwise distinct coordinates can be realized.

Proof of the reachable sets

Translate all coordinates by −B-B−B, placing frog NNN at 000. The greatest common divisor of the coordinates of the frogs with indices greater than iii is initially GiG_iG and remains invariant, because replacing by preserves . Every center of a jump by frog is therefore a multiple of , so a jump can only negate its coordinate modulo . This proves necessity.

The reachable sets have a strong nesting property. If i<ji<ji<j, then either Si∩Sj=∅S_i\cap S_j=\varnothingSi​∩Sj​ or .

Proof of laminarity

For i<ji<ji<j, we have Gi∣GjG_i\mid G_jGi​∣Gj​, and is also a multiple of . Suppose the two sets intersect. Reducing the two residues and of modulo gives the two residues and of . Since , every coordinate of belongs to . The finite case and the singleton follow identically.

Process the frogs in the order N,N−1,…,1N,N-1,\ldots,1N,N−1,…,1. Place each frog at a coordinate of its reachable set that is not already used and has minimum absolute value. This greedy algorithm is optimal.

Proof of the greedy algorithm

Take an optimal assignment that already agrees with the greedy choices for all greater indices. For the current frog iii, let xxx be the greedy coordinate and let yyy be its coordinate in the optimal assignment. The coordinate yyy is not used by any greater index, so ∣x∣≤∣y∣|x|\le|y|∣x.

It remains to find the closest unused coordinate of each SiS_iSi​. When Gi>0G_i>0Gi​>0, let m=2Gim=2G_i and normalize a residue to . Its coordinates form the nonnegative stream and the negative stream . When , the negative stream starts at .

​
−
B∣)
{
B
}
Gi=0G_i=0Gi​=0
Si={Xi,2B−Xi}S_i=\{X_i,2B-X_i\}Si​={Xi​,2B−Xi​}
Gi>0G_i>0Gi​>0
SiS_iSi​
xxx
x≡Xi(mod2Gi)x\equiv X_i\pmod {2G_i}x≡Xi​(mod2Gi​)
x≡2B−Xi(mod2Gi)x\equiv2B-X_i\pmod {2G_i}x≡2B−Xi​(mod2Gi​)
Yi∈SiY_i\in S_iYi​∈Si​
i
​
uuu
2v−u2v-u2v−u
gcd⁡(u,v,…)\gcd(u,v,\ldots)gcd(u,v,…)
iii
GiG_iGi​
2Gi2G_i2Gi​

For the converse, freeze all frogs with greater indices at a finite set CCC and move only one frog. We have 0∈C0\in C0∈C; let d=gcd⁡{∣c∣:c∈C}d=\gcd\{|c|:c\in C\}d=gcd{∣c∣:c∈C}. Write reflection about ccc as Rc(y)=2c−yR_c(y)=2c-yRc​(y)=2c−y. The composition RcR0R_cR_0Rc​R0​ translates by 2c2c2c. Bezout's identity therefore produces translation by 2d2d2d, and R0R_0R0​ changes the sign. Ignoring occupied landing points, this generates exactly the residue classes above.

It remains to avoid CCC. If an orbit does not meet CCC, this is immediate. Otherwise, the orbit is one arithmetic progression. Let L=min⁡CL=\min CL=minC and U=max⁡CU=\max CU=maxC. Reflections about LLL and UUU move any allowed orbit point to the right of UUU, and alternating them moves it arbitrarily far away. Fix a finite reflection word that translates by 2d2d2d. Applied sufficiently far away, every intermediate coordinate lies outside CCC. Hence any two unoccupied points in one orbit are connected.

Finally, induct on the number of frogs. A finite sequence that moves frogs 2,…,N2,\ldots,N2,…,N to their targets visits only finitely many coordinates. For N≥3N\ge3N≥3, S1S_1S1​ is infinite, so frog 111 can first be parked outside all of them. Move the other frogs, and then move frog 111 to its target. The cases N=1,2N=1,2N=1,2 are immediate. Thus every tuple of distinct representatives is reachable.

=
∅
Sj⊆SiS_j\subseteq S_iSj​⊆Si​
Xj−BX_j-BXj​−B
GiG_iGi​
Xj−BX_j-BXj​−B
−(Xj−B)-(X_j-B)−(Xj​−B)
SjS_jSj​
2Gi2G_i2Gi​
Xi−BX_i-BXi​−B
−(Xi−B)-(X_i-B)−(Xi​−B)
SiS_iSi​
2Gi∣2Gj2G_i\mid2G_j2Gi​∣2Gj​
SjS_jSj​
SiS_iSi​
Gj=0G_j=0Gj​=0
SNS_NSN​
∣
≤
∣y∣

If xxx is unused in the optimal assignment, assign it to frog iii without increasing the maximum. Otherwise, some frog k<ik<ik<i uses xxx. Since x∈Si∩Skx\in S_i\cap S_kx∈Si​∩Sk​ and k<ik<ik<i, laminarity gives Si⊆SkS_i\subseteq S_kSi​⊆Sk​. Hence y∈Sky\in S_ky∈Sk​, so the coordinates x,yx,yx,y of frogs i,ki,ki,k can be swapped. The set of used coordinates and its maximum absolute value remain unchanged. Repeating this exchange proves that some optimal assignment agrees with every greedy choice.

m
=
2Gi​
rrr
0≤r<m0\le r<m0≤r<m
r,r+m,r+2m,…r,r+m,r+2m,\ldotsr,r+m,r+2m,…
r−m,r−2m,…r-m,r-2m,\ldotsr−m,r−2m,…
r=0r=0r=0
−m-m−m

For every residue under the current modulus, store the first unchecked coordinate in each direction. Store all occupied coordinates in a hash set and advance a pointer while it points to an occupied coordinate. The two residue classes defining SiS_iSi​ yield at most four candidates; choose the best one. When Gi=0G_i=0Gi​=0, simply compare XiX_iXi​ and 2B−Xi2B-X_i2B−Xi​.

While iterating downwards, update Gi=gcd⁡(Gi+1,∣Xi+1−B∣)G_i=\gcd(G_{i+1},|X_{i+1}-B|)Gi​=gcd(Gi+1​,∣Xi+1​−B∣). When the modulus changes, clear only the residue frontiers and keep the occupied-coordinate set. Every change between positive values replaces the gcd by a proper divisor, at most halving it. Thus there are only O(log⁡109)O(\log 10^9)O(log109) different moduli. For one fixed modulus, each occupied coordinate is skipped at most once. The expected time complexity is O(Nlog⁡109)O(N\log 10^9)O(Nlog109) and the memory complexity is O(N)O(N)O(N).

Solution written by GPT5.6