5f:"/_next/static/immutable/chunks/3v8ben6d43d91.js" 60:"/_next/static/immutable/chunks/0le4-u130-4hz.js" 61:"/_next/static/immutable/chunks/35821513-5wlr.js" 62:"/_next/static/immutable/chunks/2gx86s6q8ou3-.js" 63:"/_next/static/immutable/chunks/1l84jpbzha-ys.js" 64:"/_next/static/immutable/chunks/2lqw1ywfom61e.js" 65:"/_next/static/immutable/chunks/2dc_52--hiuh_.js" 66:I[290370,["$4","$5","$6","$7","$8","$9","$a","$b","$c","$47","$4e","$4f","$4a","$50","$51","$52","$48","$3e","$3d","$53","$54","$5f","$60","$61","$62","$63","$64","$65"],"default"] 67:I[218728,["$4","$5","$6","$7","$8","$9","$a","$b","$c","$47","$4e","$4f","$4a","$50","$51","$52","$48","$3e","$3d","$53","$54","$5f","$60","$61","$62","$63","$64","$65"],"default"] 68:T6c1,#include "testlib.h" #include using namespace std; // Independently decide feasibility using a priority queue of block starts. bool possible(const vector& b) { int n = int(b.size()) - 1; priority_queue> candidates; if (b[1] > 0) candidates.push({1, b[1] + 1}); for (int i = 2; i <= n + 1; ++i) { while (!candidates.empty() && candidates.top().second < i) candidates.pop(); if (candidates.empty()) return false; if (i <= n) { int right = candidates.top().first + b[i] + 1; if (right > i) candidates.push({i, right}); } } return true; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int n = inf.readInt(); vector b(n + 1); for (int i = 1; i <= n; ++i) b[i] = inf.readInt(); long long first = ouf.readLong(-1LL, static_cast(n), "a_1 or -1"); if (first == -1) { if (!ouf.seekEof()) quitf(_wa, "Extra output tokens"); if (possible(b)) quitf(_wa, "A valid array exists"); quitf(_ok, "Impossible instance"); } vector seen(n + 1, false); long long sum = 0; for (int i = 1; i <= n; ++i) { long long value = (i == 1 ? first : ouf.readLong(-1LL, static_cast(b[i]), "a_i")); if (value < -1 || value > b[i]) quitf(_wa, "a_%d is out of bounds", i); sum += value; if (sum < 1 || sum > n) quitf(_wa, "Prefix sum %d is out of range", i); if (seen[int(sum)]) quitf(_wa, "Repeated prefix sum %lld", sum); seen[int(sum)] = true; } if (!ouf.seekEof()) quitf(_wa, "Extra output tokens"); quitf(_ok, "Valid array"); } 69:T40d,Process positions from left to right. Keep previously reached starts in a stack, inserting a start only when its interval contains a later position. At position $j$, repeatedly remove the top start while its right endpoint is smaller than $j$. Such a start can never help again, since all remaining positions are even larger. If the stack is nonempty, its top is the largest start that reaches $j$, so it gives $\operatorname{parent}[j]$. If the stack becomes empty, no earlier reachable start reaches $j$ or any later position. The answer is $-1$. Otherwise, after reaching $n+1$, follow the parent pointers backwards. Each pair of consecutive boundaries gives a block to reverse. Build the resulting permutation $p$ and output $a_i=p_i-p_{i-1}$, with $p_0=0$. Every jump respects its bound by construction, and the reversed blocks contain every value exactly once. Each start enters and leaves the stack at most once. Reconstructing the blocks also visits each position once. The total time and memory complexities are both $O(n)$.6a:T861,We now show that $m+B$ minutes always suffice. This schedule is only for the proof; the algorithm does not build it. Number a child's operations by their progress $d=0,1,\ldots,m-1$. At each pencil, order its users by increasing progress: children who start with that pencil go first, then children who use it second, and so on. Break ties by child index. Create a dependency from each operation to the child's next operation, and from each operation to the next user of the same pencil. Every dependency increases progress, except dependencies between children with the same starting color and progress, which increase the child index. Therefore there is no directed cycle. Schedule each operation one minute after its latest predecessor, or in minute $1$ if it has none. All child orders are respected, and no pencil has two users in the same minute. The finishing time is the largest number of operations on a dependency chain. ## Bound a dependency chain Along a child dependency, progress increases by $1$ and the starting color stays fixed. Along a pencil dependency between different starting colors, the starting color moves backward around the circle by exactly the increase in progress. Let $J$ be the number of child dependencies on a chain, and let $L$ be the total backward movement of its starting color. Since progress stays between $0$ and $m-1$, we have $J+L\le m-1$. All starting colors encountered on this chain lie in one circular interval of $L+1$ colors. The chain cannot go all the way around the circle, so it never returns to a starting color after leaving it. Suppose this interval contains $C$ children. Within a fixed starting color, every pencil dependency increases the child index. The number of these dependencies is at most $c_j-1$. If the chain visits $g$ starting colors, there are exactly $g-1$ pencil dependencies between different starting colors. Altogether, the chain has at most $C-1$ pencil dependencies and hence at most $C+J$ operations. Using $J\le m-1-L$, its length is at most $C+m-1-L=m+C-(L+1)\le m+B$. Thus the schedule finishes within the lower bound, and the answer is exactly $m+B$.6b:T459,Start with the sum of the unavoidable costs: $L-1$ for the empty-sofa cycle and $L+1$ for every other nontrivial cycle. Let $R$ be the largest capacity in the empty-sofa cycle. We can reach its largest sofa and pause there before completing that cycle. For every other cycle, record its pair $(w,B)$. Sort these pairs by $w$. Process all pairs with $w \le R$: - For a nontrivial cycle, mark it processed and set $R=\max(R,B)$. - For a correctly seated guest, remember their sofa as an available helper. An increase of $R$ may make more cycles available, so continue until no further pair is eligible. If every nontrivial cycle has been processed, the answer is complete. Otherwise, choose the available helper with the largest sofa capacity. If that capacity exceeds $R$, add two moves, increase $R$, and continue. If no helper can increase $R$, the target is impossible. Choosing the largest available sofa is optimal: every helper costs the same two moves, and a larger capacity makes every move available that a smaller capacity would. Processing all freely available cycles can only improve this choice.6c:T5df,Consider any valid sequence, and look at the first time it touches a cycle outside the empty-sofa cycle. All sofas in that cycle are still occupied by their original guests. Therefore, its first move must take an original guest out to an already exposed sofa. This requires a previously exposed capacity of at least the cycle's smallest guest size. After this first move, even granting access to every sofa in that cycle increases the largest exposed capacity only to $\max(R,B)$. Consequently, the capacity expansion rules describe an upper bound on what any sequence can reach. A correctly seated guest used in such a sequence contributes at least two additional moves. At each such paid expansion, choosing the largest available capacity reaches at least as far as any other choice; the subsequent free expansions preserve this advantage. The greedy algorithm therefore uses the minimum possible number of helpers. These bounds are attainable. Whenever a component increases the capacity, pause its processing at its largest sofa and perform the next expansion there. Once all required cycles have been handled, finish the suspended processes in reverse order. Each inner process restores the empty sofa needed by its outer process. Thus every nontrivial cycle uses exactly its baseline cost, and every chosen helper uses exactly two moves. Finding the cycles takes $O(n)$ time. Sorting their pairs takes $O(n\log n)$ time, and one forward scan performs all expansions. The memory usage is $O(n)$.2b:["$","div",null,{"children":[["$","$L66",null,{"contestId":"6aa6ea4e982e23f8568a79d4","contestType":"cp","contestNumber":25,"contestUrlId":"25","initialIsRegistered":false,"registrationClosed":true}],["$","$L67",null,{"contest":{"contestNumber":25,"title":"Repovive Starter Round 9","startDate":"2026-09-27T15:05:00.000Z","endDate":"2026-09-27T17:05:00.000Z","urlSlug":"$undefined","problemDisplay":"letters","requiresPremium":false,"lobbyProblemsCount":7,"isProblemSet":false,"contestType":"cp","adminOnly":false,"isWeeklyChallenge":false,"weekNumber":"$undefined","ratedMaxTier":"sushi-roll","announcements":[]},"problems":[{"_id":"6ab7bc24167b809fc0b27c72","contestId":"6aa6ea4e982e23f8568a79d4","slug":"group-photos","title":"Group Photos","description":"A group of $n$ friends want to take group photos, but they do not have a tripod.\n\nFor each photo, one friend takes the photo, and all the other $n-1$ friends appear in it. The photographer does not appear in that photo.\n\nEach friend wants to appear in at least $k$ photos. What is the minimum number of photos they need to take?","constraints":"- $2 \\le n \\le 1000$\n- $1 \\le k \\le 1000$","difficulty":"easy","order":1,"label":"A","releaseDay":"$undefined","points":500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2 3\n","expectedOutput":"6\n","isSample":true,"hidden":false,"explanation":"Each photo contains only one friend. They can take three photos of each other, for a total of six. Fewer photos cannot give both friends three appearances.\n"},{"input":"3 2\n","expectedOutput":"3\n","isSample":true,"hidden":false,"explanation":"Each friend can take one photo. Then every friend appears in the other two photos. Two photos would give only four appearances in total, but six are needed.\n"},{"input":"4 4\n","expectedOutput":"6\n","isSample":true,"hidden":false,"explanation":"Number the friends from 1 to 4. They can choose friends 1, 2, 3, 4, 1, and 2 as the photographers, in that order. Friends 1 and 2 appear in four photos each, and friends 3 and 4 appear in five photos each. Five photos would give only fifteen appearances in total, but sixteen are needed.\n"}],"sampleCount":3,"inputFormat":"$$$\nn \\quad k\n$$","outputFormat":"$$$\n\\mathrm{answer}\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":57,"attemptedCount":59,"tags":["math"],"learnPages":[{"title":"Counting appearances","content":"If the friends take $m$ photos, there are exactly $m(n-1)$ appearances in total. Everyone needs at least $k$ appearances, so $m(n-1) \\ge nk$. Therefore, at least $\\lceil nk/(n-1)\\rceil$ photos are necessary.\n\n# Taking turns\n\nLet $m=\\lceil nk/(n-1)\\rceil$, and let friends take turns being the photographer in the order $1,2,\\ldots,n,1,2,\\ldots$.\n\nEach friend takes at most $\\lceil m/n\\rceil$ photos. From $m(n-1)\\ge nk$, we obtain $m/n\\le m-k$. Since $m-k$ is an integer, $\\lceil m/n\\rceil\\le m-k$. Thus, every friend appears in at least $m-\\lceil m/n\\rceil\\ge k$ photos.\n\nThe lower bound is achievable, so $\\mathrm{answer}=\\lceil nk/(n-1)\\rceil$. Using integer division, compute it as $(nk+n-2)/(n-1)$.\n\nThe time complexity is $O(1)$, and the extra space complexity is $O(1)$."}],"hasLearnContent":true,"likeCount":5,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-09-26T12:35:48.388Z","updatedAt":"2026-09-26T12:51:25.926Z"},{"_id":"6ab7bca1406c7fb2ea17917b","contestId":"6aa6ea4e982e23f8568a79d4","slug":"one-more-merge","title":"One More Merge","description":"You are given an array $a$ of $n$ positive integers.\n\nIn one operation, choose two adjacent elements $x$ and $y$ and replace them with the single number $\\min(x,y)+1$. The other elements keep their relative order.\n\nFind the minimum possible value of the remaining element after $n-1$ operations.","constraints":"- $2 \\le n \\le 2 \\times 10^5$\n- $1 \\le a_i \\le 10^9$","difficulty":"easy","order":2,"label":"B","releaseDay":"$undefined","points":1000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n1 8 8\n","expectedOutput":"2\n","isSample":true,"hidden":false,"explanation":"Merge the two elements equal to $8$, obtaining $[1,9]$. Merge the remaining pair to obtain $2$. Since every merge produces a number at least $2$, this is optimal.\n"},{"input":"3\n8 1 8\n","expectedOutput":"3\n","isSample":true,"hidden":false,"explanation":"The first operation produces either $[2,8]$ or $[8,2]$. In both cases, the final operation produces $3$.\n"},{"input":"4\n8 1 1 8\n","expectedOutput":"3\n","isSample":true,"hidden":false,"explanation":"Merge the first two elements, obtaining $[2,1,8]$. Merge the last two elements to obtain $[2,2]$, and then merge once more to obtain $3$. No order of operations produces a value smaller than $3$.\n"}],"sampleCount":3,"inputFormat":"$$$\n\\begin{array}{l}\nn \\\\\na_1 \\quad a_2 \\quad \\cdots \\quad a_n\n\\end{array}\n$$","outputFormat":"$$$\n\\mathrm{answer}\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":50,"attemptedCount":52,"tags":["greedy","math"],"learnPages":[{"title":"What can the last merge produce?","content":"Let $m$ be the minimum element of the original array. Every current element is at least $m$, since merging two values at least $m$ produces a value at least $m+1$.\n\nThe last operation therefore gives at least $m+1$. To obtain exactly $m+1$, one of the two elements immediately before that operation must equal $m$.\n\nNo merge can create $m$, so this element must be an original minimum that has never been merged."},{"title":"Keep a minimum until the end","content":"If an original minimum lies strictly inside the array and remains untouched, there is always at least one element on each side of it. Operations on either side can shorten that side, but cannot remove it entirely. Such a minimum cannot be one of the last two elements.\n\nThus, $m+1$ is possible only if $a_1=m$ or $a_n=m$. In that case, keep that endpoint untouched, merge all other elements into one, and perform the final merge. Its result is exactly $m+1$.\n\nOtherwise, the answer is at least $m+2$. Keep any original minimum untouched and merge each side separately into one element. Merge the minimum with one side, producing $m+1$, and then with the other side. The final value is at most $m+2$, so the lower bound is attained."},{"title":"A single scan","content":"Find $m=\\min(a_1,a_2,\\ldots,a_n)$ and remember the two endpoints.\n\n- If $a_1=m$ or $a_n=m$, output $m+1$.\n- Otherwise, output $m+2$.\n\nThe algorithm takes $O(n)$ time and $O(1)$ extra space. There is no need to store the array or simulate the operations."}],"hasLearnContent":true,"likeCount":4,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-09-26T12:37:53.715Z","updatedAt":"2026-09-26T12:51:33.556Z"},{"_id":"6ab7bd0b03b16818a256a6c3","contestId":"6aa6ea4e982e23f8568a79d4","slug":"compression-space","title":"Compression Space","description":"A computer stores $n$ files on its disk. File $i$ occupies $a_i$ units of space, and its compressed version occupies $b_i$ units, where $b_i < a_i$.\n\nTo compress a file, the computer first writes its compressed version into free space on the same disk. Only after the compressed version has been written completely does it delete the original file. Thus, the disk must have at least $b_i$ units of free space before file $i$ can be compressed.\n\nYou may compress the files in any order, one at a time.\n\nFind the minimum amount of free disk space needed initially to compress all the files.","constraints":"- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le b_i < a_i \\le 10^9$\n- All input values are integers.","difficulty":"easy","order":3,"label":"C","releaseDay":"$undefined","points":1500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"1\n7 3\n","expectedOutput":"3\n","isSample":true,"hidden":false,"explanation":"The compressed version needs 3 units of free space. After it is written, the original file can be deleted.\n"},{"input":"3\n10 8\n4 3\n6 2\n","expectedOutput":"3\n","isSample":true,"hidden":false,"explanation":"Start with 3 free units and compress files 3, 2, and 1, in that order. The free space after each compression is 7, 8, and 10 units.\n\nWith fewer than 2 free units, no file can be compressed. With 2 free units, only file 3 can be compressed first. Compressing files 3 and 2 leaves 7 free units, which is not enough for file 1.\n"},{"input":"4\n12 4\n5 2\n9 7\n3 1\n","expectedOutput":"1\n","isSample":true,"hidden":false,"explanation":"Start with 1 free unit and compress files 4, 2, 1, and 3. The free space becomes 3, 6, 14, and 16 units, respectively. With no free space, no file can be compressed.\n"}],"sampleCount":3,"inputFormat":"$$$\n\\begin{array}{l}\nn \\\\\na_1 \\quad b_1 \\\\\na_2 \\quad b_2 \\\\\n\\vdots \\\\\na_n \\quad b_n\n\\end{array}\n$$","outputFormat":"$$$\n\\mathrm{answer}\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":48,"attemptedCount":50,"tags":["greedy"],"learnPages":[{"title":"Compress the smallest version first","content":"Compressing file $i$ requires $b_i$ units of free space. Writing its compressed version consumes $b_i$ units, and deleting the original releases $a_i$ units. The free space therefore increases by $a_i-b_i>0$.\n\nConsider the remaining file with the smallest $b_i$. If it does not fit, no remaining file fits. If it fits, compressing it immediately cannot hurt: move it to the front of any successful order. Every file that originally preceded it now has more free space available, and after those files the amount of free space is unchanged.\n\nRepeating this argument shows that sorting by $b_i$ in nondecreasing order is optimal. Ties may be resolved arbitrarily."},{"title":"Account for the space already freed","content":"Sort the files by $b_i$. Let $S$ be the total space saved by the files already compressed. Starting with $R$ free units, the current free space is $R+S$.\n\nThe next file fits exactly when $R+S\\ge b_i$, or $R\\ge b_i-S$. This bound is necessary for that step and sufficient to perform it. Taking the maximum of these bounds therefore gives the smallest initial space that works for the entire order.\n\nStart with $S=0$ and $\\mathrm{answer}=0$. For each file, first set $\\mathrm{answer}=\\max(\\mathrm{answer},b_i-S)$, then increase $S$ by $a_i-b_i$.\n\nThe order is optimal by the previous observation, so this also minimizes the required space over all possible orders.\n\nSorting takes $O(n\\log n)$ time, and the scan takes $O(n)$ time. The memory usage is $O(n)$. Use a 64-bit integer for $S$, since the savings accumulate across all files."}],"hasLearnContent":true,"likeCount":1,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-09-26T12:39:39.451Z","updatedAt":"2026-09-26T12:51:44.208Z"},{"_id":"6ab7be9903b16818a256a6c8","contestId":"6aa6ea4e982e23f8568a79d4","slug":"prefix-permutation","title":"Prefix Permutation","description":"You are given an array $b$ of $n$ nonnegative integers.\n\nConstruct an integer array $a$ of length $n$ such that:\n\n- $-1 \\le a_i \\le b_i$ for every $i$.\n- The prefix sums $a_1, a_1+a_2, \\ldots, a_1+a_2+\\cdots+a_n$ contain each integer from $1$ to $n$ exactly once.\n\nIf no such array exists, output $-1$. Otherwise, output any valid array.","constraints":"- $1 \\le n \\le 2 \\times 10^5$\n- $0 \\le b_i \\le n$\n- All input values are integers.","difficulty":"easy","order":4,"label":"D","releaseDay":"$undefined","points":2000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"6\n2 0 4 0 0 3\n","expectedOutput":"2 -1 4 -1 -1 3\n","isSample":true,"hidden":false,"explanation":"The prefix sums are $2,1,5,4,3,6$, so each integer from $1$ to $6$ appears exactly once. Every element of the output also satisfies its corresponding bound.\n"},{"input":"4\n2 0 2 0\n","expectedOutput":"-1\n","isSample":true,"hidden":false,"explanation":"The first prefix sum must be $1$ or $2$. If it is $1$, no allowed value of $a_2$ gives a new positive prefix sum. If it is $2$, then $a_2=-1$ is forced. The third prefix sum is then at most $3$, so it must be $3$. Since $a_4\\le 0$, the fourth prefix sum cannot be the remaining value $4$. Thus no valid array exists.\n"},{"input":"1\n1\n","expectedOutput":"1\n","isSample":true,"hidden":false,"explanation":"The only prefix sum is $1$, and $-1\\le a_1\\le b_1$ holds.\n"}],"sampleCount":3,"inputFormat":"$$$\n\\begin{array}{l}\nn \\\\\nb_1 \\quad b_2 \\quad \\cdots \\quad b_n\n\\end{array}\n$$","outputFormat":"$$$\na_1 \\quad a_2 \\quad \\cdots \\quad a_n\n$$\n\nIf no valid array exists:\n\n$$\n-1\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$68"},"solvedCount":14,"attemptedCount":23,"tags":["greedy"],"learnPages":[{"title":"The shape of the prefix sums","content":"Let $p_0=0$ and $p_i=a_1+\\cdots+a_i$. We need a permutation $p$ of $1,\\ldots,n$ with $-1\\le p_i-p_{i-1}\\le b_i$.\n\nWhenever the permutation decreases, it must decrease by exactly one: a larger drop is forbidden, and equal values would repeat a prefix sum.\n\nSuppose its first value is $r$. It must begin $r,r-1,\\ldots,1$. If it increases before reaching $1$, it can never return to the remaining smaller values: moving down to them would require passing through a value already used.\n\nThe same argument applies to the unused values. Thus every valid permutation is obtained by splitting $1,2,\\ldots,n$ into consecutive blocks and reversing each block. For example, blocks $[1,2]$, $[3]$, $[4,5,6]$ give $2,1,3,6,5,4$.\n\nInside a block, $a_i=-1$, which always satisfies its bound. Only the jumps at block starts need to be checked."},{"title":"Keep the latest previous start","content":"Consider a block starting at position $i$ and ending just before position $j$. Its first prefix sum is $j-1$. If the previous block started at $k$, its last prefix sum is $k$. The jump at $i$ is therefore $j-1-k$, so this block is allowed exactly when $j\\le k+b_i+1$. For the first block, use $i=1$ and $k=0$.\n\nFor each possible block start $i$, let $\\operatorname{parent}[i]$ be the largest possible previous block start among all valid ways to cover positions before $i$. Set $\\operatorname{parent}[1]=0$.\n\nKeeping only this largest value loses nothing: a larger previous start makes the jump at $i$ smaller, allowing every block ending that any smaller previous start allows.\n\nConsequently, a reachable start $i$ can be followed by any start from $i+1$ through $R_i=\\min(n+1,\\operatorname{parent}[i]+b_i+1)$. At a position $j$, choose the largest earlier start $i$ whose interval reaches $j$, and set $\\operatorname{parent}[j]=i$.\n\nTreat $n+1$ as a final boundary. Reaching it means all positions have been covered."},{"title":"Find the starts with a stack","content":"$69"}],"hasLearnContent":true,"likeCount":0,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-09-26T12:46:17.612Z","updatedAt":"2026-09-26T12:51:55.798Z"},{"_id":"6ab7bed903b16818a256a6cc","contestId":"6aa6ea4e982e23f8568a79d4","slug":"colored-pencils","title":"Colored Pencils","description":"There are $n$ children and $m$ colored pencils. The colors are numbered from $1$ to $m$, and there is exactly one pencil of each color.\n\nEach child wants to draw one line with each color. Child $i$ must use the colors in the order $a_i, a_i+1, \\ldots, m, 1, \\ldots, a_i-1$.\n\nDrawing one line takes exactly one minute. During each minute, each child can use at most one pencil, and each pencil can be used by at most one child. Children may wait before drawing their first line or between drawing two lines.\n\nFind the minimum number of minutes needed for all children to finish drawing.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n,m \\le 2 \\times 10^5$\n- $1 \\le a_i \\le m$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$.\n- The sum of $m$ over all test cases is at most $2 \\times 10^5$.","difficulty":"medium","order":5,"label":"E","releaseDay":"$undefined","points":2500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2\n3 4\n1 1 1\n4 4\n1 2 3 4\n","expectedOutput":"6\n4\n","isSample":true,"hidden":false,"explanation":"The children can start in minutes $1$, $2$, and $3$, then each draws for four consecutive minutes. They finish in minutes $4$, $5$, and $6$. The last child to use pencil $1$ cannot do so before minute $3$ and needs three more minutes, so fewer than $6$ minutes is impossible.\n`\nAll four children can draw without waiting. In each minute, they use four different pencils, so everyone finishes after $4$ minutes. Each child needs four lines, so this is optimal.\n","displayOutput":"6\n`\n4","displayInput":"2\n`\n3 4\n1 1 1\n`\n4 4\n1 2 3 4"},{"input":"3\n6 4\n1 1 1 3 3 3\n1 5\n4\n5 1\n1 1 1 1 1\n","expectedOutput":"7\n5\n5\n","isSample":true,"hidden":false,"explanation":"One schedule is shown below. A dash means that the child does not draw during that minute.\n\n| Child | Minute 1 | Minute 2 | Minute 3 | Minute 4 | Minute 5 | Minute 6 | Minute 7 |\n| --- | --- | --- | --- | --- | --- | --- | --- |\n| 1 | 1 | 2 | - | 3 | 4 | - | - |\n| 2 | - | 1 | 2 | - | 3 | 4 | - |\n| 3 | - | - | 1 | 2 | - | 3 | 4 |\n| 4 | 3 | 4 | - | 1 | 2 | - | - |\n| 5 | - | 3 | 4 | - | 1 | 2 | - |\n| 6 | - | - | 3 | 4 | - | 1 | 2 |\n\nEvery child still needs at least one line after using pencil $3$. That pencil must be used six times, so the last of these uses cannot finish before minute $6$. At least $7$ minutes are necessary.\n`\nThe only child uses colors $4,5,1,2,3$ in five consecutive minutes. Five lines require at least $5$ minutes.\n`\nThe children take turns using the only pencil. Exactly $5$ minutes are needed.\n","displayOutput":"7\n`\n5\n`\n5","displayInput":"3\n`\n6 4\n1 1 1 3 3 3\n`\n1 5\n4\n`\n5 1\n1 1 1 1 1"}],"sampleCount":2,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad m \\\\\na_1 \\quad a_2 \\quad \\cdots \\quad a_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\mathrm{answer}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":8,"attemptedCount":11,"tags":["greedy"],"learnPages":[{"title":"Crowded arcs force extra time","content":"Let $c_j$ be the number of children whose first color is $j$. Every child needs $m$ minutes of work, so the answer is at least $m$.\n\nTake any nonempty circular interval of $k$ colors, ending at color $r$, and let $C$ children start inside it. Each of these children must use pencil $r$. After doing so, each still has at least $m-k$ lines left: reaching $r$ uses at most the first $k$ colors of their sequence.\n\nPencil $r$ needs $C$ different minutes for these children. Its last such use cannot finish before minute $C$, and that child needs at least $m-k$ more minutes. Thus the answer is at least $C+m-k$.\n\nWrite $x_j=c_j-1$. The bound becomes $m+\\sum x_j$ over the chosen circular interval. Let $B$ be the maximum of these sums, also allowing the empty interval with sum $0$. We have proved that at least $m+B$ minutes are necessary."},{"title":"Order each pencil's users by progress","content":"$6a"},{"title":"Find the largest circular sum","content":"A circular interval either is an ordinary interval in $x_1,\\ldots,x_m$, or is the complement of an ordinary interval.\n\nLet $S$ be the sum of the array, $H$ its maximum ordinary subarray sum, and $L$ its minimum ordinary subarray sum. Allow empty subarrays in both definitions. Then $B=\\max(H,S-L)$: the second term also covers the full circle by removing an empty interval.\n\nCompute $H$ and $L$ in one scan. Keep the largest and smallest sums ending at the current position, updating them as $h=\\max(0,h+x_j)$ and $\\ell=\\min(0,\\ell+x_j)$. Record their largest and smallest values.\n\nOutput $\\mathrm{answer}=m+\\max(H,S-L)$.\n\nBuilding the counts takes $O(n)$ time, and the scan takes $O(m)$ time. Total complexity is $O(n+m)$ time and $O(m)$ memory per test case."}],"hasLearnContent":true,"likeCount":0,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-09-26T12:47:21.746Z","updatedAt":"2026-09-27T13:51:52.540Z"},{"_id":"6ab7bf8803b16818a256a6d3","contestId":"6aa6ea4e982e23f8568a79d4","slug":"empty-sofa","title":"Empty Sofa","description":"There are $n$ guests and $n+1$ sofas, numbered from $1$ to $n$ and from $1$ to $n+1$, respectively. Guest $i$ has size $a_i$, and sofa $j$ has capacity $b_j$. Each sofa can hold at most one guest, and guest $i$ can sit on sofa $j$ only if $a_i \\le b_j$.\n\nInitially, guest $i$ is sitting on sofa $p_i$ and wants to end up on sofa $q_i$. Both arrangements are valid: the guests occupy distinct sofas, and every guest fits on their sofa.\n\nIn one move, choose a guest and move them to the empty sofa, provided that they fit on it. Their previous sofa becomes empty.\n\nFind the minimum number of moves needed to reach the desired arrangement. If it is impossible, output $-1$.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le a_i, b_j \\le 10^9$\n- $1 \\le p_i, q_i \\le n+1$\n- The values $p_1,\\ldots,p_n$ are pairwise distinct.\n- The values $q_1,\\ldots,q_n$ are pairwise distinct.\n- $a_i \\le b_{p_i}$ and $a_i \\le b_{q_i}$ for every guest $i$.\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$.","difficulty":"medium","order":6,"label":"G","releaseDay":"$undefined","points":3500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2\n2\n2 3\n3 2 1\n2 1\n2 1\n2\n2 2\n2 2 1\n1 2\n2 1\n","expectedOutput":"0\n-1\n","isSample":true,"hidden":false,"explanation":"The initial arrangement already matches the desired arrangement, so no moves are needed.\n`\nThe empty sofa has capacity 1, but both guests have size 2. No move is possible, and the guests are not in their desired positions.\n","displayOutput":"0\n`\n-1","displayInput":"2\n`\n2\n2 3\n3 2 1\n2 1\n2 1\n`\n2\n2 2\n2 2 1\n1 2\n2 1"},{"input":"3\n2\n2 1\n2 2 1\n1 3\n2 1\n3\n1 3 3\n1 3 3 3\n2 3 4\n2 4 3\n4\n1 1 5 5\n1 5 1 5 5\n2 3 4 5\n3 2 5 4\n","expectedOutput":"2\n5\n6\n","isSample":true,"hidden":false,"explanation":"Move guest 1 from sofa 1 to sofa 2, then move guest 2 from sofa 3 to sofa 1. Both guests must change sofas, so two moves are necessary.\n`\nMove guest 1 to sofa 1, guest 2 to sofa 2, guest 3 to sofa 3, guest 2 to sofa 4, and guest 1 back to sofa 2. Initially, only guest 1 can move to the empty sofa, and they must eventually return. Guests 2 and 3 need at least three moves to exchange their sofas, so at least five moves are needed.\n`\nMove guest 1 to sofa 1, guest 3 to sofa 2, guest 4 to sofa 4, guest 3 to sofa 5, guest 2 to sofa 2, and guest 1 to sofa 3. Guests 1 and 2 exchange their sofas, as do guests 3 and 4. In each pair, the first guest to move must move again because their destination is occupied. Therefore, at least six moves are needed.\n","displayOutput":"2\n`\n5\n`\n6","displayInput":"3\n`\n2\n2 1\n2 2 1\n1 3\n2 1\n`\n3\n1 3 3\n1 3 3 3\n2 3 4\n2 4 3\n`\n4\n1 1 5 5\n1 5 1 5 5\n2 3 4 5\n3 2 5 4"}],"sampleCount":2,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\na_1 \\quad a_2 \\quad \\cdots \\quad a_n \\\\\nb_1 \\quad b_2 \\quad \\cdots \\quad b_{n+1} \\\\\np_1 \\quad p_2 \\quad \\cdots \\quad p_n \\\\\nq_1 \\quad q_2 \\quad \\cdots \\quad q_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\mathrm{answer}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":3,"attemptedCount":3,"tags":["greedy"],"learnPages":[{"title":"Follow each guest's destination","content":"For every guest $i$, draw an arrow from $p_i$ to $q_i$. Also draw an arrow from the initially empty sofa to the desired empty sofa. Each sofa now has exactly one incoming and one outgoing arrow, so the sofas split into cycles.\n\nThe cycle containing the empty sofa can be solved by repeatedly moving the guest whose destination is currently empty. If it contains $L$ sofas, this takes $L-1$ moves. Every guest moves directly to their destination, so all these moves are legal. Along the way, every sofa in this cycle becomes empty.\n\nA different cycle of length $L>1$ needs at least $L+1$ moves. Every guest must move, and the first guest to leave the cycle cannot move directly to their destination: that sofa is still occupied. This guest must move at least twice.\n\nA one-sofa cycle contains a guest who is already correctly seated. Leaving this guest alone costs nothing. Using their sofa temporarily costs at least two moves, since they must leave and return."},{"title":"A small guest can expose a large sofa","content":"For a cycle not containing the empty sofa, let $w$ be its smallest guest size and $B$ its largest sofa capacity.\n\nIf the current empty sofa has capacity at least $w$, move a smallest guest there. Within the cycle, repeatedly move the guest whose destination is empty. Finally, move the guest waiting outside the cycle to their destination. For a cycle of length $L>1$, this uses exactly $L+1$ moves and restores the original empty sofa.\n\nEvery sofa in the cycle becomes empty during this process. In particular, we can pause when the sofa of capacity $B$ is empty, solve other cycles using it, and then resume. Those operations return the same sofa to its empty state, so the suspended process remains valid.\n\nThe same argument applies to a correctly seated guest: moving them out exposes their sofa, and moving them back costs one more move.\n\nThus a nontrivial cycle expands the capacity we can use without exceeding its unavoidable $L+1$ moves. A correctly seated guest can expand it at an extra cost of two moves."},{"title":"Pay only when progress stops","content":"$6b"},{"title":"Why extra detours cannot improve the answer","content":"$6c"}],"hasLearnContent":true,"likeCount":0,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-09-26T12:50:16.591Z","updatedAt":"2026-09-27T13:53:36.914Z"},{"_id":"6ab7bfbf03b16818a256a6d4","contestId":"6aa6ea4e982e23f8568a79d4","slug":"single-route","title":"Single Route","description":"You are given a directed acyclic graph with $n$ vertices and $m$ edges. The $i$-th edge goes from vertex $u_i$ to vertex $v_i$. Initially, every vertex is reachable from vertex $1$.\n\nYou may remove at most one edge. After the removal, there must be at most one directed path from vertex $1$ to each vertex.\n\nFind the maximum number of vertices that can remain reachable from vertex $1$, or report that this is impossible. Vertex $1$ itself is considered reachable.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $0 \\le m \\le 2 \\times 10^5$\n- $1 \\le u_i, v_i \\le n$\n- The graph has no directed cycles or parallel edges.\n- Initially, every vertex is reachable from vertex $1$.\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$.\n- The sum of $m$ over all test cases is at most $2 \\times 10^5$.","difficulty":"medium","order":7,"label":"F","releaseDay":"$undefined","points":3000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2\n4 3\n1 2\n1 3\n3 4\n7 8\n1 2\n1 3\n2 4\n3 4\n1 5\n1 6\n5 7\n6 7\n","expectedOutput":"4\n-1\n","isSample":true,"hidden":false,"explanation":"No edge needs to be removed. All four vertices are reachable, and each has a unique path from vertex $1$.\n`\nThere are two paths from vertex $1$ to vertex $4$ and two paths from vertex $1$ to vertex $7$. The edges used by these two pairs are disjoint, so removing one edge cannot fix both.\n","displayOutput":"4\n`\n-1","displayInput":"2\n`\n4 3\n1 2\n1 3\n3 4\n`\n7 8\n1 2\n1 3\n2 4\n3 4\n1 5\n1 6\n5 7\n6 7"},{"input":"3\n1 0\n4 4\n1 2\n1 3\n2 4\n3 4\n5 6\n1 2\n2 3\n1 4\n4 5\n2 4\n3 5\n","expectedOutput":"1\n4\n3\n","isSample":true,"hidden":false,"explanation":"The only vertex is vertex $1$, which is reachable.\n`\nRemove the edge $2 \\to 4$. All four vertices remain reachable, and each has a unique path from vertex $1$.\n`\nRemove the edge $1 \\to 2$. Exactly vertices $1$, $4$, and $5$ remain reachable, each by a unique path. Every other single-edge removal leaves two paths to vertex $4$ or vertex $5$, so the answer is $3$.\n","displayOutput":"1\n`\n4\n`\n3","displayInput":"3\n`\n1 0\n`\n4 4\n1 2\n1 3\n2 4\n3 4\n`\n5 6\n1 2\n2 3\n1 4\n4 5\n2 4\n3 5"}],"sampleCount":2,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad m \\\\\nu_1 \\quad v_1 \\\\\nu_2 \\quad v_2 \\\\\n\\vdots \\\\\nu_m \\quad v_m\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\mathrm{answer}\n\\end{array}\n\\right\\} \\times t\n$$\n\n$\\mathrm{answer} = -1$ if it is impossible.","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":3,"attemptedCount":4,"tags":["graph","dag"],"learnPages":[{"title":"When every vertex can stay","content":"Since all vertices are reachable from $1$, we can select $n-1$ edges forming a directed tree rooted at $1$. It has exactly one path to each vertex.\n\nTherefore, if $m \\le n$, deleting at most one edge leaves such a tree, and the answer is $n$.\n\nOtherwise, compute a topological order. Let $z$ be the first vertex in this order with at least two incoming edges. Every earlier vertex has a unique path from $1$: except for $1$, it has exactly one predecessor, which is also earlier."},{"title":"Only two paths matter","content":"Choose any two incoming edges of $z$. Each predecessor has a unique path from $1$, so these edges give two distinct paths $P$ and $Q$ from $1$ to $z$.\n\nA successful deletion must remove an edge of $P$ or $Q$. Otherwise, both paths survive, violating the requirement at $z$.\n\nRecover the two paths by following the sole incoming edge of each vertex before $z$. They may share a prefix. We only need to search the edges of these two paths, even if $z$ has more incoming edges."},{"title":"Valid deletions form a prefix","content":"Consider two edges $e$ and $f$ on one selected path, with $e$ earlier than $f$.\n\nThe tail of $f$ is before $z$, so its original path from $1$ is unique and uses $e$. Removing $e$ makes that tail unreachable. Consequently, every path starting at $1$ that survives deleting $e$ also avoids $f$, and survives deleting $f$.\n\nThis gives two useful facts:\n\n- If deleting $f$ is valid, deleting $e$ is valid too, because it leaves a subset of the paths.\n- Deleting $f$ leaves at least as many reachable vertices as deleting $e$.\n\nThus valid deletions form a prefix of each selected path. Its last edge gives the best answer on that path. Find this edge by binary search, allowing the prefix to be empty."},{"title":"Checking one deletion","content":"Ignore the chosen edge and process vertices in topological order. Start with one path to vertex $1$ and zero paths to every other vertex.\n\nFor each remaining edge $u \\to v$, add the number of paths to $u$ to the count for $v$. Each path to $v$ has exactly one last edge, so this counts all paths. Stop and reject as soon as a count reaches two. No large integers are needed.\n\nIf no count reaches two, the deletion is valid. The number of positive counts is the number of reachable vertices.\n\nRun the binary search on both selected paths and take the largest valid result. If neither contains a valid deletion, output $-1$, since every possible successful deletion had to be on their union.\n\nEach check takes $O(n+m)$ time, and there are $O(\\log n)$ checks per path. Total time is $O((n+m)\\log n)$ and memory is $O(n+m)$ per test case."}],"hasLearnContent":true,"likeCount":0,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-09-26T12:51:11.042Z","updatedAt":"2026-09-27T13:52:54.246Z"}],"contestId":"6aa6ea4e982e23f8568a79d4","contestUrlId":"25","isAdmin":false,"isTester":false,"isStarted":true,"isRegistered":false,"canRegister":false,"problemStatusMap":{},"isPremiumBlocked":false,"sponsorshipSnapshot":"$2a:props:children:props:children:1:props:children:0:props:sponsorshipSnapshot","recentRoundParticipantCounts":[114,127,148],"participationMode":null,"virtualStartTime":null,"contestDurationMs":7200000}]]}]

AGroup Photos	500	57/59
BOne More Merge	1000	50/52
CCompression Space	1500	48/50
DPrefix Permutation	2000	14/23
EColored Pencils	2500	8/11
FSingle Route	3000	3/4
GEmpty Sofa	3500	3/3