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

Candies

Back to problem

Editorial

Let pos⁡x\operatorname{pos}_xposx​ be the initial position of child xxx.

Suppose a child is currently at position ppp and has ccc candies. In one operation, the leftmost chosen child moves two positions to the right and receives one candy, while each of the other two children moves one position to the left and receives one candy. Therefore, for every child, p+c≡pos⁡x(mod3)p+c\equiv \operatorname{pos}_x\pmod3p+c≡posx​(mod3) is invariant.

The three children chosen in an operation have the same number of candies. Hence the residues modulo 333 of their initial positions are all different. Therefore, two children whose initial positions have the same residue modulo 333 can never change their relative order.

In particular, the children initially at positions iii and i+3i+3i+3 must appear in the same relative order in the final arrangement. Since the final arrangement is increasing by child number, Pi<Pi+3P_i<P_{i+3}Pi​<P must hold for every . If this condition fails, the answer is .

Assume from now on that this condition holds.

In the final arrangement, child iii must be at position iii. If this child initially stood at position pos⁡i\operatorname{pos}_iposi​ and ends with HiH_iH candies, the invariant gives .

Now ignore the identities of the children and look only at the number of candies at each position. If three consecutive positions all contain children with hhh candies, one operation changes their values from h,h,hh,h,hh,h,h to h+1,h+1,h+1h+1,h+1,h+1h+1,h+1,h. Thus, an operation can be viewed as placing a horizontal block of length on a bar chart.

Suppose the final candy counts are H1,H2,…,HNH_1,H_2,\ldots,H_NH1​,H2​,…,HN​. For any positive integer , consider the positions satisfying . Every maximal consecutive segment of such positions must have length divisible by , because one layer can only be formed by blocks of length .

This condition is also sufficient. Process the layers from bottom to top. For each layer kkk, split every maximal segment with height at least kkk into blocks of three consecutive positions and perform one operation on each block. Immediately before constructing layer kkk, the three selected positions all have exactly k−1k-1k−1 candies, so every operation is valid.

Therefore, it remains to choose H1,H2,…,HNH_1,H_2,\ldots,H_NH1​,H2​,…,HN​ such that for every , while every layer consists of consecutive segments whose lengths are divisible by . Since every operation increases the total number of candies by exactly , the number of operations is .

Determine the values HiH_iHi​ from left to right. For every height kkk, let SkS_kSk​ be the length modulo 33 of the last currently open consecutive segment on layer .

If Sk≠0S_k\ne0Sk​=0, the current segment on layer kkk has not been completed yet. Therefore, the next position must also have height at least kkk. Let be the largest such that . If no such exists, let .

The next value HiH_iHi​ must be at least MMM, and it must satisfy Hi≡pos⁡i−i(mod3)H_i\equiv \operatorname{pos}_i-i\pmod3Hi. Choose the smallest integer satisfying both conditions.

This greedy choice is optimal. Choosing a value below MMM is impossible because it would terminate an unfinished segment. Any larger value with the same residue differs by at least 333. Those additional three layers do not help complete any existing unfinished layer; they only start new unfinished segments. Hence there is never a benefit in choosing a larger value.

After choosing HiH_iHi​, the last segment on every layer from 111 through HiH_iHi​ is extended by one position. Therefore, add 11 modulo to .

After all positions have been processed, if some Sk≠0S_k\ne0Sk​=0 remains, then the last segment on that layer has length not divisible by 333, so the target is impossible. Otherwise, the heights chosen by the greedy algorithm are optimal.

We need two operations on the sequence SSS: add 111 modulo 333 to a prefix S1,…,SHS_1,\ldots,S_HS1​,…,S, and find the largest such that . Both can be supported with a lazy segment tree.

For each node, store a 333-bit mask describing which values among 0,1,20,1,20,1,2 occur in that interval. Bit jjj is set if some Sk=jS_k=jSk​ exists in the interval. Adding modulo maps the states to , so the mask can be updated by a cyclic rotation of its three bits.

To find the largest kkk with Sk≠0S_k\ne0Sk​=0, descend from the root while checking the right child first and choosing a child whose mask contains state 111 or .

Each new HiH_iHi​ is at most M+2M+2M+2, so it is sufficient to maintain heights only up to 2N2N2N.

The time complexity is O(Nlog⁡N)O(N\log N)O(NlogN), and the memory complexity is O(N)O(N)O(N).

Solution written by GPT5.6

i+3​
1≤i≤N−31\le i\le N-31≤i≤N−3
−1-1−1
i
​
Hi≡pos⁡i−i(mod3)H_i\equiv \operatorname{pos}_i-i\pmod3Hi​≡posi​−i(mod3)
+
1
333
kkk
Hi≥kH_i\ge kHi​≥k
333
333
Hi≡pos⁡i−i(mod3)H_i\equiv \operatorname{pos}_i-i\pmod3
Hi​≡posi​−i(mod3)
iii
333
333
(H1+H2+⋯+HN)/3(H_1+H_2+\cdots+H_N)/3(H1​+H2​+⋯+HN​)/3
3
kkk
MM
M
kkk
Sk≠0S_k\ne0Sk​=0
kkk
M=0M=0M=0
​
≡
posi​−i
(mod3)
1
333
S1,S2,…,SHiS_1,S_2,\ldots,S_{H_i}S1​,S2​,…,SHi​​
H​
kkk
Sk≠0S_k\ne0Sk​=0
=
j
111
333
0,1,20,1,20,1,2
1,2,01,2,01,2,0
22
2