5f:"/_next/static/immutable/chunks/0t_984-15imyt.js" 60:"/_next/static/immutable/chunks/1z_ykp5dnqoue.js" 61:"/_next/static/immutable/chunks/0u6rsm220c3gx.js" 62:"/_next/static/immutable/chunks/0u44pe9dot2jc.js" 63:I[290370,["$4","$5","$6","$7","$8","$9","$a","$b","$46","$4e","$4f","$50","$51","$3d","$52","$3c","$4a","$53","$48","$54","$5f","$60","$61","$62"],"default"] 64:I[218728,["$4","$5","$6","$7","$8","$9","$a","$b","$46","$4e","$4f","$50","$51","$3d","$52","$3c","$4a","$53","$48","$54","$5f","$60","$61","$62"],"default"] 65:T5e9,#include "testlib.h" #include using namespace std; int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; ++tc) { int n = inf.readInt(); long long sum = 0; int positive = 0; for (int i = 0; i < n; ++i) { int degree = inf.readInt(); int remaining = degree - 2; sum += remaining; if (remaining > 0) { ++positive; } } bool possible = positive == 0 || (sum % 2 == 0 && sum <= 2LL * positive - 2); string received = ouf.readWord(); for (char& c : received) { if ('A' <= c && c <= 'Z') { c = char(c - 'A' + 'a'); } } string expected = possible ? "yes" : "no"; if (received != "yes" && received != "no") { quitf( _wa, "test case %d: expected Yes or No, but found '%s'", tc, received.c_str() ); } if (received != expected) { quitf( _wa, "test case %d: expected %s, but found %s", tc, expected.c_str(), received.c_str() ); } } if (!ouf.seekEof()) { quitf(_wa, "extra tokens in the participant output"); } quitf(_ok, "all %d answers are correct", t); }66:T723,If two different cycles shared a vertex, that vertex would belong to more than one cycle. Therefore, all cycles of a valid graph are vertex-disjoint. Remove the edges of these cycles. Every vertex loses exactly $2$ from its degree, including a vertex whose cycle is a loop. Define $$ b_i=a_i-2. $$ The remaining graph must be a forest. Otherwise, any cycle in it would be an additional cycle containing each of its vertices. The converse is also useful: from any forest with degrees $b_i$, add one loop to every vertex. The loops are then the only cycles, and the final degrees are $a_i$. Thus, we only have to determine whether $b_1,b_2,\ldots,b_n$ is the degree sequence of a forest. # Characterizing forest degree sequences Ignore the zero values. Let $k$ be the number of positive values and let $S$ be their sum. If $k=0$, the empty forest works. Now suppose $k>0$. A forest on these $k$ non-isolated vertices has at most $k-1$ edges. Hence, its degree sum must be even and must satisfy $S\le 2k-2$. These two conditions are also sufficient. Since all $k$ degrees are positive and $S<2k$, at least one degree is $1$. If every degree is $1$, then $S$ being even allows us to pair the vertices and use one edge for every pair. Otherwise, take a vertex of degree $1$ and a vertex whose degree is greater than $1$. Join them, remove the first vertex, and decrease the second degree by $1$. The new sequence is still positive, its sum is $S-2$, and it satisfies $S-2\le 2(k-1)-2$. Repeating this process constructs a forest; adding a removed vertex back as a leaf never creates a cycle. Therefore, the answer is `Yes` exactly when either $k=0$, or both $S$ is even and $S\le 2k-2$. # Complexity We only scan the sequence once. The time complexity is $O(n)$ per test case, and the extra space complexity is $O(1)$.67:T452,#include #include "testlib.h" using namespace std; string normalizeAnswer(string s) { for (char& c : s) { c = char(tolower(static_cast(c))); } return s; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; ++tc) { string expected = normalizeAnswer(ans.readToken()); string received = normalizeAnswer(ouf.readToken()); if (expected != "yes" && expected != "no") { quitf(_fail, "the jury answer for test case %d is invalid", tc); } if (received != expected) { quitf( _wa, "test case %d: expected %s, found %s", tc, expected.c_str(), received.c_str() ); } } if (!ans.seekEof()) { quitf(_fail, "the jury output contains extra tokens"); } if (!ouf.seekEof()) { quitf(_wa, "the participant output contains extra tokens"); } quitf(_ok, "all %d answers are correct", t); }68:T4ec,#include #include "testlib.h" using namespace std; string normalizeAnswer(string s) { for (char& c : s) { c = char(tolower(static_cast(c))); } return s; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; ++tc) { string expected = normalizeAnswer(ans.readWord()); string received = normalizeAnswer(ouf.readWord()); if (expected != "yes" && expected != "no") { quitf(_fail, "the jury answer for test case %d is invalid", tc); } if (received != "yes" && received != "no") { quitf(_wa, "test case %d: expected Yes or No, found %s", tc, received.c_str()); } if (received != expected) { quitf( _wa, "test case %d: expected %s, found %s", tc, expected.c_str(), received.c_str() ); } } if (!ans.seekEof()) { quitf(_fail, "the jury output contains extra tokens"); } if (!ouf.seekEof()) { quitf(_wa, "the participant output contains extra tokens"); } quitf(_ok, "all %d answers are correct", t); }2a:["$","div",null,{"children":[["$","$L63",null,{"contestId":"6a5d215e8bf66175db80f279","contestType":"cp","contestNumber":18,"contestUrlId":"18","initialIsRegistered":false,"registrationClosed":true}],["$","$L64",null,{"contest":{"contestNumber":18,"title":"Repovive Standard Round 6","startDate":"2026-07-27T14:35:00.000Z","endDate":"2026-07-27T16: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":"6a62963c2beac98d01743da4","contestId":"6a5d215e8bf66175db80f279","slug":"one-cycle-each","title":"One Cycle Each","description":"You are given a sequence $a_1,a_2,\\ldots,a_n$.\n\nDetermine whether there exists an undirected multigraph with vertices numbered from $1$ to $n$ such that:\n\n- the degree of vertex $i$ is exactly $a_i$;\n- every vertex belongs to exactly one cycle.\n\nThe graph does not have to be connected. Loops and multiple edges are allowed.\n\nA loop is considered a cycle of length $1$, and it contributes $2$ to the degree of its endpoint. Every pair of parallel edges forms a cycle of length $2$. Cycles that use different edges are considered different.","constraints":"- $1 \\le t \\le 10^4$\n- $2 \\le n \\le 2 \\times 10^5$\n- $2 \\le a_i \\le n$\n- The sum of $n$ over all test cases does not exceed $2 \\times 10^5$","difficulty":"medium","order":1,"label":"C","releaseDay":"$undefined","points":1500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n3\n2 2 2\n4\n3 3 2 2\n4\n3 2 2 2\n","expectedOutput":"Yes\nYes\nNo\n","isSample":true,"hidden":false,"explanation":"Place one loop on each of the $3$ vertices and add no other edges. Every degree is $2$, and each vertex belongs only to its own loop.\n\n`\nPlace one loop on every vertex, then add one edge between vertices $1$ and $2$. Their degrees become $3$, the other two degrees remain $2$, and the added edge creates no new cycle.\n\n`\nThe degree sum is $3+2+2+2=9$. In every undirected multigraph, loops included, the degree sum is twice the number of edges and is therefore even. Hence, no such graph exists.\n","displayInput":"3\n`\n3\n2 2 2\n`\n4\n3 3 2 2\n`\n4\n3 2 2 2","displayOutput":"Yes\n`\nYes\n`\nNo"},{"input":"2\n8\n5 3 3 3 2 2 2 2\n10\n4 4 4 4 2 2 2 2 2 2\n","expectedOutput":"Yes\nNo\n","isSample":true,"hidden":false,"explanation":"Loops on all vertices and three edges from vertex $1$ to vertices $2$, $3$, and $4$ give the required degrees.\n\n`\nAfter reserving degree $2$ for one cycle at each vertex, the first $4$ vertices would need degree sum $8$ in an acyclic graph, which is impossible.\n","displayInput":"2\n`\n8\n5 3 3 3 2 2 2 2\n`\n10\n4 4 4 4 2 2 2 2 2 2","displayOutput":"Yes\n`\nNo"}],"sampleCount":2,"inputFormat":"$$$\nt\n$$\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":"For each test case, output `Yes` if such a multigraph exists, and `No` otherwise.\n\nThe answer is case-insensitive. For example, `YES`, `yes`, and `yEs` are all accepted.\n\n$$\n\\left.\n\\begin{array}{l}\n\\texttt{Yes or No}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$65"},"solvedCount":35,"attemptedCount":38,"tags":["graphs","trees","math","constructive"],"learnPages":[{"title":"Removing the cycle degrees","content":"$66"}],"hasLearnContent":true,"likeCount":17,"neutralCount":0,"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-07-23T22:31:24.994Z","updatedAt":"2026-07-31T07:09:09.366Z"},{"_id":"6a6296b0739edd6d77c5a4d6","contestId":"6a5d215e8bf66175db80f279","slug":"successor-swap","title":"Successor Swap","description":"You are given a permutation $p$ of the integers from $1$ to $n$.\n\nIn one operation, you may do the following:\n\n- choose an index $i$ such that $i < p_i$;\n- set $j = p_i$;\n- swap the elements at indices $i$ and $j$. In other words, swap $p_i$ and $p_j$.\n\nFind the number of distinct permutations that can be reached after performing any number of operations, possibly zero.\n\nPrint the answer modulo $998244353$.","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- $p$ is a permutation of the integers from $1$ to $n$","difficulty":"medium","order":2,"label":"D","releaseDay":"$undefined","points":2000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n4\n1 2 3 4\n4\n2 3 4 1\n4\n4 3 1 2\n","expectedOutput":"1\n8\n6\n","isSample":true,"hidden":false,"explanation":"No operation can be performed, so the only reachable permutation is $(1,2,3,4)$.\n`\nStarting from $(2,3,4,1)$, the following sequences of chosen indices produce all reachable permutations:\n\n- no operations: $(2,3,4,1)$\n- $1$: $(3,2,4,1)$\n- $2$: $(2,4,3,1)$\n- $3$: $(2,3,1,4)$\n- $1,1$: $(4,2,3,1)$\n- $1,3$: $(3,2,1,4)$\n- $2,2$: $(2,1,3,4)$\n- $1,1,1$: $(1,2,3,4)$\n\nTherefore, the answer is $8$.\n`\nStarting from $(4,3,1,2)$, choosing the indices\n\n- none,\n- $1$,\n- $2$,\n- $1,1$,\n- $1,2$,\n- $1,1,1$\n\nproduces the six distinct reachable permutations. Therefore, the answer is $6$.","displayInput":"3\n`\n4\n1 2 3 4\n`\n4\n2 3 4 1\n`\n4\n4 3 1 2","displayOutput":"1\n`\n8\n`\n6"},{"input":"2\n8\n2 3 1 5 4 8 6 7\n10\n10 9 8 6 7 1 4 2 5 3\n","expectedOutput":"24\n98\n","isSample":true,"hidden":false,"explanation":"For example, choosing the indices $1,1,4,6,6$ produces $(1,2,3,4,5,6,7,8)$. Considering all legal sequences gives $24$ distinct reachable permutations.\n`\nFor example, applying the operation at index $1$ nine times produces $(1,2,3,4,5,6,7,8,9,10)$. Considering all legal sequences gives $98$ distinct reachable permutations.","displayInput":"2\n`\n8\n2 3 1 5 4 8 6 7\n`\n10\n10 9 8 6 7 1 4 2 5 3","displayOutput":"24\n`\n98"}],"sampleCount":2,"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":15,"attemptedCount":15,"tags":["dp","data structures","combinatorics"],"learnPages":[{"title":"Viewing an Operation on a Cycle","content":"Write the permutation as disjoint directed cycles. Suppose one cycle contains\n\n$i \\to j \\to k$,\n\nso $p_i=j$ and $p_j=k$.\n\nIf $ia$.\n\nIf this condition holds, delete them from left to right. Their current predecessor is always $a$, so every deletion is legal.\n\nFor necessity, suppose some deleted vertex is smaller than $a$, and choose the smallest deleted vertex $x$ in this gap. When $x$ is deleted, its predecessor is either $a$ or another vertex of the gap. Both are larger than $x$, so that deletion cannot be legal."},{"title":"DP by the Last Remaining Vertex","content":"Scan $c_1,c_2,\\ldots,c_m$ from left to right.\n\nLet $dp[y]$ be the number of valid decisions for the processed prefix whose last remaining vertex is $y$, and let $S$ be the sum of all current states.\n\nWhen the next vertex is $x$, we have two possibilities.\n\nIf we keep $x$, every previous state creates a distinct state ending at $x$. Thus the new weight of $x$ is $S$.\n\nIf we delete $x$, the last remaining vertex $y$ must satisfy $yx$ disappear.\n\nAfter the whole cycle is processed, the sum of the DP states is exactly the number of reachable states of this cycle."},{"title":"Maintaining the DP with a Stack","content":"The active keys $y$ are always increasing.\n\nWhen processing $x$, all keys greater than $x$ form a suffix. We remove that suffix, then append the new state for $x$ with weight equal to the old total sum.\n\n```\nstack = [(c[1], 1)]\nsum = 1\n\nfor x in c[2 ... m]:\n old_sum = sum\n\n while stack.top.vertex > x:\n sum -= stack.top.ways\n stack.pop()\n\n stack.push((x, old_sum))\n sum += old_sum\n```\n\nAll values are maintained modulo $998244353$.\n\nEvery cycle vertex is pushed once and popped at most once. Hence the total time complexity is $O(n)$ and the memory complexity is $O(n)$."}],"hasLearnContent":true,"likeCount":7,"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-07-23T22:33:20.806Z","updatedAt":"2026-07-31T07:09:09.366Z"},{"_id":"6a629718739edd6d77c5a4d9","contestId":"6a5d215e8bf66175db80f279","slug":"consecutive-run","title":"Consecutive Run","description":"You are given an integer $n$.\n\nConsider a permutation $p_1,p_2,\\ldots,p_n$ of $1,2,\\ldots,n$.\n\nA contiguous segment $p_l,p_{l+1},\\ldots,p_r$ is called consecutive increasing if\n$p_{l+i}=p_l+i$\nfor every $0\\le i\\le r-l$.\n\nThe value of a permutation is the maximum length of a consecutive increasing segment in it.\n\nFor every $k$ from $1$ to $n$, find the number of permutations of value exactly $k$. Output each answer modulo $998244353$.","constraints":"- $1 \\le t \\le 100$\n- $1 \\le n \\le 2000$\n- The sum of $n$ over all test cases is at most $2000$","difficulty":"medium","order":3,"label":"E","releaseDay":"$undefined","points":2500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"4\n1\n2\n3\n5\n","expectedOutput":"1\n1 1\n3 2 1\n53 53 11 2 1\n","isSample":true,"hidden":false,"explanation":"The only permutation is $(1)$, and its value is $1$.\n\n`\nThe permutations $(2,1)$ and $(1,2)$ have values $1$ and $2$, respectively.\n\n`\nAmong the six permutations, three have value $1$, two have value $2$, and only $(1,2,3)$ has value $3$.\n\n`\nFor example, $(1,2,5,3,4)$ has value $2$. Only $(1,2,3,4,5)$ has value $5$.\n","displayInput":"4\n`\n1\n`\n2\n`\n3\n`\n5","displayOutput":"1\n`\n1 1\n`\n3 2 1\n`\n53 53 11 2 1"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn\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$$\n\nHere, $ans_k$ is the number of permutations whose value is exactly $k$, taken modulo $998244353$.","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":11,"attemptedCount":11,"tags":["combinatorics","dp","math"],"learnPages":[{"title":"Turning segments into bonds","content":"Call $i$ a bond of a permutation if $i+1$ appears immediately after $i$.\n\nA consecutive increasing segment of length $k+1$ exists exactly when there are $k$ consecutive bonds. Therefore, if $F_k$ is the number of permutations whose value is at most $k$, we need to count permutations with no $k$ consecutive bonds.\n\nThe requested answer for $k$ is $F_k-F_{k-1}$."},{"title":"Inclusion-exclusion on required bonds","content":"For a set $T$ of required bonds, every maximal run of bonds can be glued into one block. Hence exactly $(n-|T|)!$ permutations contain all bonds of $T$.\n\nAfter Möbius inversion, the coefficient of $T$ in $F_k$ is\n\n$\\displaystyle \\sum_{\\substack{A\\subseteq T\\\\A\\text{ has no }k\\text{ consecutive bonds}}}(-1)^{|T|-|A|}$.\n\nThis coefficient factors over the maximal runs of $T$. Let $h_l$ be the factor contributed by a run of length $l$. Inside that run, a bond included in $A$ has weight $1$, while an excluded bond has weight $-1$, and $A$ may not contain $k$ consecutive bonds.\n\nThe generating function of these weighted binary strings is\n\n$\\displaystyle H(z)=\\sum_{l\\ge 0}h_lz^l=\\frac{1-z^k}{1-z^{k+1}}$.\n\nThus a nonempty run contributes through\n\n$\\displaystyle R(z)=H(z)-1=-\\frac{z^k}{1+z+\\cdots+z^k}$."},{"title":"Summing all placements","content":"Suppose $T$ has $c$ nonempty runs and contains $j$ bonds in total. For fixed ordered run lengths, these runs can be placed on the $n-1$ possible bonds in\n\n$\\binom{n-j}{c}$\n\nways. Let\n\n$p_{c,j}=[z^j]R(z)^c$.\n\nIt follows that\n\n$\\displaystyle F_k=n!+\\sum_{c\\ge1}\\sum_j p_{c,j}\\binom{n-j}{c}(n-j)!$.\n\nWe compute the coefficients without polynomial multiplication. From\n\n$(1+z+\\cdots+z^k)R(z)^c=-z^kR(z)^{c-1}$\n\nwe get\n\n$p_{c,j}+p_{c,j-1}+\\cdots+p_{c,j-k}=-p_{c-1,j-k}$.\n\nFor fixed $c$, a sliding-window sum computes all relevant $p_{c,j}$ in linear time. We only need $c\\le\\lfloor n/(k+1)\\rfloor$ and $ck\\le j\\le n-c$.\n\nPrecompute $(n-j)!\\binom{n-j}{c}$ for all needed pairs. Summing the work over every $k$ gives $O(n^2\\log n)$ time and $O(n^2)$ memory."}],"hasLearnContent":true,"likeCount":7,"neutralCount":0,"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":"6a628249ab07c08345b7af0c","name":"Mani Zare"}],"statementOverrides":"$undefined","createdAt":"2026-07-23T22:35:04.855Z","updatedAt":"2026-07-31T07:09:09.366Z"},{"_id":"6a639fe3b879475f051ec785","contestId":"6a5d215e8bf66175db80f279","slug":"behind-the-peak","title":"Behind the Peak","description":"You are given a permutation $p$ of length $n$.\n\nIn one operation, you may choose an index $i$ such that $1 \\le i \\le n-2$ and\n\n$$\np_{i+1}>\\max(p_i,p_{i+2}),\n$$\n\nthen swap $p_i$ and $p_{i+2}$.\n\nDetermine whether it is possible, after performing any number of operations, to make\n$p_i\\max(2,1)$, swap the elements at indices $1$ and $3$. The sequence becomes $1,3,2$, which satisfies the required condition.\n\n`\nChoose $i=1$ and swap indices $1$ and $3$. The sequence becomes $2,4,3,5,1$.\n\nNext, choose $i=3$ and swap indices $3$ and $5$. The sequence becomes $2,4,1,5,3$.\n\nFinally, choose $i=1$ and swap indices $1$ and $3$. The sequence becomes $1,4,2,5,3$, which satisfies the required condition.\n\n`\nIt is impossible to reach a permutation satisfying the required condition.\n","displayInput":"3\n`\n3\n2 3 1\n`\n5\n3 4 2 5 1\n`\n4\n3 1 2 4","displayOutput":"Yes\n`\nYes\n`\nNo"},{"input":"2\n8\n1 3 4 6 7 5 8 2\n10\n10 9 8 7 6 5 4 3 2 1\n","expectedOutput":"Yes\nNo\n","isSample":true,"hidden":false,"explanation":"Swap the elements at indices $(4,6)$, then $(6,8)$, then $(4,6)$, and finally $(2,4)$. These operations produce a permutation satisfying the required condition.\n\n`\nIt is impossible to reach a permutation satisfying the required condition.\n","displayInput":"2\n`\n8\n1 3 4 6 7 5 8 2\n`\n10\n10 9 8 7 6 5 4 3 2 1","displayOutput":"Yes\n`\nNo"}],"sampleCount":2,"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":"For each test case, output `Yes` if the required permutation can be obtained, and `No` otherwise.\n\nThe answer is case-insensitive. For example, `YES`, `yes`, and `yEs` are all accepted.\n\n$$\n\\left.\n\\begin{array}{l}\n\\texttt{Yes or No}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$67"},"solvedCount":10,"attemptedCount":12,"tags":["greedy","data structures","sortings","constructive"],"learnPages":[{"title":"Split the permutation by parity","content":"Let\n\n$A=(p_1,p_3,p_5,\\ldots)$\n\nand\n\n$B=(p_2,p_4,p_6,\\ldots)$.\n\nIf the chosen index is odd, the operation swaps two adjacent elements of $A$. If the chosen index is even, it swaps two adjacent elements of $B$.\n\nMore precisely:\n\n- swapping $A_j$ and $A_{j+1}$ is allowed when $B_j>\\max(A_j,A_{j+1})$;\n- swapping $B_j$ and $B_{j+1}$ is allowed when $A_{j+1}>\\max(B_j,B_{j+1})$.\n\nTherefore, elements never move between $A$ and $B$."},{"title":"Identify the only target","content":"The required inequalities $p_ix$.\n\nSimilarly, if $x$ belongs to $B$, the first required gate is\n\n$a_{s+1}$,\n\nso we need $a_{s+1}>x$.\n\nIf $x$ is already the last remaining value, it does not move and no gate needs to be checked.\n\nWhen the check succeeds, every required gate has value larger than $x$. These gate values have already been fixed, so the corresponding swaps are valid. If the first gate is not larger than $x$, the decreasing-order argument shows that no successful sequence exists."},{"title":"Maintain positions with Fenwick trees","content":"We do not perform the swaps explicitly.\n\nFor each of $A$ and $B$, create a Fenwick tree containing $1$ at every original position. A position remains active exactly while its value has not been processed.\n\nFor a value $x$ stored at original position $pos$, its current position among the remaining values is\n\n$s=\\operatorname{prefixSum}(pos)-1$.\n\nAfter checking $x$, remove its original position from the Fenwick tree. This represents moving $x$ to the end of the active prefix and fixing it: all smaller elements keep their relative order, exactly as if the swaps had been performed.\n\nWe also maintain the number of remaining values in each subsequence to know its last active position."},{"title":"Algorithm and complexity","content":"For each test case:\n\n1. Split $p$ into $A$ and $B$, and record the subsequence and original position of every value.\n2. Sort copies of the two subsequences to obtain $a$ and $b$.\n3. Initialize two Fenwick trees with all positions active.\n4. For $x=n,n-1,\\ldots,1$:\n - find its current active position $s$;\n - if it is not the last active position, check $b_s>x$ for $x\\in A$, or $a_{s+1}>x$ for $x\\in B$;\n - if the check fails, output `No`;\n - remove $x$ from its Fenwick tree.\n5. If every check succeeds, output `Yes`.\n\nSorting and all Fenwick operations take $O(n\\log n)$ time. The memory usage is $O(n)$."}],"hasLearnContent":true,"likeCount":4,"neutralCount":0,"dislikeCount":2,"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-07-24T17:24:51.386Z","updatedAt":"2026-07-31T07:09:09.366Z"},{"_id":"6a672129f6c039be590ec563","contestId":"6a5d215e8bf66175db80f279","slug":"open-at-both-ends","title":"Open at Both Ends","description":"There are $n$ books on a shelf, numbered from $1$ to $n$. From left to right, their current order is the permutation $p_1,p_2,\\ldots,p_n$.\n\nThe shelf is sorted if the books appear in the order $1,2,\\ldots,n$.\n\nIn one operation, you may choose the leftmost or the rightmost book, remove it from the shelf, and insert it at any position. In particular, you may insert it at either end of the shelf.\n\nFind the minimum number of operations needed to sort the shelf.","constraints":"- $1 \\le t \\le 10^3$\n- $1 \\le n \\le 10^5$\n- The sum of $n$ over all test cases is at most $10^5$\n- $p$ is a permutation of $1,2,\\ldots,n$","difficulty":"easy","order":5,"label":"B","releaseDay":"$undefined","points":1000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n4\n4 2 3 1\n5\n1 2 3 4 5\n5\n5 4 3 2 1\n","expectedOutput":"2\n0\n4\n","isSample":true,"hidden":false,"explanation":"One optimal sequence is:\n\n- Remove book $1$ from the right end and insert it between books $4$ and $2$, obtaining $4,1,2,3$.\n- Remove book $4$ from the left end and insert it at the right end, obtaining $1,2,3,4$.\n\nOne operation cannot be enough. If book $4$ is moved, the remaining books are in the order $2,3,1$; if book $1$ is moved, they are in the order $4,2,3$. Neither order can be part of the sorted shelf.\n`\nThe shelf is already sorted, so no operation is needed.\n`\nThe books are initially in decreasing order. Any two books that are never moved would stay in decreasing relative order, so at least four books must be moved.\n\nFour operations are sufficient:\n\n$$\n5,4,3,2,1\n\\to 5,4,1,3,2\n\\to 5,4,1,2,3\n\\to 4,1,2,3,5\n\\to 1,2,3,4,5.\n$$\n","displayInput":"3\n`\n4\n4 2 3 1\n`\n5\n1 2 3 4 5\n`\n5\n5 4 3 2 1","displayOutput":"2\n`\n0\n`\n4"},{"input":"2\n8\n8 1 3 5 6 2 4 7\n10\n2 5 8 9 1 3 4 6 7 10\n","expectedOutput":"4\n4\n","isSample":true,"hidden":false,"explanation":"The shelf can be sorted in four operations, and three operations are not sufficient.\n`\nThe minimum number of operations is four.\n","displayInput":"2\n`\n8\n8 1 3 5 6 2 4 7\n`\n10\n2 5 8 9 1 3 4 6 7 10","displayOutput":"4\n`\n4"}],"sampleCount":2,"inputFormat":"The input consists of multiple test cases.\n\n$$\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":"For each test case, output the minimum number of operations needed to sort the shelf.\n\n$$\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":43,"attemptedCount":43,"tags":["greedy","constructive","implementation"],"learnPages":[{"title":"Which books can stay untouched?","content":"Suppose some books are never chosen in any operation.\n\nThey must form one contiguous subarray of the initial shelf. Indeed, before we can choose a book, every book to its left or every book to its right must already have been removed. Therefore, we cannot remove a book that lies strictly between two untouched books.\n\nThe relative order of untouched books never changes. Since the final shelf is increasing, these books must also be increasing from left to right."},{"title":"Keeping any increasing subarray","content":"Now choose any increasing contiguous subarray and decide not to move its books.\n\nIt is useful to view the operations backwards. A reversed operation removes any book and places it at the left or right end.\n\nStart from the sorted shelf. Move the books that should appear to the left of the chosen subarray to the left end, in the appropriate reverse order. Similarly, move the books that should appear to its right to the right end, in the appropriate reverse order.\n\nMore precisely, if the original permutation is $A+S+B$, move the books of $A$ to the left end from right to left, and move the books of $B$ to the right end from left to right. Once all other books have been moved, the untouched books of $S$ become consecutive automatically.\n\nThis constructs the original permutation while never moving the chosen subarray. Reversing this sequence sorts the shelf and moves every other book exactly once."},{"title":"Computing the answer","content":"Let $L$ be the maximum length of an increasing contiguous subarray of $p$.\n\nThe first observation shows that at most $L$ books can remain untouched, so at least $n-L$ operations are necessary. The construction above keeps an increasing subarray of length $L$ and moves all other books once, so $n-L$ operations are also sufficient.\n\nWe find $L$ in one scan. If $p_i

ATwo VIPs	500	48/48
BOpen at Both Ends	1000	43/43
COne Cycle Each	1500	35/38
DSuccessor Swap	2000	15/15
EConsecutive Run	2500	11/11
FBehind the Peak	3000	10/12