39:I[290370,["/_next/static/immutable/chunks/0_d-hjchaviu8.js","/_next/static/immutable/chunks/2v61o810dw1rf.js","/_next/static/immutable/chunks/0so_6hiupchv7.js","/_next/static/immutable/chunks/3b2h_bbz559px.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/2luv2orik4flv.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/3fo-xwmct_52g.js","/_next/static/immutable/chunks/37g2plzi61m9w.js","/_next/static/immutable/chunks/1fhnvrltjz3dq.js","/_next/static/immutable/chunks/3tit614wiqzli.js","/_next/static/immutable/chunks/0cxjiw1oj-yi4.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/0xcz7j92bzv8_.js","/_next/static/immutable/chunks/438uimm6zzysg.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/0_d-hjchaviu8.js","/_next/static/immutable/chunks/2v61o810dw1rf.js","/_next/static/immutable/chunks/0so_6hiupchv7.js","/_next/static/immutable/chunks/3b2h_bbz559px.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/2luv2orik4flv.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/3fo-xwmct_52g.js","/_next/static/immutable/chunks/37g2plzi61m9w.js","/_next/static/immutable/chunks/1fhnvrltjz3dq.js","/_next/static/immutable/chunks/3tit614wiqzli.js","/_next/static/immutable/chunks/0cxjiw1oj-yi4.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/0xcz7j92bzv8_.js","/_next/static/immutable/chunks/438uimm6zzysg.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:T443,**Scenario 1:** $n=3$, $a=[3, 4, 5]$. Sorted: $[3, 4, 5]$. The only triple is $(3, 4, 5)$: $3+4=7 > 5$, $3+5=8 > 4$, $4+5=9 > 3$. The array is already nice. No elements need to be removed. ` **Scenario 2:** $n=4$, $a=[1, 3, 4, 5]$. Sorted: $[1, 3, 4, 5]$. The triple $(1, 3, 5)$ fails: $1+3=4 \not> 5$. The longest nice subsequence is $[3, 4, 5]$ (length $3$): $3+4=7 > 5$. Remove $1$ element. Answer: $4 - 3 = 1$. ` **Scenario 3:** $n=6$, $a=[1, 1, 1, 10, 10, 10]$. Sorted: $[1, 1, 1, 10, 10, 10]$. The subset $[1, 10, 10, 10]$ is nice: every triple is of the form $(1, 10, 10)$ or $(10, 10, 10)$, and $1+10=11 > 10$ holds. This gives a nice subsequence of length $4$. No nice subsequence of length $5$ or $6$ exists (any two $1$s paired with a $10$ gives $1+1=2 \not> 10$). Answer: $6 - 4 = 2$. ` **Scenario 4:** $n=2$, $a=[1, 1000]$. With only $2$ elements, no triple of elements exists, so the array is trivially nice. Answer: $0$. ` **Scenario 5:** $n=4$, $a=[5, 5, 5, 5]$. All elements are equal. Every triple $(5, 5, 5)$ satisfies $5+5=10 > 5$. The array is already nice. Answer: $0$.3c:T45a,**Scenario 1:** $n=3$, intervals $[1,3], [2,4], [3,5]$. Answer: $1\ 2\ 3$. Witness: $a = [1, 2, 3]$. Reading in permutation order: $a_1=1 \le a_2=2 \le a_3=3$. All values in range. The identity permutation works because the intervals already overlap in increasing order. All $6$ permutations are valid (intervals overlap heavily), but $1\ 2\ 3$ is lexicographically smallest. ` **Scenario 2:** $n=3$, intervals $[5,7], [1,3], [2,4]$. Answer: $2\ 3\ 1$. Witness: $a = [5, 1, 2]$. Reading in permutation order: $a_2=1 \le a_3=2 \le a_1=5$. Interval $1$ has high values $[5,7]$ while intervals $2,3$ have low values, so index $1$ must come last. Only $2$ valid permutations exist: $2\ 3\ 1$ and $3\ 2\ 1$. Lexicographically smallest is $2\ 3\ 1$. ` **Scenario 3:** $n=4$, intervals $[2,4], [1,3], [5,7], [1,2]$. Answer: $1\ 2\ 4\ 3$. Witness: $a = [2, 2, 5, 2]$. Reading in permutation order: $a_1=2 \le a_2=2 \le a_4=2 \le a_3=5$. Interval $3=[5,7]$ has high values so must come last. Among the remaining, index $4=[1,2]$ fits before $3$. There are $6$ valid permutations; $1\ 2\ 4\ 3$ is lexicographically smallest.3d:T4d4,Let $c$ be a centroid of the tree: a vertex such that every subtree (when the tree is rooted at $c$) has size $\le \lfloor n/2 \rfloor$. Every tree has at least one centroid. Root the tree at $c$. Label the subtree sizes of $c$'s children as $s_1 \ge s_2 \ge \cdots \ge s_d$ where $d = \deg(c)$. By the centroid property, $s_i \le \lfloor n/2 \rfloor$ for all $i$. Cutting the edge from $c$ to the root of subtree $i$ separates that subtree (size $s_i$) from the component containing $c$. Cutting edges to the $k$ largest subtrees (for $k \le d$) leaves $c$ in a component of size $n - (s_1 + \cdots + s_k)$, while each separated subtree has size $\le s_1 \le \lfloor n/2 \rfloor$. Centroid-edges are always optimal. If an edge $e$ strictly inside subtree $T_i$ is cut without cutting $T_i$'s root-edge, the root of $T_i$ stays connected to $c$, so $c$'s component does not shrink. If both $T_i$'s root-edge and an internal edge of $T_i$ are cut, those 2 cuts split one subtree into two pieces, reducing $c$'s component by $s_i$. Cutting two root-edges (of $T_i$ and $T_j$, $j \ne i$) instead reduces $c$'s component by $s_i + s_j$, which is at least as good. So cutting centroid-edges in order of decreasing subtree size is optimal.3e:T40e,Let $P_k = s_1 + s_2 + \cdots + s_{\min(k, d)}$ be the prefix sum of the sorted subtree sizes. After cutting $\min(k, d)$ centroid-edges, the component containing $c$ has size $n - P_{\min(k,d)}$. Every other component has size $\le s_1 \le \lfloor n/2 \rfloor$. - While $P_k < \lceil n/2 \rceil$: the centroid's component has size $n - P_k > \lfloor n/2 \rfloor \ge s_1$, so it is the unique largest component and $f(k) = n - (n - P_k) = P_k$. - Once $P_k \ge \lceil n/2 \rceil$: the centroid's component has size $\le \lfloor n/2 \rfloor$, and all separated subtrees also have size $\le \lfloor n/2 \rfloor$, so $f(k) = \lfloor n/2 \rfloor$. When $k \ge d$, all centroid-edges are cut and the centroid is isolated (component size 1). Every remaining component is a full subtree of size $\le \lfloor n/2 \rfloor$. Cutting additional edges inside subtrees can only keep or reduce component sizes, so $f(k) = \lfloor n/2 \rfloor$ for all $k \ge d$. The final formula: $$f(k) = \min\!\big(P_{\min(k,\,d)},\; \lfloor n/2 \rfloor\big).$$19:["$","div",null,{"children":[["$","$L39",null,{"contestId":"69936951c54170e0611396c9","contestType":"cp","contestNumber":4,"contestUrlId":"4","initialIsRegistered":false,"registrationClosed":true}],["$","$L3a",null,{"contest":{"contestNumber":4,"title":"Repovive Standard Round 1","startDate":"2026-03-02T14:35:00.000Z","endDate":"2026-03-02T16:35:00.000Z","urlSlug":"$undefined","problemDisplay":"letters","requiresPremium":false,"lobbyProblemsCount":6,"isProblemSet":false,"contestType":"cp","adminOnly":false,"isWeeklyChallenge":false,"weekNumber":"$undefined","ratedMaxTier":"$undefined","announcements":[]},"problems":[{"_id":"69a0c94ec7fda3477ca4b96c","contestId":"69936951c54170e0611396c9","slug":"pouri-less-parham","title":"Pouri is less than Parham","description":"You are given an integer $n$.\n\nYou have exactly $n$ apples, and you want to distribute all of them between two people: Pouri and Parham.\n\nLet $p$ be the number of apples given to Pouri and $q$ be the number of apples given to Parham. You must have:\n- $p + q = n$\n- $p \\le q$\n\nYour goal is to maximize $p$. Output this maximum possible value of $p$.\n\n## Constraints\n- $1 \\le n \\le 1000$","constraints":"$undefined","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\n","expectedOutput":"1","hidden":false,"isSample":true},{"input":"3\n","expectedOutput":"1","hidden":false,"isSample":true}],"sampleCount":2,"inputFormat":"$$\nn\n$","outputFormat":"$$\n\\max p\n$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":95,"attemptedCount":96,"tags":["math"],"learnPages":[{"title":"Page 1","content":"Since $p + q = n$ and $p \\le q$, substituting $q = n - p$ gives\n$$\np \\le n - p,\n$$\nwhich rearranges to\n$$\n2p \\le n.\n$$\nSo we need $p \\le \\left\\lfloor \\dfrac{n}{2} \\right\\rfloor$."},{"title":"Page 2","content":"Setting $p = \\left\\lfloor \\dfrac{n}{2} \\right\\rfloor$ and $q = n - p$ satisfies both $p + q = n$ and $p \\le q$, so this value is achievable.\n\nThe answer is $\\left\\lfloor \\dfrac{n}{2} \\right\\rfloor$."}],"hasLearnContent":true,"likeCount":3,"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":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-02-26T22:29:34.536Z","updatedAt":"2026-06-28T22:22:26.596Z"},{"_id":"6998b2199e5cc443d8965816","contestId":"69936951c54170e0611396c9","slug":"not-k-consecutive","title":"Not K Consecutive","description":"You are given three integers $n$, $m$, and $k$.\n\nYou want to build a binary string $s$ of length $n+m$ that contains exactly $n$ characters equal to `0` and exactly $m$ characters equal to `1`.\n\nDetermine whether it is possible to build such a string so that there is **no** substring of length $k$ whose characters are all equal. \nIn other words, there must not exist an index $i$ such that $s_i = s_{i+1} = \\cdots = s_{i+k-1}$.\n\nPrint `Yes` if it is possible, otherwise print `No`.\n\n**Constraints:**\n- $1 \\le t \\le 10^4$\n- $1 \\le n, m, k \\le 10^4$","constraints":"$undefined","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":"3\n3 3 3\n7 2 3\n6 2 3\n","expectedOutput":"Yes\nNo\nYes\n","hidden":false,"displayInput":"3\n`\n3 3 3\n`\n7 2 3\n`\n6 2 3","displayOutput":"Yes\n`\nNo\n`\nYes","isSample":true}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad m \\quad k\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\text{ans}\n\\end{array}\n\\right\\} \\times t\n$$\n\nwhere $\\text{ans}$ is either `Yes` or `No`.","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":82,"attemptedCount":87,"tags":["math"],"learnPages":[{"title":"Page 1","content":"The $m$ ones partition the string into at most $m+1$ contiguous blocks of zeros (some may be empty). For the string to have no $k$ consecutive equal characters, each block must have length at most $k-1$. The total number of zeros is then at most $(m+1)(k-1)$, so a necessary condition is\n$$\nn \\le (m+1)(k-1).\n$$"},{"title":"Page 2","content":"By the same reasoning applied to the other character: the $n$ zeros create at most $n+1$ contiguous blocks of ones, each of length at most $k-1$, giving the second necessary condition\n$$\nm \\le (n+1)(k-1).\n$$\nBoth conditions together are sufficient. If they hold, spread the $n$ zeros into the $m+1$ positions so that each position receives at most $\\lceil n/(m+1) \\rceil \\le k-1$ zeros, and place the ones analogously."},{"title":"Page 3","content":"The answer is `Yes` if and only if\n$$\nn \\le (m+1)(k-1) \\quad \\text{and} \\quad m \\le (n+1)(k-1).\n$$"}],"hasLearnContent":true,"likeCount":6,"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-02-20T19:12:25.837Z","updatedAt":"2026-06-28T22:22:26.596Z"},{"_id":"6998b247feb81702039ebe0a","contestId":"69936951c54170e0611396c9","slug":"all-triangle","title":"All Triangles","description":"Consider a sequence $a_1, a_2, \\ldots, a_m$ of positive integers. \nWe call this sequence **nice** if for every choice of three **distinct** indices $i,j,k$, the lengths $a_i, a_j, a_k$ can be the side lengths of a (non-degenerate) triangle.\n\nYou are given an array $a_1, a_2, \\ldots, a_n$. Remove the minimum number of elements so that the remaining sequence becomes nice.\n\n## Constraints\n- $1 \\le t \\le 10^4$\n- $2 \\le n \\le 2 \\times 10^5$\n- $1 \\le a_i \\le 10^9$\n- The sum of $n$ over all test cases does not exceed $2 \\times 10^5$.","constraints":"$undefined","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":"5\n3\n3 4 5\n4\n1 3 4 5\n6\n1 1 1 10 10 10\n2\n1 1000\n4\n5 5 5 5\n","expectedOutput":"0\n1\n2\n0\n0\n","hidden":false,"displayInput":"5\n`\n3\n3 4 5\n`\n4\n1 3 4 5\n`\n6\n1 1 1 10 10 10\n`\n2\n1 1000\n`\n4\n5 5 5 5\n","displayOutput":"0\n`\n1\n`\n2\n`\n0\n`\n0\n","explanation":"$3b"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\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\\text{ans}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":62,"attemptedCount":76,"tags":["greedy","sortings"],"learnPages":[{"title":"Page 1","content":"Sort $a$. In a sorted sequence $b_1 \\le b_2 \\le \\cdots \\le b_m$ of positive integers, the triangle inequality for a triple $(b_i, b_j, b_k)$ with $i < j < k$ requires three conditions. Since all values are positive, $b_i + b_k > b_j$ and $b_j + b_k > b_i$ hold automatically. The only condition that can fail is\n$$\nb_i + b_j > b_k.\n$$\nThe hardest instance of this is $i=1$, $j=2$, $k=m$: if $b_1 + b_2 > b_m$ holds, then for any triple $b_i + b_j \\ge b_1 + b_2 > b_m \\ge b_k$, so every triple is satisfied.\n\nA sorted sequence is nice if and only if\n$$\na_1 + a_2 > a_m.\n$$"},{"title":"Page 2","content":"We want the longest contiguous subarray $[l, r]$ of the sorted array satisfying $a_l + a_{l+1} > a_r$ (subarrays of length at most $2$ are always nice since no triple of distinct indices exists).\n\nFor any nice subset of size $k$ at sorted positions $\\{p_1 < p_2 < \\cdots < p_k\\}$, consider the contiguous window $[p_k - k + 1,\\; p_k]$. Since $p_1 < p_2 < \\cdots < p_k$ are $k$ distinct integers, $p_k - p_j \\le k - j$, so $p_k - k + j \\ge p_j$ for all $j$. Therefore $a_{p_k-k+j} \\ge a_{p_j} = s_j$, and in particular\n$$\na_{p_k-k+1} + a_{p_k-k+2} \\ge s_1 + s_2 > s_k = a_{p_k},\n$$\nso the window is nice and has size $k$. The optimal subset is therefore always a contiguous window of the sorted array.\n\nTwo pointers find the longest such window in $O(n)$: for each right endpoint $r$, advance $l$ while $l + 1 < r$ and $a_l + a_{l+1} \\le a_r$."},{"title":"Page 3","content":"The answer is\n$$\nn - \\max_{l \\le r}\\,(r - l + 1),\n$$\nwhere the maximum is over all windows $[l, r]$ with $a_l + a_{l+1} > a_r$ or $r - l < 2$."}],"hasLearnContent":true,"likeCount":3,"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-02-20T19:13:11.893Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6998691e90c95a3db628bd74","contestId":"69936951c54170e0611396c9","slug":"max-by-min","title":"Max by Min","description":"You are given an array $a$ of length $n$.\n\nIn one operation, you choose a segment $[l,r]$ with $1 \\le l \\le r \\le n$, and then for every index $i$ such that $l < i < r$ you set\n$a_i = \\max\\!\\big(a_i,\\ \\min(a_l,\\ a_r)\\big)$.\n\nYou may apply the operation any number of times (possibly zero). Your goal is to maximize the sum $\\sum_{i=1}^{n} a_i$.\n\n## Constraints\n- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le a_i \\le 10^9$\n- The sum of $n$ over all test cases does not exceed $2 \\times 10^5$","constraints":"$undefined","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":"3\n2\n3 5\n5\n4 1 1 1 3\n6\n3 1 10 1 1 5\n","expectedOutput":"8\n16\n31\n","hidden":false,"displayInput":"3\n`\n2\n3 5\n`\n5\n4 1 1 1 3\n`\n6\n3 1 10 1 1 5\n","displayOutput":"8\n`\n16\n`\n31\n","explanation":"**Scenario 1:** Array: $[3, 5]$. No interior positions exist (need $l < i < r$, but only $2$ elements). No operations possible. Answer $= 3 + 5 = 8$.\n`\n**Scenario 2:** Array: $[4, 1, 1, 1, 3]$. Operation on $[1, 5]$: $\\min(4, 3) = 3$, raises all interior elements (indices $2, 3, 4$) from $1$ to $3$. Final array: $[4, 3, 3, 3, 3]$. Answer $= 4 + 3 + 3 + 3 + 3 = 16$.\n`\n**Scenario 3:** Array: $[3, 1, 10, 1, 1, 5]$. Operation on $[3, 6]$: $\\min(10, 5) = 5$, raises indices $4, 5$ from $1$ to $5$. Operation on $[1, 3]$: $\\min(3, 10) = 3$, raises index $2$ from $1$ to $3$. Final array: $[3, 3, 10, 5, 5, 5]$. Answer $= 3 + 3 + 10 + 5 + 5 + 5 = 31$."}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\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\\text{ans}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":68,"attemptedCount":70,"tags":["greedy","data structures"],"learnPages":[{"title":"Page 1","content":"Operations only increase values. To raise $a_i$ via an operation on $[l,r]$ with $l < i < r$, we need $\\min(a_l, a_r) > a_i$, requiring some value $\\ge v$ on each side.\n\nAny element $a_j$ with $j < i$ is bounded above by\n$$\nL_i = \\max_{j < i}\\, a_j\n$$\nthroughout all operations. This is because $a_j$ can be raised only via an operation $[l', r']$ with $l' < j < r'$, which requires values to the left of $j$ (bounded by $L_j \\le L_i$) and to the right. By induction, $a_j$ never exceeds $L_i$.\n\nBy the same argument, any $a_j$ with $j > i$ is bounded by $R_i = \\max_{j > i}\\, a_j$.\n\nSo the maximum achievable value of $a_i$ is at most\n$$\n\\max\\!\\left(a_i,\\; \\min(L_i, R_i)\\right).\n$$"},{"title":"Page 2","content":"This bound is always achievable in a single operation.\n\nLet $l^*$ be any index with $a_{l^*} = L_i$ and $r^*$ be any index with $a_{r^*} = R_i$. Apply the operation on $[l^*, r^*]$: every interior element (including $a_i$) is raised to at least\n$$\n\\min(a_{l^*},\\, a_{r^*}) = \\min(L_i, R_i).\n$$\nNo chaining of operations is needed."},{"title":"Page 3","content":"The maximum sum is\n$$\n\\sum_{i=1}^{n} \\max\\!\\bigl(a_i,\\; \\min(L_i, R_i)\\bigr),\n$$\nwhere $L_i = \\max(a_1, \\ldots, a_{i-1})$ and $R_i = \\max(a_{i+1}, \\ldots, a_n)$, with $L_1 = R_n = 0$.\n\nCompute $L_i$ in a single left-to-right pass and $R_i$ in a right-to-left pass, then evaluate the sum. Total time complexity is $O(n)$."}],"hasLearnContent":true,"likeCount":6,"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":"6910edb50cda69581e13124c","name":"Hamid Shafi"}],"statementOverrides":"$undefined","createdAt":"2026-02-20T14:01:02.613Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"699883229781d3530afdd996","contestId":"69936951c54170e0611396c9","slug":"permute-intervals","title":"Permute Intervals","description":"You are given $n$ closed intervals $[l_i, r_i]$.\n\nYou want to choose a permutation $p_1, p_2, \\ldots, p_n$ of $\\{1,2,\\ldots,n\\}$ such that there exists an array $a_1, a_2, \\ldots, a_n$ satisfying:\n\n- $l_i \\le a_i \\le r_i$ for each $1 \\le i \\le n$, \n- $a_{p_i} \\le a_{p_{i+1}}$ for each $1 \\le i < n$. \n\nAmong all permutations $p$ for which such an array $a$ exists, output the lexicographically smallest permutation.\n\nIt is guaranteed that at least one valid permutation exists.\n\n## Constraints\n\n- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le l_i \\le r_i \\le 10^9$","constraints":"$undefined","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":"3\n3\n1 3\n2 4\n3 5\n3\n5 7\n1 3\n2 4\n4\n2 4\n1 3\n5 7\n1 2\n","expectedOutput":"1 2 3\n2 3 1\n1 2 4 3\n","hidden":false,"displayInput":"3\n`\n3\n1 3\n2 4\n3 5\n`\n3\n5 7\n1 3\n2 4\n`\n4\n2 4\n1 3\n5 7\n1 2","displayOutput":"1 2 3\n`\n2 3 1\n`\n1 2 4 3\n","explanation":"$3c"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\nl_1 \\quad r_1 \\\\\nl_2 \\quad r_2 \\\\\n\\vdots \\\\\nl_n \\quad r_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\np_1 \\quad p_2 \\quad \\cdots \\quad p_n\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":28,"attemptedCount":34,"tags":["greedy","sortings"],"learnPages":[{"title":"Page 1","content":"Call a state $(v, S)$ **valid** if there exists an ordering of the remaining intervals $S$ such that, starting from running value $v$, each interval can be assigned a value in its range in non-decreasing order.\n\nSort $S$ by $r_i$. The greedy assignment sets $a_{s_k} = \\max(l_{s_k}, a_{s_{k-1}})$, so the running value after step $k$ is\n$$\nv_k = \\max\\bigl(v,\\, l_{s_1},\\, l_{s_2},\\, \\ldots,\\, l_{s_k}\\bigr).\n$$\nSince $l_{s_j} \\le r_{s_j} \\le r_{s_k}$ for all $j \\le k$, the condition $v_k \\le r_{s_k}$ reduces to $v \\le r_{s_k}$.\n\nA state $(v, S)$ is valid if and only if\n$$\nv \\le \\min_{j \\in S}\\, r_j.\n$$"},{"title":"Page 2","content":"Suppose the current state $(v, S)$ is valid. We want to place interval $i \\in S$ next.\n\nAfter placing $i$, the new running value is $v' = \\max(l_i, v)$, and the remaining set is $S' = S \\setminus \\{i\\}$. The new state $(v', S')$ must be valid:\n$$\n\\max(l_i, v) \\le r_i \\quad \\text{and} \\quad \\max(l_i, v) \\le \\min_{j \\in S'} r_j.\n$$\nBoth conditions together say $\\max(l_i, v) \\le \\min_{j \\in S} r_j$.\n\nSince the current state is valid, $v \\le \\min_{j \\in S} r_j$ already holds. So the binding condition is\n$$\nl_i \\le \\min_{j \\in S}\\, r_j.\n$$"},{"title":"Page 3","content":"At each step, the set of placeable intervals is exactly $\\{\\,i \\in S : l_i \\le r_{\\min}\\,\\}$ where $r_{\\min} = \\min_{j \\in S} r_j$.\n\nTo get the lexicographically smallest permutation, always pick the interval with the **smallest index** from this set.\n\nAfter placing $i$, the running value becomes $\\max(l_i, v)$ and $r_{\\min}$ is recomputed over the new $S$. Since removing an interval can only increase $r_{\\min}$, the eligible set can only grow between steps."},{"title":"Page 4","content":"Sort intervals by $l_i$. Maintain a min-heap $H$ (keyed by index) of eligible intervals, and a multiset $R$ of remaining $r$ values.\n\nInitially, add all intervals with $l_i \\le r_{\\min}$ to $H$.\n\nAt each step:\n1. Pop the minimum-index interval $i$ from $H$. Output $i$.\n2. Remove $r_i$ from $R$. The new $r_{\\min}$ is $\\min R$.\n3. Add all intervals not yet in $H$ with $l_i \\le$ new $r_{\\min}$ to $H$.\n\nEach interval is pushed and popped at most once, so the total time is $O(n \\log n)$."}],"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-02-20T15:52:02.648Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6998694f90c95a3db628bd75","contestId":"69936951c54170e0611396c9","slug":"path-conver-matching","title":"Path Cover Matching","description":"You are given a tree with $n$ vertices.\n\nFor each $k$ with $1 \\le k \\le n-1$, define $f(k)$ as follows.\n\nYou choose exactly $k$ edges of the tree and mark them. Then you construct a graph $G$ on the same $n$ vertices, where you add an edge between two distinct vertices $u$ and $v$ if and only if the unique simple path between $u$ and $v$ in the tree contains at least one marked edge.\n\nLet $\\nu(G)$ be the size of a maximum matching in $G$. \nThen $f(k)$ is the maximum possible value of $\\nu(G)$ over all choices of $k$ marked edges.\n\nFor each test case, output $f(1), f(2), \\ldots, f(n-1)$.\n\n## Constraints\n- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$","constraints":"$undefined","difficulty":"hard","order":6,"label":"$undefined","releaseDay":"$undefined","points":3000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n4\n1 2\n1 3\n1 4\n6\n1 2\n2 3\n3 4\n4 5\n5 6\n2\n1 2\n","expectedOutput":"1 2 2\r\n3 3 3 3 3\r\n1\r\n","hidden":false,"displayInput":"3\n`\n4\n1 2\n1 3\n1 4\n`\n6\n1 2\n2 3\n3 4\n4 5\n5 6\n`\n2\n1 2","displayOutput":"1 2 2\r\n`\n3 3 3 3 3\r\n`\n1","explanation":""}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\nu_1 \\quad v_1 \\\\\nu_2 \\quad v_2 \\\\\n\\vdots \\\\\nu_{n-1} \\quad v_{n-1}\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\nf(1)\\quad f(2)\\quad \\cdots \\quad f(n-1)\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":9,"attemptedCount":15,"tags":["trees","greedy","math"],"learnPages":[{"title":"Page 1","content":"Removing the $k$ marked edges from the tree splits the vertex set into $k+1$ connected components $C_1, C_2, \\ldots, C_{k+1}$.\n\nTwo vertices $u, v$ are adjacent in $G$ exactly when the unique $u$-$v$ path in the tree passes through at least one marked edge. This happens precisely when $u$ and $v$ lie in different components of the forest.\n\nSo $G$ is the complete multipartite graph $K_{|C_1|,\\, |C_2|,\\, \\ldots,\\, |C_{k+1}|}$, where each part is one connected component of the forest.\n\nThe problem reduces to: for each $k$, choose $k$ edges to remove so that the maximum matching of the resulting complete multipartite graph is maximized."},{"title":"Page 2","content":"Let the parts of a complete multipartite graph have sizes $s_1 \\ge s_2 \\ge \\cdots \\ge s_m$ with $n = \\sum s_i$. Any two vertices from distinct parts can be matched. The only constraint is that each vertex appears in at most one matched edge.\n\nIf $s_1 \\le \\lceil n/2 \\rceil$, a perfect or near-perfect matching exists: pair vertices greedily across parts to get $\\lfloor n/2 \\rfloor$ edges.\n\nIf $s_1 > \\lceil n/2 \\rceil$, each matched edge uses at most one vertex from the largest part, and the partner must come from the remaining $n - s_1$ vertices. So at most $n - s_1$ edges.\n\nThis gives\n\n$$\\nu(K_{s_1, \\ldots, s_m}) = \\min\\!\\big(n - s_1,\\; \\lfloor n/2 \\rfloor\\big).$$\n\nTo maximize $\\nu$ over all ways to remove $k$ edges, we need to minimize the largest component size. Writing $\\text{OPT}(k)$ for this minimum,\n\n$$f(k) = \\min\\!\\big(n - \\text{OPT}(k),\\; \\lfloor n/2 \\rfloor\\big).$$"},{"title":"Page 3","content":"$3d"},{"title":"Page 4","content":"$3e"},{"title":"Page 5","content":"Find the centroid by rooting the tree at any vertex, computing subtree sizes, and walking from the root toward any child whose subtree exceeds $\\lfloor n/2 \\rfloor$ until no such child exists.\n\nCollect the $d$ subtree sizes of the centroid's neighbors, sort them in decreasing order, and compute prefix sums $P_1, P_2, \\ldots, P_d$.\n\nFor each $k$ from $1$ to $n-1$, output $\\min(P_{\\min(k,d)},\\; \\lfloor n/2 \\rfloor)$.\n\nSubtree computation and centroid finding are $O(n)$. Sorting the subtree sizes is $O(d \\log d)$. The total complexity is $O(n \\log n)$ per test case."}],"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":"6910dbd9f636aa34a20ab8b2","name":"Bahamin Shafaghi"}],"statementOverrides":"$undefined","createdAt":"2026-02-20T14:01:51.317Z","updatedAt":"2026-06-28T22:22:26.596Z"}],"contestId":"69936951c54170e0611396c9","contestUrlId":"4","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":[180,109,434],"participationMode":null,"virtualStartTime":null,"contestDurationMs":7200000}]]}]

APouri is less than Parham	500	95/96
BNot K Consecutive	1000	82/87
CAll Triangles	1500	62/76
DMax by Min	2000	68/70
EPermute Intervals	2500	28/34
FPath Cover Matching	3000	9/15