39:I[290370,["/_next/static/immutable/chunks/3ywlgh2gdk10-.js","/_next/static/immutable/chunks/2v61o810dw1rf.js","/_next/static/immutable/chunks/21xhskz0ddfeh.js","/_next/static/immutable/chunks/3b2h_bbz559px.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/3z9ijn_lb0a45.js","/_next/static/immutable/chunks/3fo-xwmct_52g.js","/_next/static/immutable/chunks/3t4q2aicaxgqp.js","/_next/static/immutable/chunks/30mvq78--5n8t.js","/_next/static/immutable/chunks/3tit614wiqzli.js","/_next/static/immutable/chunks/0cxjiw1oj-yi4.js","/_next/static/immutable/chunks/0xcz7j92bzv8_.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/3u26hx7f63szn.js","/_next/static/immutable/chunks/0dlc-qvk2lsni.js","/_next/static/immutable/chunks/2rt3qqlht6ovu.js","/_next/static/immutable/chunks/3am8x40qt_406.js","/_next/static/immutable/chunks/0rwu25h6frxyw.js","/_next/static/immutable/chunks/0_0v4iiyk1nvr.js"],"default"] 3a:I[218728,["/_next/static/immutable/chunks/3ywlgh2gdk10-.js","/_next/static/immutable/chunks/2v61o810dw1rf.js","/_next/static/immutable/chunks/21xhskz0ddfeh.js","/_next/static/immutable/chunks/3b2h_bbz559px.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/3z9ijn_lb0a45.js","/_next/static/immutable/chunks/3fo-xwmct_52g.js","/_next/static/immutable/chunks/3t4q2aicaxgqp.js","/_next/static/immutable/chunks/30mvq78--5n8t.js","/_next/static/immutable/chunks/3tit614wiqzli.js","/_next/static/immutable/chunks/0cxjiw1oj-yi4.js","/_next/static/immutable/chunks/0xcz7j92bzv8_.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/3u26hx7f63szn.js","/_next/static/immutable/chunks/0dlc-qvk2lsni.js","/_next/static/immutable/chunks/2rt3qqlht6ovu.js","/_next/static/immutable/chunks/3am8x40qt_406.js","/_next/static/immutable/chunks/0rwu25h6frxyw.js","/_next/static/immutable/chunks/0_0v4iiyk1nvr.js"],"default"] 3b:T4e5,Claim (structural): In an optimal/necessary search, we never need a coloring that contains a pattern `1-2-1` on three indices $i < j < k$ (i.e., $b_i$ is color $1$, $b_j$ is color $2$, $b_k$ is color $1$). Why is `1-2-1` unnecessary? Assume we have $i < j < k$ with colors $1,2,1$. Let’s compare this coloring to the coloring where we change $b_j$ from color $2$ to color $1$ (so the triple becomes `1-1-1`). - For color 1: Adding $b_j$ (which lies between two already-in-color-1 points) does not decrease $min_1$ and does not increase $max_1$. So $max_1 - min_1$ does not get worse. - For color 2: Removing $b_j$ can only make color 2 “tighter” (its $min/max$ interval can only stay the same or shrink), so $max_2 - min_2$ does not get worse either. So whenever `1-2-1` appears, we can transform it into `1-1-1` without breaking feasibility. Hence, if a feasible split exists, one exists with no `1-2-1` pattern. Now interpret “no `1-2-1`” on a sorted line: Once color $1$ stops and color $2$ starts, color $1$ can never appear again later. That means each color forms a contiguous block in sorted order. So every feasible split can be assumed to look like: `111...111 222...222` (or the symmetric version `222...222 111...111`) 3c:T649,#include #include "testlib.h" using namespace std; vector> cellsOf(int x, int y, int type) { if (type == 1) return {{x, y}, {x + 1, y}, {x, y + 1}}; if (type == 2) return {{x, y}, {x + 1, y}, {x, y - 1}}; if (type == 3) return {{x, y}, {x - 1, y}, {x, y + 1}}; return {{x, y}, {x - 1, y}, {x, y - 1}}; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int n = inf.readInt(); int m = inf.readInt(); vector a(n); for (int i = 0; i < n; i++) { a[i] = inf.readToken(); } long long limit = 4LL * n * m; long long k = ouf.readLong(0, limit, "k"); for (long long step = 1; step <= k; step++) { int x = ouf.readInt(1, n, "x"); int y = ouf.readInt(1, m, "y"); int type = ouf.readInt(1, 4, "type"); auto cells = cellsOf(x, y, type); for (auto [r, c] : cells) { if (r < 1 || r > n || c < 1 || c > m) { quitf(_wa, "operation %lld uses a cell outside the table", step); } } for (auto [r, c] : cells) { a[r - 1][c - 1] = (a[r - 1][c - 1] == '0' ? '1' : '0'); } } if (!ouf.seekEof()) { quitf(_wa, "extra output after the operations"); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] != '0') { quitf(_wa, "cell (%d,%d) is still 1", i + 1, j + 1); } } } quitf(_ok, "valid answer with %lld operations", k); }3d:T616,We can apply operations: choose $i$ $(l < i ≤ r)$, do `a[i-1]--` and `a[i]++`. Equivalently, we move $1$ unit of value one step to the right, inside $[l, r]$. Define $d[i] = a[i] - b[i]$. We want to make $d[i] = 0$ for all $i$ in $[l, r]$. Key invariant $1$ (total sum): The operation preserves $\sum_{i=l..r} a[i]$, so it preserves $\sum_{i=l..r} d[i]$. To end with all zeros we must have: $\sum_{i=l..r} d[i] = 0$. Key invariant $2$ (interval prefix sums can only go down): For $j$ in $[l, r]$, define interval-prefix: $S(j) = sum_{i=l..j} d[i]$. If we apply the operation at index $i$, only $d[i-1]$ decreases and $d[i]$ increases. So among all $S(j)$, the only one that changes is $S(i-1)$, and it decreases by $1$. No $S(j)$ can ever increase. In the target state (all $d = 0$), every $S(j)$ equals $0$. Since $S(j)$ never increases during operations, we must start with: $S(j) ≥ 0$ for all $j = l..r-1$, and also (from total sum): $S(r) = 0$. So a necessary condition is: 1) for all $j$ in $[l, r-1]$: $sum_{i=l..j} (a[i]-b[i]) ≥ 0$ 2) $sum_{i=l..r} (a[i]-b[i]) = 0$ This condition is also sufficient: Process positions from left to right. At position $x$, if $d[x] > 0$, we can move this surplus right (using operations at $x+1$ repeatedly) to reduce $d[x]$ to $0$. The constraints $S(j) ≥ 0$ guarantee we never need to “pull” from the right (which is impossible), so we can finish and reach all zeros. Conclusion: $[l, r]$ is beautiful ⇔ all interval prefix sums of $(a-b)$ are nonnegative and the total is zero. 3e:T4f0,You are given a rooted tree with $n$ vertices, numbered from $1$ to $n$. The root is vertex $1$. For every vertex $i$ with $2 \le i \le n$, you are given its parent $p_i$. It is guaranteed that $1 \le p_i < i$. The parents $p_2,p_3,\ldots,p_n$ are given in one line. At first, only vertex $1$ is red, and all other vertices are white. Vertex $1$ always remains red. You are given $q$ queries. The query vertices $x_1,x_2,\ldots,x_q$ are given in a single line. In each query, a vertex $x$ with $2 \le x \le n$ is given. If vertex $x$ is white, it becomes red. If vertex $x$ is red, it becomes white. After each query, consider all ways to choose some of the white vertices and color them blue. If there are $w$ white vertices, there are $2^w$ such choices. For each choice, define the colored vertices as all vertices that are red or blue. The blue coloring is only used for this calculation and is not kept for later queries. The beauty of the tree is the minimum number of edges that must be marked so that, using only marked edges, it is possible to move between every pair of colored vertices. If there is only one colored vertex, the beauty is $0$. After each query, output the sum of the beauties over all choices of blue vertices, modulo $998244353$.3f:T6f4,So all that remains is to find the first ancestor $u$ of $x_i$ whose subtree contains a red vertex. Once $u$ is known, we need to add or remove the contributions of all edges on the path from $x_i$ to $u$. This can be done using a simple prefix sum. Define $$ ps_u = \sum 2^{-sz}, $$ where the sum is taken over all ancestor edges of $u$. To find $u$, one approach is to binary search on the ancestors of $x_i$ while using a segment tree over Euler-tour entry times to count red vertices inside subtrees. However, there is also a solution that uses only Euler-tour order. Let the current red vertices other than $x_i$ be $$ r_1, r_2, \dots, r_k, $$ sorted by Euler-tour entry time. Suppose $x_i$ lies between $r_j$ and $r_{j+1}$ in this order. Then $$ u \in \left\{ \operatorname{lca}(x_i, r_j), \operatorname{lca}(x_i, r_{j+1}) \right\}. $$ To prove this, first observe that $u = \operatorname{lca}(x_i, r_t)$ for some red vertex $r_t$. Indeed, take any red vertex in the subtree of $u$. It cannot belong to the child of $u$ that contains $x_i$, because otherwise that child would be a lower valid ancestor than $u$. Therefore $$ \operatorname{lca}(x_i, r_t) = u. $$ Now suppose $$ u = \operatorname{lca}(x_i, r_t) $$ for some $t < j$. By considering Euler-tour order, one can verify that $$ depth(\operatorname{lca}(x_i, r_t)) \le depth(\operatorname{lca}(x_i, r_j)). $$ Hence if $\operatorname{lca}(x_i, r_t)$ is a valid candidate, then so is $\operatorname{lca}(x_i, r_j)$, and the latter is never higher. Therefore no vertex before $r_j$ can produce the desired answer. The same argument applies symmetrically to every $t > j+1$. Consequently, it is sufficient to check only the predecessor and successor of $x_i$ among the red vertices in Euler-tour order.19:["$","div",null,{"children":[["$","$L39",null,{"contestId":"6a126da3444ccfa6934559d1","contestType":"cp","contestNumber":10,"contestUrlId":"10","initialIsRegistered":false,"registrationClosed":true}],["$","$L3a",null,{"contest":{"contestNumber":10,"title":"Repovive Starter Round 2","startDate":"2026-05-31T14:35:00.000Z","endDate":"2026-05-31T16:35: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":"6a196e4937234fcd472c1aa2","contestId":"6a126da3444ccfa6934559d1","slug":"two-waves","title":"Two Waves","description":"There is an infinite tape of cells numbered $0, 1, 2, \\ldots$.\n\nTwo waves start at time $0$. The first wave starts from cell $a$, and the second wave starts from cell $b$.\n\nA wave reaches a neighboring cell in exactly $1$ second. More formally, the wave starting from cell $x$ reaches cell $y$ at time $|x-y|$.\n\nDetermine whether there exists a cell $c$ such that both waves reach cell $c$ at the same time.","constraints":"* $0 \\le a,b \\le 1000$","difficulty":"easy","order":1,"label":"$undefined","releaseDay":"$undefined","points":500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2 6\n","expectedOutput":"Yes","isSample":true,"hidden":false,"explanation":"Both waves reach cell 4 at time 2."},{"input":"3 8\n","expectedOutput":"No","isSample":true,"hidden":false,"explanation":"There is no cell whose distance from 3 is equal to its distance from 8."},{"input":"0 0\n","expectedOutput":"Yes","isSample":true,"hidden":false,"explanation":"Both waves start from cell 0, so they reach cell 0 at time 0."}],"sampleCount":3,"inputFormat":"$$$\na \\quad b\n$$\n","outputFormat":"Print `Yes` if there exists such a cell. Otherwise, print `No`.\n","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":140,"attemptedCount":141,"tags":["math"],"learnPages":[{"title":"Page 1) Black–White Coloring (Parity Invariant)","content":"1. Color the cells alternately:\n - Even-indexed cells: White\n - Odd-indexed cells: Black\n\n2. Each wave moves to a neighboring cell in exactly $1$ second.\n That means after every $1$ second, the wave changes its cell parity:\n - From even to odd, or from odd to even.\n In other words, the color flips every second.\n\n3. Suppose both waves reach the same cell `c` at the same time `t`.\n Then at time t, both waves must be on the same cell, hence on the same color.\n Since both flip color every second, this is only possible if they started on the same color.\n\nConclusion of Part 1:\n- A necessary condition is: `a` and `b` have the same parity (both even or both odd).\n- If `a` and `b` have different parity, answer is `No`.\n"},{"title":"Page 2) Distance Shrinks by 2 (Why the condition is also sufficient)","content":"1) If `a` and `b` have the same parity, then `|a - b|` is even.\n\n2) Imagine moving both waves toward each other symmetrically.\n After $1$ second:\n - The left one can move right by $1$\n - The right one can move left by $1$\n So the distance between them decreases by $2$ each second.\n\n3) Starting from an even distance, repeatedly subtracting $2$ will eventually reach $0$.\n That means there exists an integer “middle” cell `c` where they meet at the same time.\n\nConclusion of Part 2:\n- If a and b have the same parity -> `Yes` (a meeting cell exists).\n- Otherwise -> `No`.\n\nFinal Rule (Implementation logic):\n- Print `Yes` if (a and b have the same parity), else print `No`.\n\n"}],"hasLearnContent":true,"likeCount":43,"neutralCount":2,"dislikeCount":16,"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-05-29T10:45:29.627Z","updatedAt":"2026-08-20T14:44:35.849Z"},{"_id":"6a19825637234fcd472c1ac4","contestId":"6a126da3444ccfa6934559d1","slug":"class-photo-groups","title":"Class Photo Groups","description":"A school wants to split $n$ students into two photo groups.\n\nThe height of the $i$-th student is $a_i$.\n\nThe two groups must be non-empty. A group is called good if the difference between the tallest and the shortest student in that group is at most $d$.\n\nDetermine whether it is possible to split all students into two good groups.","constraints":"- $2 \\le n \\le 1000$\n- $0 \\le d \\le 10^6$\n- $1 \\le a_i \\le 10^6$","difficulty":"easy","order":2,"label":"$undefined","releaseDay":"$undefined","points":1000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5 3\n150 153 160 162 161\n","expectedOutput":"Yes","isSample":true,"hidden":false,"explanation":"One possible split is to put the students with heights $150$ and $153$ in one group, and the students with heights $160$, $161$, and $162$ in the other group.\n\nBoth groups are good."},{"input":"5 3\n150 154 160 161 162\n","expectedOutput":"No","isSample":true,"hidden":false,"explanation":"The students with heights $160$, $161$, and $162$ can form a good group.\n\nHowever, the remaining heights $150$ and $154$ differ by more than $d$.\n\nNo split makes both groups good."},{"input":"4 0\n170 180 170 180\n","expectedOutput":"Yes","isSample":true,"hidden":false,"explanation":"One group can contain the two students with height $170$, and the other group can contain the two students with height $180$.\n\nIn both groups, the tallest and shortest students have the same height, so the difference is $0$."}],"sampleCount":3,"inputFormat":"$$$\nn \\quad d\n$$\n\n$$\na_1 \\quad a_2 \\quad \\cdots \\quad a_n\n$$","outputFormat":"Print `Yes` if it is possible to split the students into two good groups.\n\nOtherwise, print `No`.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":129,"attemptedCount":130,"tags":["sortings"],"learnPages":[{"title":"Page 1) Visualize on a line + what makes a group “good”","content":"Think of heights as points on a number line.\nA group is “good” iff $($`max height in the group`$) - ($`min height in the group`$) \\leq d$.\n\nKey observation:\nFor checking goodness, the internal arrangement does not matter at all; only the minimum and maximum of that group matter.\n\nSo the whole problem is:\nCan we color each student either color $1$ or color $2$ (both colors non-empty) such that:\n$(max_1 - min_1 \\leq d) \\land (max_2 - min_2 \\leq d)$?"},{"title":"Page 2) Sort the heights (looking along the axis becomes easier)","content":"Sort the heights: $b_1 \\leq b_2 \\leq ... \\leq b_n$.\n\nAfter sorting, any group’s minimum and maximum are just “some earlier element” and “some later element” in this order.\nSo you can reason only with indices and intervals on the sorted line.\n\nThis is the main simplification:\nInstead of considering all $2^n$ splittings, we exploit that only the extreme endpoints of each color matter, and sorting makes endpoints easy to track.\n"},{"title":"Page 3) The “no 1-2-1 pattern” idea (why we can restrict the form of a solution)","content":"$3b"},{"title":"Page 4) Reduce the search to choosing one cut position","content":"Because the solution can be assumed to be two contiguous blocks after sorting,\nit is enough to choose the last index of group 1 (the cut):\n\nChoose p where $1 \\leq p \\leq n-1$:\n- Group 1 = $\\{b_1, b_2, ..., b_p\\}$\n- Group 2 = $\\{b_{p+1}, ..., b_n\\}$\n\nThen both groups are automatically non-empty.\n\nNow checking “good” becomes `O(1)` per cut:\n- Group 1 is good iff $b_p - b_1 \\le d$\n- Group 2 is good iff $b_n - b_{p+1} \\le d$\n\nSo:\nAnswer is `Yes` if there exists `p` with\n$(b_p - b_1 \\leq d) \\land (b_n - b_{p+1} \\leq d)$,\notherwise `No`.\n"},{"title":"Page 5) Complexity + why it is efficient","content":"Brute force is $2^n$, impossible.\n\nWith the sorted-block structure:\n- Sorting: `O(n log n)`\n- Try all cuts `p = 1..n-1`: `O(n)`\n- Each cut check is constant time (just endpoints)\n\nTotal: `O(n log n)`, easily within limits for $n \\leq 1000$.\n\nImplementation logic (no code):\n1) Read `n`, `d` and the array.\n2) Sort heights.\n3) For each cut position `p` from `1` to `n-1`:\n - Check range of first block: $b[p] - b[1] \\leq d$\n - Check range of second block: $b[n] - b[p+1] \\leq d$\n - If both true, print `Yes` and stop\n4) If no cut works, print `No`.\n\n\n\n"}],"hasLearnContent":true,"likeCount":43,"neutralCount":3,"dislikeCount":9,"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-05-29T12:11:02.403Z","updatedAt":"2026-08-20T14:44:19.161Z"},{"_id":"6a1b2ae1e2df64a7a91be620","contestId":"6a126da3444ccfa6934559d1","slug":"hannah-brain","title":"Hannah's Brain","description":"Hannah has $n$ CPUs. The $i$-th CPU initially has $a_i$ cores.\n\nIn one operation, she chooses one CPU with $x$ cores and splits it into two CPUs with positive integer numbers of cores $y$ and $x-y$, where $1 \\le y < x$.\n\nAfter performing some number of operations, Hannah wants all remaining CPUs to have the same number of cores.\n\nFind the minimum number of operations required.","constraints":"- $1 \\le n \\le 5\\,000$\n- $1 \\le a_i \\le 5\\,000$","difficulty":"easy","order":3,"label":"$undefined","releaseDay":"$undefined","points":1500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2\n2 6\n","expectedOutput":"2","isSample":true,"hidden":false,"explanation":"First, split the CPU with 6 cores into two CPUs with 4 and 2 cores. Then split the CPU with 4 cores into two CPUs with 2 and 2 cores."},{"input":"3\n3 3 3\n","expectedOutput":"0","isSample":true,"hidden":false,"explanation":"All CPUs already have the same number of cores; no splits are needed."}],"sampleCount":2,"inputFormat":"$$$n$$\n\n$$a_1 \\quad a_2 \\quad \\ldots \\quad a_n$$","outputFormat":"$$$\\text{ans}$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":115,"attemptedCount":119,"tags":["math","number theory"],"learnPages":[{"title":"Page 1) A target value x must divide every initial CPU","content":"Let the final common number of cores be `x`.\n\nA split operation never changes the total number of cores; it only breaks one CPU into two smaller positive integers.\nSo if a CPU with value $a_i$ is eventually turned into several CPUs all equal to `x`, then $a_i$ must be representable as:\n$x + x + ... + x$\nwhich means $a_i$ must be divisible by `x`.\n\nTherefore, a necessary condition for making all remaining CPUs equal to `x` is:\n$x | a_i$ for every $i$.\n\nA simple special case:\nWe can always make everything equal to $1$, because every positive integer is divisible by $1$.\n\nSo the problem always has at least one valid target."},{"title":"Page 2) Why divisibility is also sufficient","content":"Now assume 'x' divides every $a_i$.\n\nThen each CPU of size $a_i$ can be split into exactly $a_i / x$ CPUs, each having `x` cores.\nThis is always possible: keep splitting until you break $a_i$ into pieces of size `x`.\n\nSo:\n- If `x` divides every $a_i$, then making all CPUs equal to `x` is possible.\n- If `x` does not divide even one $a_i$, then making all CPUs equal to `x` is impossible.\n\nHence we get the exact criterion:\n\nIt is possible to make all final CPUs equal to `x`\niff\n`x` divides every $a_i$.\n\nThat means the only candidates for the final value are the common divisors of all numbers.\n"},{"title":"Page 3) Why “not divisible” can never be fixed by splitting","content":"This is the key impossibility proof.\n\nSuppose some CPU has `x` cores modulo-wise “bad”, meaning it is not divisible by the target `x`.\nCan one split operation fix this forever?\n\nTake a CPU of size `A` that is not divisible by `x`.\nAfter one split:\n$A = y + (A - y)$\n\nAssume, for contradiction, that both resulting parts are divisible by `x`.\nThen:\n$x | y$\nand\n$x | (A - y)$\n\nAdding them gives:\n$x | y + (A - y) = A$\n\nBut that says `A` is divisible by `x`, contradiction.\n\nSo whenever a non-divisible CPU is split, at least one of the children is still non-divisible by `x`.\nTherefore, once such a “bad” CPU exists, you can never get rid of all bad CPUs.\nSo reaching a state where every remaining CPU equals `x` is impossible.\n\nThis proves the “only if” direction rigorously."},{"title":"Page 4) If x is valid, how many operations are needed?","content":"Assume x divides every ai.\n\nA CPU of size $a_i$ will finally become exactly $a_i / x$ CPUs of size `x`.\n\nImportant fact:\nStarting from 1 CPU, to end up with `k` CPUs, you need exactly `k-1` splits,\nbecause each split increases the number of CPUs by exactly 1.\n\nSo for the i-th CPU:\nrequired operations = $(a_i / x) - 1$\n\nSumming over all CPUs:\n\ntotal operations\n\n$= \\sum_{i=1}^{n} (ai / x) - 1$\n\n$= (\\sum a_i) / x - n$\n\nIf we denote:\n$S = a_1 + a_2 + ... + a_n$\n\nthen for any valid target $x$,\noperations $= S / x - n$"},{"title":"Page 5) Which valid x is best?","content":"Now $S$ and $n$ are fixed.\nSo the expression\n$S / x - n$\ngets smaller when $x$ gets larger.\n\nTherefore, among all valid targets $x$, we want the largest possible one.\n\nAnd the largest integer dividing every $a_i$ is exactly:\n$gcd(a_1, a_2, ..., a_n)$\n\nSo the optimal final value is the $gcd$ of all CPUs.\n\nHence the minimum number of operations is:\n$S / gcd(a_1, a_2, ..., a_n) - n$"},{"title":"Page 6) How to compute it","content":"There are two standard ways to think about computation:\n\n1) Brute-force divisors idea\nSince $a_i \\leq 5000$, you could try every $x$ from $1$ to $max(a_i)$,\ncheck whether $x$ divides all $a_i$,\nand among valid ones take the largest.\nThis works in `O(maxAi * n)`.\n\n2) Better idea: directly compute $gcd$\nCompute $g = gcd(a_1, a_2, ..., a_n)$, then answer is:\n$S / g - n$\n\nThis is the cleanest solution.\nUsing iterative $gcd$ gives roughly `O(n log(maxA))` time.\n\nFinal implementation logic (no code):\n1) Read `n` and the array.\n2) Compute the total sum `S`.\n3) Compute `g = gcd of all ai`.\n4) Print `S / g - n`.\n"}],"hasLearnContent":true,"likeCount":48,"neutralCount":0,"dislikeCount":5,"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":"69135650701a1372647a6f23","name":"Ali Barikbin"}],"statementOverrides":"$undefined","createdAt":"2026-05-30T18:22:25.379Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6a1aee8f89821e95fb3b548d","contestId":"6a126da3444ccfa6934559d1","slug":"ice-cream","title":"Ice Cream","description":"Hannah has $n$ ice creams. The $i$-th ice cream has initial volume $v_i$.\n\nEach second, the following steps happen in order:\n\n1. If all ice creams have volume $0$, Hannah wins immediately.\n2. Otherwise, if any ice cream has volume $0$, Hannah loses.\n3. All ice creams melt, so each ice cream loses $1$ unit of volume.\n4. If every ice cream now has volume strictly less than $k$, Hannah loses.\n5. Hannah picks exactly one ice cream with volume at least $k$ and licks it, reducing its volume by exactly $k$.\n\nDetermine whether Hannah can finish all the ice creams without losing.","constraints":"- $1 \\le n \\le 2 \\cdot 10^5$\n- $1 \\le k \\le 10^9$\n- $1 \\le v_i \\le 10^9$","difficulty":"easy","order":4,"label":"$undefined","releaseDay":"$undefined","points":2000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2 2\n4 4\n","expectedOutput":"Yes","isSample":true,"hidden":false,"explanation":"After the first melting step, the volumes become $3$ and $3$. Hannah licks the first ice cream, so the volumes become $1$ and $3$.\n\nAfter the second melting step, the volumes become $0$ and $2$. Hannah licks the second ice cream, so both volumes become $0$.\n\nAt the start of the next second, all ice creams have volume $0$, so Hannah wins."},{"input":"1 1\n1\n","expectedOutput":"No","isSample":true,"hidden":false,"explanation":"After the first melting step, the only ice cream has volume $0$.\n\nNow every ice cream has volume strictly less than $k$, so Hannah loses before she can win."},{"input":"3 2\n2 4 4\n","expectedOutput":"Yes","isSample":true,"hidden":false,"explanation":"After the first melting step, the volumes become $1$, $3$, and $3$. Hannah licks one of the ice creams with volume $3$.\n\nAfter the second melting step, the volumes can become $0$, $0$, and $2$. Hannah licks the last ice cream with volume $2$, so all volumes become $0$.\n\nAt the start of the next second, Hannah wins."}],"sampleCount":3,"inputFormat":"$$$\nn \\quad k\n$$\n\n$$\nv_1 \\quad v_2 \\quad \\ldots \\quad v_n\n$$","outputFormat":"Print `Yes` if Hannah can finish all the ice creams without losing.\n\nOtherwise, print `No`.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":64,"attemptedCount":76,"tags":["math","number theory"],"learnPages":[{"title":"Page 1) Restate the process as a “resource accounting” game","content":"Let the volumes be $v_1, v_2, ..., v_n$.\n\nEach second, if the game does not end earlier, two kinds of decreases happen:\n1) Melting: every ice cream decreases by 1 -> total decrease = $n$\n2) Lick: exactly one ice cream decreases by $k$ -> total decrease = $k$\n\nSo in any full second that is actually played, the total sum of volumes decreases by exactly:\n$n + k$\n\nThis is a strong invariant to track the possibility of ever reaching total sum $= 0$ exactly at the start of some second.\n"},{"title":"Page 2) Necessary condition from the total sum (divisibility)","content":"Let $S = v_1 + v_2 + ... + v_n$.\n\nIf Hannah eventually wins, then at some moment all volumes become $0$ simultaneously.\nBetween the starts of consecutive seconds (i.e., after executing one full second), the total sum always decreases by exactly ($n + k$).\n\nTherefore, starting from $S$ and repeatedly subtracting $(n + k)$, reaching exactly $0$ requires:\n$S$ is divisible by $(n + k)$\n\nSo a necessary condition is:\n`S % (n + k) == 0`\n\nLet:\n$T = S / (n + k)$\nIf winning is possible, $T$ is exactly the number of seconds that must be played before the start of the winning second.\n\n(Reason: after $T$ full seconds, the sum becomes $S - T(n+k) = 0$, so at the start of the next second Hannah wins immediately.)\n"},{"title":"Page 3) Track each ice cream after T seconds (what must happen individually)","content":"Assume $S$ is divisible and define $T$ as above.\n\nIn each of the $T$ seconds:\n- every ice cream melts by 1, so each individual volume decreases by $T$ total from melting alone.\n\nAlso, exactly one ice cream is licked per second, so across all ice creams there are exactly T lick-actions total.\nIf ice cream $i$ is licked $t_i$ times, then:\n$t_1 + t_2 + ... + t_n = T$\nand ice cream $i$ loses an additional $k \\times t_i$ volume from licks.\n\nSo after $T$ seconds, ice cream $i$ becomes:\n$v_i - T - k \\times t_i$\n\nTo win exactly then, we need all final volumes to be $0$:\n$v_i - T - k \\times t_i = 0$\n--> $vi - T = k \\times t_i$\n\nThis gives two per-ice-cream requirements:\n1) $v_i \\geq T$ (otherwise $v_i - T$ is negative, impossible)\n2) $(v_i - T)$ must be divisible by $k$, and $t_i = (v_i - T)/k$\n\nSo the condition becomes:\nFor all $i$: $v_i \\geq T$ and `(vi - T) % k == 0`\n"},{"title":"Page 4) The “number of licks” must match exactly T","content":"Even if each $(v_i - T)$ is divisible by $k$, we also must have exactly $T$ licks total.\n\nBut if we set:\n\n$t_i = (v_i - T)/k$\n\nthen summing over $i$:\n\n$ \\sum t_i = \\sum(v_i - T)/k = (S - n.T)/k$\n\nUsing $S = T(n+k)$:\n\n$S - n.T = T(n+k) - n.T = T.k$\n\nSo:\n$\\sum t_i = (T.k)/k = T$\n\nSo the lick count constraint is automatically satisfied if:\n- $S$ is divisible by $(n+k)$, and\n- all $(vi - T)$ are non-negative multiples of $k$.\n\nThat means these conditions are not just necessary; together they fully match the required per-second lick budget.\n"},{"title":"Page 5) Why these conditions are also sufficient (constructive scheduling idea)","content":"Suppose:\n- `S % (n+k) == 0`, define $T = S/(n+k)$\n- For every $i$, $v_i \\geq T$ and `(vi - T) % k == 0`\n\nDefine $ti = (v_i - T)/k$ (a nonnegative integer).\nWe know sum $t_i = T$.\n\nNow schedule the game for exactly $T$ seconds:\n- On each second, after melting, lick any ice cream $i$ that still has remaining “lick quota” ($t_i$ not yet used up) and whose current volume is at least $k$.\nIntuition:\nBecause we planned exactly ti licks for each $i$, and total licks equal $T$, we can always pick one of the remaining quotas each second.\nAlso, the condition $v_i \\geq T$ ensures no ice cream hits $0$ before the end due to melting alone.\nAnd the equation $v_i - T = k \\times t_i$ ensures that after applying exactly $t_i$ licks across $T$ seconds, ice cream $i$ reaches exactly $0$ at the end.\n\nSo these arithmetic conditions guarantee a feasible strategy exists.\n"},{"title":"Page 6) Final check list (implementation logic, no code)","content":"1) Compute $S = \\sum v_i$.\n2) If `S % (n + k) != 0` -> print `No`.\n3) Else set $T = S / (n + k)$.\n4) For each $i$:\n - if $v_i < T$ -> print `No`\n - else if `(vi - T) % k != 0` -> print `No`\n5) If all pass -> print `Yes`\n\nComplexity:\n`O(n)`, works for $n$ up to $2e5$.\n\nNotes about edge cases:\n- $n = 1$ is handled naturally by the same checks.\n- Large $k$ and $v_i$ are fine since we only use sums and modular arithmetic with 64-bit integers.\n\n"}],"hasLearnContent":true,"likeCount":29,"neutralCount":1,"dislikeCount":1,"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":"6910edb50cda69581e13124c","name":"Hamid Shafi"}],"statementOverrides":"$undefined","createdAt":"2026-05-30T14:05:03.104Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6a1b45d8d6856c1c74d94d62","contestId":"6a126da3444ccfa6934559d1","slug":"l-toggle-table","title":"L-Toggle Table","description":"You are given a binary table with $n$ rows and $m$ columns.\n\nIn one operation, you choose one L-shaped tile and toggle all cells covered by it. \nToggling a cell means changing $0$ to $1$ and changing $1$ to $0$.\n\nEach tile covers exactly three cells. The tile is described by the coordinate of its center cell and one of the following four types.\n\nIf the center is $(x,y)$:\n\n| Type | Covered cells |\n| --- | --- |\n| $1$ | $(x,y)$, $(x+1,y)$, $(x,y+1)$ |\n| $2$ | $(x,y)$, $(x+1,y)$, $(x,y-1)$ |\n| $3$ | $(x,y)$, $(x-1,y)$, $(x,y+1)$ |\n| $4$ | $(x,y)$, $(x-1,y)$, $(x,y-1)$ |\n\nAll covered cells must be inside the table.\n\nYour task is to make all cells equal to $0$ using at most $4nm$ operations.\n\nIt can be proven that under the given constraints, such a sequence of operations always exists.","constraints":"- $2 \\le n,m \\le 100$\n- Each cell of the table is either $0$ or $1$","difficulty":"medium","order":5,"label":"$undefined","releaseDay":"$undefined","points":2500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2 3\n101\n010\n","expectedOutput":"3\n1 2 2\n2 2 3\n2 3 4","isSample":true,"hidden":false,"explanation":"Each operation toggles one valid L-shaped tile. After all listed operations, the whole table becomes zero."},{"input":"3 3\n010\n101\n010\n","expectedOutput":"2\n2 2 1\n2 2 4","isSample":true,"hidden":false,"explanation":"Initially, the table is:\n\n$$\n\\begin{array}{ccc}\n0 & 1 & 0 \\\\\n1 & 0 & 1 \\\\\n0 & 1 & 0\n\\end{array}\n$$\n\nAfter applying operation $(2,2,1)$, cells $(2,2)$, $(3,2)$, and $(2,3)$ are toggled. The table becomes:\n\n$$\n\\begin{array}{ccc}\n0 & 1 & 0 \\\\\n1 & 1 & 0 \\\\\n0 & 0 & 0\n\\end{array}\n$$\n\nAfter applying operation $(2,2,4)$, cells $(2,2)$, $(1,2)$, and $(2,1)$ are toggled. The table becomes:\n\n$$\n\\begin{array}{ccc}\n0 & 0 & 0 \\\\\n0 & 0 & 0 \\\\\n0 & 0 & 0\n\\end{array}\n$$\n\nSo the output is valid."}],"sampleCount":2,"inputFormat":"$$$\n\\begin{array}{l}\nn \\quad m \\\\\ns_1 \\\\\ns_2 \\\\\n\\vdots \\\\\ns_n\n\\end{array}\n$$\n\nHere $s_i$ is a binary string of length $m$, describing row $i$ of the table.","outputFormat":"First, output an integer $k$, the number of operations.\n\nThen output $k$ lines. Each line must contain three integers $x$, $y$, and $p$, meaning that you apply a tile with center $(x,y)$ and type $p$.\n\nFor every operation, the following must hold:\n\n- $1 \\le x \\le n$\n- $1 \\le y \\le m$\n- $1 \\le p \\le 4$\n\nAlso, all cells covered by the chosen tile must be inside the table.\n\n$$\n\\begin{array}{l}\nk \\\\\n\\left.\n\\begin{array}{l}\nx \\quad y \\quad p\n\\end{array}\n\\right\\} \\times k\n\\end{array}\n$$\n\nYour output must satisfy $0 \\le k \\le 4nm$.\n\nIf there are multiple valid answers, you may output any of them.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$3c"},"solvedCount":32,"attemptedCount":36,"tags":["constructive"],"learnPages":[{"title":"Page 1","content":"The key idea is to reduce the whole table to its bottom-right $2 \\times 2$ block.\n\nEach operation toggles exactly three cells forming an L-shape.\n\nInside any $2 \\times 2$ block, choosing any three of its four cells is always one valid L-shaped tile."},{"title":"Page 2","content":"First, clear the first $n-2$ rows.\n\nProcess rows from top to bottom.\n\nFor every cell $(i,j)$ with $1 \\le i \\le n-2$:\n\n- If $(i,j)$ is already $0$, do nothing.\n- If $(i,j)$ is $1$, apply one operation that includes $(i,j)$ and two cells in row $i+1$.\n\nThis makes $(i,j)$ equal to $0$.\n\nAll other changed cells are in lower rows, so after we finish a row, it will never be changed again."},{"title":"Page 3","content":"Now clear the first $m-2$ columns of the last two rows.\n\nAt this point, only the last two rows may still contain $1$ cells.\n\nProcess columns from left to right.\n\nFor each $j$ with $1 \\le j \\le m-2$:\n\n- If $(n-1,j)$ is $1$, apply one operation that includes this cell and only changes cells in columns $j$ and $j+1$.\n- If $(n,j)$ is $1$, do the same for this cell.\n\nEach operation fixes the current cell and only affects later columns.\n\nSo after this part, all cells outside the bottom-right $2 \\times 2$ block are zero."},{"title":"Page 4","content":"It remains to solve the bottom-right $2 \\times 2$ block.\n\nLet $c$ be the number of $1$ cells in this block.\n\nWe repeat the following until $c=0$:\n\n- If $c=3$, toggle exactly the three $1$ cells. Then all of them become $0$.\n- If $c=4$, toggle any three $1$ cells. Then $c$ becomes $1$.\n- If $c=2$, toggle one $1$ cell and two $0$ cells. Then $c$ becomes $3$.\n- If $c=1$, toggle the only $1$ cell and two $0$ cells. Then $c$ becomes $2$.\n\nTherefore:\n\n- $1 \\to 2 \\to 3 \\to 0$\n- $2 \\to 3 \\to 0$\n- $4 \\to 1 \\to 2 \\to 3 \\to 0$\n\nSo the final block needs at most $4$ operations."},{"title":"Page 5","content":"After clearing the first $n-2$ rows, those rows are never touched again.\n\nAfter clearing the first $m-2$ columns of the last two rows, all cells outside the bottom-right $2 \\times 2$ block are zero.\n\nThe remaining $2 \\times 2$ block can always be cleared, because any three cells in it form a valid L-shaped tile.\n\nTherefore, the algorithm always makes the whole table equal to zero."},{"title":"Page 6","content":"The number of operations is small enough.\n\nThe first part uses at most $(n-2)m$ operations.\n\nThe second part uses at most $2(m-2)$ operations.\n\nThe last $2 \\times 2$ block uses at most $4$ operations.\n\nSo the total number of operations is at most\n\n$$\n(n-2)m + 2(m-2) + 4 = nm.\n$$\n\nSince $nm \\le 4nm$, the required limit is always satisfied."},{"title":"Page 7","content":"The algorithm scans the table and creates at most $O(nm)$ operations.\n\nTherefore, the time complexity is $O(nm)$."}],"hasLearnContent":true,"likeCount":16,"neutralCount":0,"dislikeCount":3,"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":"6910e97ff1adda1971305d31","name":"Hamed Ghaffari"}],"statementOverrides":"$undefined","createdAt":"2026-05-30T20:17:28.607Z","updatedAt":"2026-08-20T14:44:12.339Z"},{"_id":"6a1b3eda2f0aebbb855f683a","contestId":"6a126da3444ccfa6934559d1","slug":"pair-increment-ranges","title":"Pair Increment Ranges","description":"You are given two arrays $a_1, a_2, \\ldots, a_n$ and $b_1, b_2, \\ldots, b_n$.\n\nAn interval $[l,r]$ with $1 \\le l \\le r \\le n$ is called beautiful if it is possible to make $a_i = b_i$ for every $l \\le i \\le r$ using the following operation any number of times:\n\nChoose an index $i$ such that $l < i \\le r$, then decrease $a_{i-1}$ by $1$ and increase $a_i$ by $1$.\n\nThe operation affects only the current interval $[l,r]$.\n\nFor each test case, output the number of beautiful intervals.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $0 \\le a_i, b_i \\le 10^9$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$","difficulty":"medium","order":6,"label":"$undefined","releaseDay":"$undefined","points":3000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n1\n5\n5\n2\n1 0\n0 1\n3\n2 0 0\n0 1 1\n4\n1 2 1 2\n1 2 1 2\n5\n2 0 0 1 0\n0 1 1 0 1\n","expectedOutput":"1\n1\n1\n10\n3","isSample":true,"hidden":false,"explanation":"The only beautiful interval is $[1,1]$, because the two arrays are already equal there.\n`\nThe only beautiful interval is $[1,2]$. By applying the operation once, the first element decreases by $1$ and the second element increases by $1$.\n`\nThe only beautiful interval is $[1,3]$. Apply the operation twice with $i=2$, then once with $i=3$.\n`\nEvery interval is beautiful, because the two arrays are already equal everywhere and we can use zero operations.\n`\nThe beautiful intervals are $[1,3]$, $[1,5]$, and $[4,5]$.","displayInput":"5\n`\n1\n5\n5\n`\n2\n1 0\n0 1\n`\n3\n2 0 0\n0 1 1\n`\n4\n1 2 1 2\n1 2 1 2\n`\n5\n2 0 0 1 0\n0 1 1 0 1","displayOutput":"1\n`\n1\n`\n1\n`\n10\n`\n3"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\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\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":23,"attemptedCount":30,"tags":["data structures","dp"],"learnPages":[{"title":"Page 1) Feasibility on a fixed interval [l, r]","content":"$3d"},{"title":"Page 2) Convert the condition using global prefix sums","content":"Let $P[0] = 0$ and\n $P[i] = \\sum_{t=1..i} (a[t] - b[t])$.\n\nFor any $l ≤ j ≤ r$:\n $\\sum_{i=l..j} (a[i]-b[i]) = P[j] - P[l-1]$.\n\nThus $[l, r]$ is beautiful iff:\n - for all $j$ in $[l, r-1]$: $P[j] - P[l-1] ≥ 0$ ⇔ $P[j] ≥ P[l-1]$\n - and $P[r] - P[l-1] = 0$ ⇔ $P[r] = P[l-1]$\n\nSo, fixing $l$ and letting $base = P[l-1]$:\n$r$ is valid iff:\n\n (A) $P[r] = base$\n\n (B) for every $j$ in $[l, r-1], P[j] ≥ base$\n\nMeaning: starting from $l$, the prefix sum never drops below base, and at $r$ it returns exactly to $base$.\n"},{"title":"Page 3) Next “drop below base” and what we must count","content":"Let $s = l-1$ (so $s$ is in $[0..n-1]$). We want to count $r$ such that:\n\n $s < r ≤ n$,\n\n $P[r] = P[s]$,\n\n and $P$ never goes below $P[s]$ on $(s, r-1)$.\n\nDefine:\n$A[s]$ = the first index $j > s$ with $P[j] < P[s]$ (first strictly smaller to the right)\n\nThen any valid endpoint must satisfy $r < A[s]$ (otherwise we would have dropped below the base first).\nSo the problem becomes:\n\nFor each $s$:\n count $r$ in $(s, A[s])$ such that $P[r] = P[s]$."},{"title":"Page 4) Two jump pointers (strictly smaller vs non-greater)","content":"Besides $A[s]$, define:\n\n$M[s] = $ the first index $j > s$ with $P[j] ≤ P[s]$ (first non-greater to the right)\n\nImportant fact:\n- If `M[s] == A[s]`, then the first time we reach $≤$ is already $<$, so there is NO equality $P[r]=P[s]$\n before dropping below. Hence there are zero valid endpoints for this $s$.\n- If $M[s] != A[s]$, then necessarily $P[M[s]] = P[s]$ (the first non-greater is actually equal),\n and $M[s]$ is the first valid endpoint.\n\nWe can compute $A$ and $M$ from right to left using DSU-style jumping:\ninitialize $A[i]=M[i]=i+1$ and keep jumping with already-computed pointers.\nAdd a sentinel $P[n+1] = -INF$ to guarantee termination.\n\nTransitions:\n\n$A[i]$:\n while $P[i] ≤ P[A[i]]$: $A[i] = A[A[i]]$\n\n$M[i]$:\n while $P[i] < P[M[i]]$: $M[i] = M[M[i]]$\n\nAfter these loops:\n $P[A[i]] < P[i]$ and $A[i]$ is the first such position\n $P[M[i]] ≤ P[i]$ and $M[i]$ is the first such position\n"},{"title":"Page 5) DP counting endpoints without any searching","content":"Let $dp[s] =$ number of valid endpoints $r$ for this start $s$ (i.e., number of beautiful intervals with $l=s+1$).\n\nCase 1) `M[s] == A[s]`\nWe drop below before any equality appears ⇒ $dp[s] = 0$.\n\nCase 2) `M[s] != A[s]`\nThen $r = M[s]$ is a valid endpoint (we returned to the baseline before dropping below).\nNow consider any further valid endpoint $r_2 > M[s]$.\nFrom $s$ to $r_2$ we never go below $P[s]$, and since $P[M[s]] = P[s]$,\n\nthe same condition from $M[s]$ to $r_2$ is exactly the “valid endpoints starting at M[s]” problem.\nSo the remaining endpoints are counted by $dp[M[s]]$.\n\nTherefore:\n $dp[s] = 1 + dp[M[s]]$.\n\nCompute dp from right to left (so $dp[M[s]]$ is already known), and sum:\n answer = $sum_{s=0..n-1} dp[s]$.\n\nEach $s$ corresponds to $l=s+1$, and each counted endpoint corresponds to one beautiful interval $[l, r]$.\n"},{"title":"Page 6) Complexity and implementation skeleton","content":"- Build $P$: $P[0]=0$, $P[i]=P[i-1]+(a[i]-b[i])$\n- Append `P.push_back(-1e18)` as sentinel at index $n+1$\n- Iterate $i$ from $n$ down to $0$:\n- $low[i]=leq[i]=i+1$\n- while $(P[i] \\leq P[low[i]])$: $low[i]=low[low[i]]$ // next strictly smaller\n- while $(P[i] < P[leq[i]])$: $leq[i]=leq[leq[i]]$ // next non-greater\n- if $(low[i]==leq[i])$ $dp[i]=0$;\n- else $dp[i]=dp[leq[i]]+1$;\n- $ans =ans+ dp[i]$\n- Print $ans$\n\n\nBuilding $P$: `O(n)`\n\nComputing $leq$ and $low$ with jump pointers: `O(n)` amortized\n\nComputing $dp$ and summing: `O(n)`\n\nTotal: `O(n)` per test case, with $sum(n) ≤ 2e5$."}],"hasLearnContent":true,"likeCount":20,"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":"6910e97ff1adda1971305d31","name":"Hamed Ghaffari"}],"statementOverrides":"$undefined","createdAt":"2026-05-30T19:47:38.435Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6a1c1af7b3d9d00197bdef37","contestId":"6a126da3444ccfa6934559d1","slug":"dynamic-tree-beauty","title":"Dynamic Tree Beauty","description":"$3e","constraints":"- $1 \\le t \\le 10^4$\n- $2 \\le n \\le 2 \\times 10^5$\n- $1 \\le q \\le 2 \\times 10^5$\n- $1 \\le p_i < i$\n- $2 \\le x \\le n$ for each query\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$\n- The sum of $q$ over all test cases is at most $2 \\times 10^5$","difficulty":"medium","order":7,"label":"$undefined","releaseDay":"$undefined","points":3500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n2 3\n1\n2 2 2\n3 3\n1 2\n2 3 2\n4 4\n1 1 1\n2 3 2 4\n5 4\n1 1 3 3\n4 5 2 4\n6 5\n1 1 2 2 3\n4 6 5 6 2\n","expectedOutput":"1 1 1\n3 2 4\n8 5 8 5\n24 14 8 14\n60 36 20 34 17","isSample":true,"hidden":false,"explanation":"There is only one non-root vertex. After each query, either it is red or it is the only vertex that may become blue, so the sum is always $1$.\n`\nAfter vertex $2$ becomes red, choosing vertex $3$ as blue or not gives beauties $2$ and $1$. After vertex $3$ also becomes red, both edges are needed. After vertex $2$ becomes white again, the path between vertices $1$ and $3$ still uses both edges in every blue choice.\n`\nThe tree is a star centered at vertex $1$. The beauty is exactly the number of colored leaves, so each query changes which leaves are already forced to be colored.\n`\nAfter the first query, vertex $4$ is red. For example, if neither vertex $2$ nor vertex $5$ is blue, the marked edges are the two edges on the path from $1$ to $4$. Summing over all blue choices gives the printed values.\n`\nIn the last query, vertex $2$ becomes red. Then vertices $1,2,4,5$ are red, and vertices $3,6$ are white. The four possible blue choices have beauties $3,5,4,5$, so the sum is $17$.","displayInput":"5\n`\n2 3\n1\n2 2 2\n`\n3 3\n1 2\n2 3 2\n`\n4 4\n1 1 1\n2 3 2 4\n`\n5 4\n1 1 3 3\n4 5 2 4\n`\n6 5\n1 1 2 2 3\n4 6 5 6 2","displayOutput":"1 1 1\n`\n3 2 4\n`\n8 5 8 5\n`\n24 14 8 14\n`\n60 36 20 34 17"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad q \\\\\np_2 \\quad p_3 \\quad \\cdots \\quad p_n \\\\\nx_1 \\quad x_2 \\quad \\cdots \\quad x_q\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\nans_1 \\quad ans_2 \\quad \\cdots \\quad ans_q\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":512,"checker":{"type":"wcmp"},"solvedCount":4,"attemptedCount":4,"tags":["trees","probabilities","math"],"learnPages":[{"title":"Page 1","content":"Instead of computing the **sum of beauties** directly, let us first compute the **expected beauty**."},{"title":"Page 2","content":"There are two types of edges:\n\n- **Edges with red vertices on both sides.** \n Such edges are always part of the beauty, so they contribute exactly $1$ to the expected beauty.\n\n- **Edges with red vertices on only one side.** \n For these edges, we need to determine the probability that they **do not** appear in the beauty."},{"title":"Page 3","content":"Consider an edge $e$ of the second type.\n\nThe only way $e$ does **not** appear in the beauty is if **every vertex on the side containing no red vertices remains uncolored**.\n\nIf that side contains $sz$ vertices, then the probability of this event is\n\n$$\n2^{-sz}.\n$$\n\nNow suppose $e$ connects $u$ and $p_u$. Since vertex $1$ is always red, the side without red vertices is exactly the subtree rooted at $u$. Therefore,\n\n$$\nsz = |subtree(u)|.\n$$\n\nHence an edge of the second type contributes\n\n$$\n1 - 2^{-sz}\n$$\n\nto the expected beauty."},{"title":"Page 4","content":"Therefore, it is enough to maintain\n\n$$\n\\sum 2^{-sz}\n$$\n\nover all edges whose subtree currently contains **no red vertex**.\n\nFor a query at vertex $x_i$, there are two possibilities:\n\n- If the subtree of $x_i$ already contains a red vertex other than $x_i$ itself, then toggling the color of $x_i$ changes nothing.\n- Otherwise, toggling $x_i$ affects exactly the edges on the path from $x_i$ upward until the first ancestor whose subtree already contains a red vertex.\n\nMore specifically:\n\n- If $x_i$ is white and becomes red, then some edges that previously had no red vertex in their subtree will now contain one.\n- If $x_i$ is red and becomes white, the same updates are applied in reverse.\n\nIn either case, the affected edges are exactly the ancestor edges of $x_i$ up to the lowest edge that already has a red vertex below it."},{"title":"Page 5","content":"$3f"},{"title":"Page 6","content":"The final solution maintains a variable\n\n$$\nsum = \\sum 2^{-sz},\n$$\n\ntaken over all edges whose subtree contains no red vertex.\n\nAfter each query, this value is updated using one of the two procedures described above.\n\nThe expected beauty is then\n\n$$\n(n - 1) - sum,\n$$\n\nsince there are exactly $n-1$ edges in the tree.\n\nIf $cnt$ denotes the number of white vertices, then there are\n\n$$\n2^{cnt}\n$$\n\npossible choices for the blue vertices. Therefore the required answer, namely the sum of beauties over all choices, is\n\n$$\n\\bigl((n - 1) - sum\\bigr)\\cdot 2^{cnt}\n\\pmod{998244353}.\n$$"}],"hasLearnContent":true,"likeCount":7,"neutralCount":1,"dislikeCount":1,"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":"6910dbd9f636aa34a20ab8b2","name":"Bahamin Shafaghi"}],"statementOverrides":"$undefined","createdAt":"2026-05-31T11:26:47.220Z","updatedAt":"2026-06-30T19:07:21.375Z"}],"contestId":"6a126da3444ccfa6934559d1","contestUrlId":"10","isAdmin":false,"isTester":false,"isStarted":true,"isRegistered":false,"canRegister":false,"problemStatusMap":{},"isPremiumBlocked":false,"sponsorshipSnapshot":"$18:props:children:props:children:1:props:children:0:props:sponsorshipSnapshot","recentRoundParticipantCounts":[104,428,97],"participationMode":null,"virtualStartTime":null,"contestDurationMs":7200000}]]}]

ATwo Waves	500	140/141
BClass Photo Groups	1000	129/130
CHannah's Brain	1500	115/119
DIce Cream	2000	64/76
EL-Toggle Table	2500	32/36
FPair Increment Ranges	3000	23/30
GDynamic Tree Beauty	3500	4/4