35:I[290370,["/_next/static/immutable/chunks/0aneuidq2dd5s.js","/_next/static/immutable/chunks/3asdwddb65r_7.js","/_next/static/immutable/chunks/11qxjuvxxj8-v.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/3dqr5h54-q26k.js","/_next/static/immutable/chunks/20gnsl3b8ay94.js","/_next/static/immutable/chunks/2v6773b5v9j_y.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/03jf6lfc9r-so.js","/_next/static/immutable/chunks/1cty97j_3t4p8.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/29bm85rhaftys.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/36tubk3midieh.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/386n_qt61qywd.js","/_next/static/immutable/chunks/12nj9lbbxts99.js","/_next/static/immutable/chunks/2h62w_fdykycp.js","/_next/static/immutable/chunks/091zjp-oxk1vw.js","/_next/static/immutable/chunks/18bin06et1f2f.js","/_next/static/immutable/chunks/0q669txy1w1q5.js"],"default"] 36:I[218728,["/_next/static/immutable/chunks/0aneuidq2dd5s.js","/_next/static/immutable/chunks/3asdwddb65r_7.js","/_next/static/immutable/chunks/11qxjuvxxj8-v.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/3dqr5h54-q26k.js","/_next/static/immutable/chunks/20gnsl3b8ay94.js","/_next/static/immutable/chunks/2v6773b5v9j_y.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/03jf6lfc9r-so.js","/_next/static/immutable/chunks/1cty97j_3t4p8.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/29bm85rhaftys.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/36tubk3midieh.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/386n_qt61qywd.js","/_next/static/immutable/chunks/12nj9lbbxts99.js","/_next/static/immutable/chunks/2h62w_fdykycp.js","/_next/static/immutable/chunks/091zjp-oxk1vw.js","/_next/static/immutable/chunks/18bin06et1f2f.js","/_next/static/immutable/chunks/0q669txy1w1q5.js"],"default"] 37:T697,For vertex $2$, the shortest paths have length $1$. There is only one good path: edge-index sequence $[1]$, with vertex sequence $1 \to 2$. Therefore, there is no second good path. ` For vertex $2$, the shortest paths have length $1$. The first good path has edge-index sequence $[1]$, and the second one has edge-index sequence $[2]$. Both have vertex sequence $1 \to 2$, because the two edges are parallel. So the answer for vertex $2$ is $2$. For vertex $3$, the shortest paths have length $2$. The first good path has edge-index sequence $[1, 3]$, with vertex sequence $1 \to 2 \to 3$. The second one has edge-index sequence $[2, 3]$, also with vertex sequence $1 \to 2 \to 3$. So the answer for vertex $3$ is $2+3=5$. ` For vertex $4$, the shortest paths have length $2$. The first good path has edge-index sequence $[1, 3]$, with vertex sequence $1 \to 2 \to 4$. The second one has edge-index sequence $[2, 4]$, with vertex sequence $1 \to 3 \to 4$. So the answer for vertex $4$ is $2+4=6$. ` For vertex $4$, the first two good paths have edge-index sequences $[1, 3]$ and $[2, 4]$, so the answer is $2+4=6$. For vertex $5$, the first two good paths have edge-index sequences $[1, 5]$ and $[2, 6]$, so the answer is $2+6=8$. ` For vertex $2$, the first two good paths have edge-index sequences $[1]$ and $[2]$, so the answer is $2$. For vertex $4$, the first two good paths have edge-index sequences $[1, 3]$ and $[1, 4]$, so the answer is $1+4=5$. For vertex $5$, the first two good paths have edge-index sequences $[1, 3, 7]$ and $[1, 4, 7]$, so the answer is $1+4+7=12$. For vertex $6$, there is only one good path, with edge-index sequence $[5, 8]$, so the answer is $-1$.38:T42e,There are no pairs of indices, so the answer is $0$. ` The good pairs are $(1, 2)$. For $(1, 2)$, choose $[l,r]=[1,2]$. The sequence is $1,2$, and its median is $1$, which is at least $p_1=1$. ` There are no good pairs. The only pair is $(1, 2)$. The only possible interval is $[1,2]$. The sequence is $2,1$, and its median is $1$, which is smaller than $p_1=2$. ` The good pairs are $(1, 2)$, $(1, 3)$, and $(2, 3)$. For $(1, 2)$ and $(1, 3)$, choose $[l,r]=[1,3]$. The sequence is $2,1,3$, and its median is $2$, which is at least $p_1=2$. For $(2, 3)$, choose $[l,r]=[2,3]$. The sequence is $1,3$, and its median is $1$, which is at least $p_2=1$. ` The good pairs are $(1, 2)$, $(1, 3)$, $(2, 3)$, and $(2, 4)$. For $(1, 2)$ and $(1, 3)$, choose $[l,r]=[1,3]$. The sequence is $3,1,4$, and its median is $3$, which is at least $p_1=3$. For $(2, 3)$, choose $[l,r]=[2,3]$. The sequence is $1,4$, and its median is $1$, which is at least $p_2=1$. For $(2, 4)$, choose $[l,r]=[2,4]$. The sequence is $1,4,2$, and its median is $2$, which is at least $p_2=1$.39:T9ee,#include #include "testlib.h" using namespace std; string lower_string(string s) { for (char &c : s) c = char(tolower(c)); return s; } int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; tc++) { setTestCase(tc); int n = inf.readInt(); bool possible = (n != 3 && n % 3 != 2); string verdict = lower_string(ouf.readToken()); if (verdict != "yes" && verdict != "no") { quitf(_wa, "test case %d: expected Yes or No", tc); } if (!possible) { if (verdict != "no") { quitf(_wa, "test case %d: participant printed Yes, but no decomposition exists", tc); } continue; } if (verdict != "yes") { quitf(_wa, "test case %d: participant printed No, but a decomposition exists", tc); } long long expected_k = 1LL * n * (n - 1) / 6; long long k = ouf.readLong(0, 1000000000LL, "k"); if (k != expected_k) { quitf(_wa, "test case %d: expected %lld paths, found %lld", tc, expected_k, k); } vector> used(n + 1, vector(n + 1, 0)); for (long long i = 1; i <= k; i++) { int v[4]; for (int j = 0; j < 4; j++) { v[j] = ouf.readInt(1, n, "vertex"); } for (int a = 0; a < 4; a++) { for (int b = a + 1; b < 4; b++) { if (v[a] == v[b]) { quitf(_wa, "test case %d, path %lld: a P4 must contain four distinct vertices", tc, i); } } } for (int j = 0; j < 3; j++) { int a = v[j]; int b = v[j + 1]; if (a > b) swap(a, b); if (used[a][b]) { quitf(_wa, "test case %d, path %lld: edge %d-%d was used more than once", tc, i, a, b); } used[a][b] = 1; } } for (int a = 1; a <= n; a++) { for (int b = a + 1; b <= n; b++) { if (!used[a][b]) { quitf(_wa, "test case %d: edge %d-%d was not used", tc, a, b); } } } } if (!ouf.seekEof()) { quitf(_wa, "extra output tokens"); } quitf(_ok, "accepted"); }1b:["$","div",null,{"children":[["$","$L35",null,{"contestId":"6a1bac191ec01f4831a73ee1","contestNumber":11,"contestUrlId":"11","initialIsRegistered":false}],["$","$L36",null,{"contest":{"contestNumber":11,"title":"Repovive Standard Round 4","startDate":"2026-06-10T14:35:00.000Z","endDate":"2026-06-10T16:35:00.000Z","urlSlug":"$undefined","problemDisplay":"letters","requiresPremium":false,"lobbyProblemsCount":6,"isProblemSet":false,"contestType":"cp","adminOnly":false,"isWeeklyChallenge":"$undefined","weekNumber":"$undefined","ratedMaxTier":"$undefined","announcements":[]},"problems":[{"_id":"6a27453b4b94a2b05a09f95a","contestId":"6a1bac191ec01f4831a73ee1","slug":"notebook-page","title":"Notebook Page","description":"There is a notebook with pages numbered from $1$ to $n$ from left to right.\n\nOn each day, exactly one remaining page is read. The page must be one of the two ends of the remaining notebook, that is, either the leftmost remaining page or the rightmost remaining page.\n\nFor each test case, determine whether it is possible that page $x$ is read exactly on day $d$.\n\nThe order of reading pages can be chosen arbitrarily, as long as the rule above is followed.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le d, x \\le n \\le 10^9$","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":"5\n5 1 1\n5 1 3\n5 3 3\n7 2 6\n10 4 5\n","expectedOutput":"Yes\nNo\nYes\nYes\nNo","isSample":true,"hidden":false,"explanation":"The page is already at one end, so it can be chosen on the first day.\n`\nOn the first day, only pages $1$ and $5$ can be read, so page $3$ cannot be read.\n`\nFor example, pages $1$ and $2$ can be read first, then page $3$ is at an end on day $3$.\n`\nPage $7$ can be read first, then page $6$ becomes the right end on day $2$.\n`\nWe can prove that after 3 days, page $5$ cannot be at an end of unread pages.","displayInput":"5\n`\n5 1 1\n`\n5 1 3\n`\n5 3 3\n`\n7 2 6\n`\n10 4 5","displayOutput":"Yes\n`\nNo\n`\nYes\n`\nYes\n`\nNo"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\quad d \\quad x\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\texttt{Yes}\\ \\text{/}\\ \\texttt{No}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":96,"attemptedCount":102,"tags":["math","implementation"],"learnPages":[{"title":"Idea","content":"At any moment, the remaining pages always form one continuous segment.\n\nFor example, after reading some pages, the remaining notebook may look like pages $l, l+1, \\ldots, r$.\n\nOn the next day, we can only read page $l$ or page $r$."},{"title":"Key Observation","content":"Before day $d$, exactly $d-1$ pages have already been read.\n\nPage $x$ can be read on day $d$ only if, after these $d-1$ reads, it is at one of the two ends of the remaining segment."},{"title":"Making x the Left End","content":"To make page $x$ the leftmost remaining page, all pages before it must be read.\n\nThere are $x-1$ such pages.\n\nSo this is possible if $x-1 \\le d-1$, which is the same as $d \\ge x$."},{"title":"Making x the Right End","content":"To make page $x$ the rightmost remaining page, all pages after it must be read.\n\nThere are $n-x$ such pages.\n\nSo this is possible if $n-x \\le d-1$, which is the same as $d \\ge n-x+1$."},{"title":"Final Condition","content":"Therefore, page $x$ can be read on day $d$ if at least one of these two conditions holds:\n\n$d \\ge x$\n\nor\n\n$d \\ge n-x+1$.\n\nIf one of them is true, the answer is `Yes`.\n\nOtherwise, the answer is `No`."},{"title":"Algorithm","content":"For each test case:\n\n1. Read $n$, $d$, and $x$.\n2. If $d \\ge x$ or $d \\ge n-x+1$, print `Yes`.\n3. Otherwise, print `No`."},{"title":"Correctness","content":"If the algorithm prints `Yes`, then either all pages before $x$ can be read before day $d$, or all pages after $x$ can be read before day $d$.\n\nSo page $x$ can become one of the two ends of the remaining notebook on day $d$, and can be read on that day.\n\nIf the algorithm prints `No`, then fewer than $x-1$ pages can be read before $x$ from the left side, and fewer than $n-x$ pages can be read before $x$ from the right side.\n\nSo page $x$ cannot become either end before day $d$.\n\nTherefore, it is impossible to read page $x$ exactly on day $d$."},{"title":"Complexity","content":"Each test case is solved using only a constant number of comparisons.\n\nThe time complexity is $O(1)$ per test case.\n\nThe memory complexity is $O(1)$."}],"hasLearnContent":true,"likeCount":54,"neutralCount":1,"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-06-08T22:42:03.938Z","updatedAt":"2026-06-28T22:22:26.596Z"},{"_id":"6a289217386d02deeda35c3e","contestId":"6a1bac191ec01f4831a73ee1","slug":"prison-watch","title":"Prison Watch","description":"There are $n$ prison cells in a row, numbered from $1$ to $n$.\n\nThere is one guard in each cell. The direction of the guards is given by a string $s$ of length $n$.\n\n- If $s_i = L$, then guard $i$ sees every cell $j$ such that $1 \\le j \\le i$.\n- If $s_i = R$, then guard $i$ sees every cell $j$ such that $i \\le j \\le n$.\n\nIn particular, every guard sees their own cell.\n\nHiring guard $i$ costs $a_i$.\n\nFor each test case, find the minimum total cost needed to hire some guards so that every cell is seen by at least one hired guard.","constraints":"- $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$\n- $s_i \\in \\{L, R\\}$\n- $1 \\le a_i \\le 1000$","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\n1\nL\n7\n4\nRRRR\n5 2 9 4\n5\nLLLLL\n6 1 8 3 4\n4\nLLRR\n10 3 2 9\n7\nRLRLLRL\n100 7 6 20 2 1 90\n","expectedOutput":"7\n5\n4\n5\n3","isSample":true,"hidden":false,"explanation":"The only guard sees the only cell, so cost 7 is necessary.\n`\nOnly guard 1 can see cell 1 while facing right, and it also sees every cell. So the minimum cost is 5.\n`\nOnly guard 5 can see cell 5 while facing left, and it also sees every cell. So the minimum cost is 4.\n`\nHiring guard 2 and guard 3 covers cells 1, 2 and 3, 4 with total cost 5. No single guard sees all cells.\n`\nHiring guard 5 and guard 6 covers cells 1 through 5 and 6 through 7 with total cost 3, which is cheaper than either single guard that sees all cells.","displayInput":"5\n`\n1\nL\n7\n`\n4\nRRRR\n5 2 9 4\n`\n5\nLLLLL\n6 1 8 3 4\n`\n4\nLLRR\n10 3 2 9\n`\n7\nRLRLLRL\n100 7 6 20 2 1 90","displayOutput":"7\n`\n5\n`\n4\n`\n5\n`\n3"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\ns \\\\\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}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":80,"attemptedCount":87,"tags":["greedy","data structures","strings"],"learnPages":[{"title":"page 1","content":"The important point is that each hired guard covers one simple interval.\n\nA guard facing left covers a prefix of the row. A guard facing right covers a suffix of the row.\n\nSo the whole problem is about covering all cells using some prefixes and suffixes."},{"title":"page 2","content":"Suppose we hire some guards facing left.\n\nAmong them, only the rightmost one matters for coverage, because it sees the longest prefix. Keeping only this guard does not uncover any cell that was seen by another left-facing guard.\n\nSimilarly, among hired guards facing right, only the leftmost one matters."},{"title":"page 3","content":"Therefore, an optimal answer uses at most two useful guards.\n\nIt may use one guard if that guard alone sees all cells:\n\n- guard $1$ facing right\n- guard $n$ facing left\n\nOtherwise, it uses one left-facing guard and one right-facing guard."},{"title":"page 4","content":"Assume we choose a left-facing guard at position $i$ and a right-facing guard at position $j$.\n\nThe left-facing guard covers cells $1$ through $i$.\n\nThe right-facing guard covers cells $j$ through $n$.\n\nTogether they cover the whole row if and only if $j \\le i + 1$."},{"title":"page 5","content":"For every position $i$, compute the minimum cost of a right-facing guard among positions $1$ through $i$.\n\nCall this value $pref_i$.\n\nThen for each left-facing guard $i$, the best right-facing guard that can be paired with it has cost $pref_{i+1}$.\n\nCheck all such pairs, and also check the two possible one-guard answers.\n\nThe time complexity is $O(n)$ per test case."}],"hasLearnContent":true,"likeCount":42,"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":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-06-09T22:22:15.813Z","updatedAt":"2026-08-20T14:44:19.138Z"},{"_id":"6a273c684b94a2b05a09f958","contestId":"6a1bac191ec01f4831a73ee1","slug":"split-machine","title":"Split Machine","description":"You are given an array $a_1, a_2, \\ldots, a_n$.\n\nA machine receives a non-empty array and returns a number. For an array of length $1$, it returns $0$.\n\nFor an array of length greater than $1$, the machine chooses one of the boundaries between two consecutive elements and splits the array into two non-empty arrays $X$ and $Y$.\n\nThen the machine gets $f(X) + f(Y)$, and adds exactly one of the following two values to it:\n\n- $sum(X) + sum(Y)$\n- $sum(X) \\times sum(Y)$\n\nHere $sum(Z)$ denotes the sum of all elements of array $Z$.\n\nThe value $f(a)$ is the maximum possible final value over all choices of splits and added values.\n\nFor each test case, output $f(a)$.","constraints":"- $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$\n- $1 \\le a_i \\le 10^4$","difficulty":"medium","order":3,"label":"$undefined","releaseDay":"$undefined","points":1500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n1\n5\n2\n1 1\n3\n1 2 1\n","expectedOutput":"0\n2\n7","isSample":true,"hidden":false,"explanation":"The array has length $1$, so the machine returns $0$.\n\n`\n\nThere is only one split. The two sums are $1$ and $1$, so the best added value is $1 + 1 = 2$.\n\n`\n\nAn optimal splitting of the array is as follows:\n$\\{1, 2\\}$ and $\\{1\\}$. Then we have: $f(\\{1, 2\\})+f(\\{1\\})+max((1+2) \\times 1, (1+2) + 1)$ $=$ $3+0+4$ $=$ $7$.","displayInput":"3\n`\n1\n5\n`\n2\n1 1\n`\n3\n1 2 1","displayOutput":"0\n`\n2\n`\n7"}],"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}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":30,"attemptedCount":49,"tags":["math","combinatorics","greedy"],"learnPages":[{"title":"Idea","content":"The whole process can be seen as a binary splitting tree.\n\nEach internal node of this tree splits one segment into two parts $X$ and $Y$. If $sum(X)=x$ and $sum(Y)=y$, the machine adds either $x+y$ or $xy$.\n\nSo we only need to understand what the best choice is at each split."},{"title":"Main Observation","content":"Since all elements are positive, we always have $x \\ge 1$ and $y \\ge 1$.\n\nCompare the two possible added values:\n\n- $x+y$\n- $xy$\n\nIf both $x$ and $y$ are at least $2$, then $xy \\ge x+y$.\n\nThe only time $x+y$ is better than $xy$ is when one of $x,y$ is equal to $1$."},{"title":"Base Contribution","content":"Assume for a moment that we always add $sum(X) \\cdot sum(Y)$.\n\nConsider two elements $a_i$ and $a_j$. During the splitting process, there is exactly one split where these two elements become separated for the first time.\n\nAt that split, one of them is inside $X$ and the other one is inside $Y$, so the product $a_i a_j$ appears exactly once in $sum(X) \\cdot sum(Y)$.\n\nTherefore, the total base contribution is\n\n$\\sum_{1 \\le i < j \\le n} a_i a_j$."},{"title":"Extra Contribution","content":"Now consider when we can gain more by choosing $sum(X)+sum(Y)$ instead of $sum(X) \\cdot sum(Y)$.\n\nThis only helps when one side has sum $1$.\n\nBecause all $a_i \\ge 1$, a segment with sum $1$ must be exactly one element equal to $1$.\n\nFor such a split, if the two sums are $1$ and $z$, then\n\n$1+z = 1 \\cdot z + 1$.\n\nSo each useful split with a single element $1$ gives exactly one extra point."},{"title":"Counting the Extras","content":"Let $cnt_1$ be the number of elements equal to $1$.\n\nEach element equal to $1$ can give this extra point at most once, because after it becomes a single-element segment, it is never split again.\n\nAlso, the whole process has exactly $n-1$ splits.\n\nSo the number of extra points is at most $\\min(cnt_1,n-1)$.\n\nThis upper bound is achievable: we can split elements equal to $1$ one by one from the remaining segment whenever possible."},{"title":"Final Formula","content":"The answer is\n\n$\\sum_{1 \\le i < j \\le n} a_i a_j + \\min(cnt_1,n-1)$.\n\nThe first term counts the product contribution of every pair of elements.\n\nThe second term counts the maximum number of times we can get one extra point from a segment with sum $1$."},{"title":"Algorithm","content":"We process the array from left to right.\n\nMaintain $pref$, the sum of previous elements.\n\nWhen we read $a_i$, its contribution with all previous elements is $pref \\cdot a_i$.\n\nThen add $a_i$ to $pref$.\n\nAlso count how many elements are equal to $1$.\n\nFinally, add $\\min(cnt_1,n-1)$ to the answer."},{"title":"Complexity","content":"For each test case, the algorithm scans the array once.\n\nTime complexity: $O(n)$\n\nMemory complexity: $O(n)$"}],"hasLearnContent":true,"likeCount":18,"neutralCount":1,"dislikeCount":8,"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-06-08T22:04:24.030Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6a273f084b94a2b05a09f959","contestId":"6a1bac191ec01f4831a73ee1","slug":"second-good-pathh","title":"Second Good Path","description":"You are given a connected undirected graph with $n$ vertices and $m$ edges.\n\nThe edges are indexed from $1$ to $m$ in the order they are given.\n\nA path from vertex $1$ to vertex $v$ is called good if it has the minimum possible number of edges among all paths from vertex $1$ to vertex $v$.\n\nTwo good paths ending at the same vertex are compared lexicographically by the sequence of edge indices along the path from vertex $1$ to that vertex.\n\nFor each vertex $v$, find the second smallest good path ending at $v$. If it exists, output the sum of the indices of the edges used in that path. Otherwise, output $-1$.\n\nFor vertex $1$, the answer is always $-1$.\n\nThere may be multiple edges between the same pair of vertices. Self-loops are not allowed.","constraints":"- $1 \\le t \\le 10^4$\n- $2 \\le n \\le 2 \\times 10^5$\n- $n - 1 \\le m \\le 2 \\times 10^5$\n- $1 \\le u_i, v_i \\le n$\n- $u_i \\ne v_i$\n- The graph is connected\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":4,"label":"$undefined","releaseDay":"$undefined","points":2000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n2 1\n1 2\n3 3\n1 2\n1 2\n2 3\n4 4\n1 2\n1 3\n2 4\n3 4\n5 6\n1 2\n1 3\n2 4\n3 4\n2 5\n3 5\n6 8\n1 2\n1 2\n2 4\n2 4\n1 3\n3 4\n4 5\n3 6\n","expectedOutput":"-1 -1\n-1 2 5\n-1 -1 -1 6\n-1 -1 -1 6 8\n-1 2 -1 5 12 -1","isSample":true,"hidden":false,"explanation":"$37","displayInput":"5\n`\n2 1\n1 2\n`\n3 3\n1 2\n1 2\n2 3\n`\n4 4\n1 2\n1 3\n2 4\n3 4\n`\n5 6\n1 2\n1 3\n2 4\n3 4\n2 5\n3 5\n`\n6 8\n1 2\n1 2\n2 4\n2 4\n1 3\n3 4\n4 5\n3 6","displayOutput":"-1 -1\n`\n-1 2 5\n`\n-1 -1 -1 6\n`\n-1 -1 -1 6 8\n`\n-1 2 -1 5 12 -1"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\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}\nans_1 \\quad ans_2 \\quad \\cdots \\quad ans_n\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"ncmp"},"solvedCount":19,"attemptedCount":25,"tags":["graphs","dfs and similar","shortest paths"],"learnPages":[{"title":"Shortest-Path DAG","content":"First, run BFS from vertex $1$ and compute $d_v$, the minimum number of edges needed to reach each vertex $v$.\n\nNow consider an edge with index $id$ between $u$ and $v$.\n\nThis edge can be used in a good path from $1$ to $v$ only if $d_u + 1 = d_v$.\n\nSo we keep only the directed edges that go from one BFS layer to the next layer. These edges form a DAG."},{"title":"Lexicographic DFS","content":"All good paths are exactly the paths in this DAG starting from vertex $1$.\n\nIf, for every vertex, we process its outgoing edges in increasing order of edge index, then a DFS from vertex $1$ visits good paths in lexicographic order.\n\nThis means that for a fixed vertex $v$:\n\n- the first time DFS reaches $v$, it has found the smallest good path to $v$\n- the second time DFS reaches $v$, it has found the second smallest good path to $v$"},{"title":"Why Two Visits Are Enough","content":"A vertex may be reachable through many good paths, but we only need the first two of them.\n\nAfter a vertex $v$ has already been reached twice, any later path to $v$ is lexicographically larger than the second one.\n\nAlso, appending the same suffix to a larger prefix cannot make it smaller.\n\nSo after the second visit of $v$, we never need to process a third visit of $v$."},{"title":"Propagating the Second Path","content":"When a vertex is reached for the second time, we still continue DFS from it.\n\nThis is important because the second path to this vertex may create the second path to some later vertices.\n\nFor example, if there is only one directed edge from $u$ to $v$, then the second good path to $v$ may be:\n\nthe second good path to $u$ followed by this edge.\n\nThe DFS handles this automatically, because it processes both the first and the second visits of each vertex."},{"title":"Computing the Answer","content":"During DFS, we keep the current sum of edge indices on the path.\n\nFor each vertex $v$, let $cnt_v$ be the number of times it has been reached.\n\nWhen DFS reaches $v$:\n\n- if $cnt_v = 0$, this is the smallest good path to $v$\n- if $cnt_v = 1$, this is the second smallest good path to $v$, so we store the current sum as the answer\n- if $cnt_v = 2$, we ignore this visit\n\nAt the end, every vertex that was reached only once has answer $-1$."},{"title":"Complexity","content":"BFS takes $O(n+m)$ time.\n\nThe DAG also has at most $m$ edges.\n\nEach vertex is processed at most twice, and each directed edge is considered at most twice.\n\nSince we add edges to the DAG in increasing order of their indices, the outgoing edges are already in the correct order and no sorting is needed.\n\nSo the total time complexity is:\n\n$O(n+m)$\n\nThe memory complexity is:\n\n$O(n+m)$"}],"hasLearnContent":true,"likeCount":15,"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-06-08T22:15:36.599Z","updatedAt":"2026-08-20T13:51:18.164Z"},{"_id":"6a2735a54b94a2b05a09f955","contestId":"6a1bac191ec01f4831a73ee1","slug":"median-witness","title":"Median Witness","description":"You are given a permutation $p_1, p_2, \\ldots, p_n$ of integers from $1$ to $n$.\n\nFor a sequence of length $k$, its median is defined as the $\\left\\lceil \\frac{k}{2} \\right\\rceil$-th smallest element of the sequence. In particular, for even $k$, this is the lower median.\n\nCount the number of pairs $(i,j)$ such that $1 \\le i < j \\le n$ and there exists an interval $[l,r]$ satisfying all of the following conditions:\n\n- $1 \\le l \\le i < j \\le r \\le n$\n- The median of $p_l, p_{l+1}, \\ldots, p_r$ is at least $p_i$\n\nFor each test case, output this number.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 10^6$\n- $p_1, p_2, \\ldots, p_n$ is a permutation of $1,2,\\ldots,n$\n- The sum of $n$ over all test cases is at most $10^6$","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":"5\n1\n1\n2\n1 2\n2\n2 1\n3\n2 1 3\n4\n3 1 4 2\n","expectedOutput":"0\n1\n0\n3\n4","isSample":true,"hidden":false,"explanation":"$38","displayInput":"5\n`\n1\n1\n`\n2\n1 2\n`\n2\n2 1\n`\n3\n2 1 3\n`\n4\n3 1 4 2","displayOutput":"0\n`\n1\n`\n0\n`\n3\n`\n4"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\np_1 \\quad p_2 \\quad \\cdots \\quad p_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":9,"attemptedCount":11,"tags":["data structures"],"learnPages":[{"title":"Main Idea","content":"For a fixed index $i$, we only care whether an interval has median at least $p_i$.\n\nReplace every element of the permutation by a sign:\n\n- $+1$ if the element is at least $p_i$\n- $-1$ otherwise\n\nSince all values are distinct, the median of an interval is at least $p_i$ if and only if strictly more than half of the interval elements are at least $p_i$.\n\nSo the condition is equivalent to saying that the sum of signs on the chosen interval is positive."},{"title":"Counting pairs for one fixed $i$","content":"Let $S_0=0$ and let $S_x$ be the prefix sum of signs up to position $x$.\n\nFor a pair $(i,j)$ to be valid, we need an interval $[l,r]$ such that $l \\le i < j \\le r$ and $S_r-S_{l-1}>0$.\n\nThe left endpoint only affects the value $S_{l-1}$, where $l-1 \\le i-1$.\n\nSo for this fixed $i$, define $mn=\\min_{0 \\le x \\le i-1} S_x$.\n\nThen a position $j>i$ is valid if there exists some $r \\ge j$ with $S_r>mn$.\n\nTherefore, if $last$ is the largest position satisfying $S_{last}>mn$, then exactly $\\max(0,last-i)$ pairs starting from $i$ are valid."},{"title":"Offline Processing","content":"We process the values from large to small.\n\nWhen we are processing value $p_i$, all positions with value at least $p_i$ are considered active.\n\nFor the current threshold $p_i$:\n\n- active positions have sign $+1$\n- inactive positions have sign $-1$\n\nInitially, when no position is active, all signs are $-1$, so $S_x=-x$.\n\nWhen position $pos$ becomes active, its sign changes from $-1$ to $+1$.\n\nThis increases every prefix $S_x$ with $x \\ge pos$ by $2$.\n\nSo every activation is a suffix add operation on the prefix array."},{"title":"Segment Tree","content":"We keep the prefix values $S_0,S_1,\\ldots,S_n$ in a segment tree.\n\nThe segment tree must support:\n\n1. Add $2$ to all prefix positions $pos,pos+1,\\ldots,n$\n2. Find $\\min S_x$ on range $0 \\le x \\le i-1$\n3. Find the largest position $last$ such that $S_{last}>mn$\n\nThe third operation can be done by storing maximum values in the segment tree and descending from the root, always trying the right child first."},{"title":"Algorithm","content":"For each test case:\n\n1. Store the position of each value in the permutation.\n2. Initialize the prefix array as $S_x=-x$ for all $0 \\le x \\le n$.\n3. Iterate values from $n$ down to $1$.\n4. Let $i$ be the position of the current value.\n5. Activate position $i$ by adding $2$ to all prefix positions from $i$ to $n$.\n6. Compute $mn=\\min_{0 \\le x \\le i-1} S_x$.\n7. Find the largest position $last$ such that $S_{last}>mn$.\n8. Add $\\max(0,last-i)$ to the answer."},{"title":"Correctness","content":"For each fixed $i$, after activating all values from $n$ down to $p_i$, the sign of every position is correct with respect to the threshold $p_i$.\n\nAn interval has median at least $p_i$ exactly when the sum of its signs is positive.\n\nFor a pair $(i,j)$, the left endpoint can be chosen before or at $i$, so the best possible left prefix is the minimum prefix among $S_0,S_1,\\ldots,S_{i-1}$.\n\nThus, $(i,j)$ is valid exactly when some prefix position $r \\ge j$ has value greater than this minimum prefix.\n\nThe algorithm finds the largest such $r$, so all positions $j$ with $i

ANotebook Page	500	96/102
BPrison Watch	1000	80/87
CSplit Machine	1500	30/49
DSecond Good Path	2000	19/25
EMedian Witness	2500	9/11
FP4 Decomposition	3000	2/4