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:T4ff,### Algorithm 1. Read $t$, the number of test cases. 2. For each test case: - Read $a, b, c$. - Sort them so $a \le b \le c$. - If $a + b > c$, output $a + b + c$. - Otherwise, output $2 \cdot (a + b) - 1$. ### Proof of Correctness **Why only shorten $c$?** Since the triangle inequality only involves $a + b$ vs $c$, shortening $a$ or $b$ makes $a + b$ even smaller, making the inequality harder to satisfy or reducing the perimeter more than necessary. Shortening $c$ is strictly better. **Why $c' = a + b - 1$?** We need $a + b > c'$. The largest integer $c'$ satisfying this is $a + b - 1$. Since we want to maximize the perimeter, we should cut $c$ as little as possible, i.e., to the largest value that still works. **Why does this give the global maximum?** Any valid triangle from cuts has sides $a' \le a$, $b' \le b$, $c' \le c$ with $a' + b' > c'$. The perimeter is $a' + b' + c' < a' + b' + (a' + b') = 2(a' + b') \le 2(a + b)$. Our construction achieves $2(a + b) - 1$, which is at most $1$ less than this upper bound — and in the $a + b > c$ case we achieve the absolute maximum $a + b + c$. ### Complexity $O(1)$ per test case, $O(t)$ total. Uses 64-bit integers since perimeters can reach up to $3 \times 10^9$, exceeding 32-bit signed range.38:T454,The two strings are already equal, so no operation is needed. ` It is impossible to perform any operation, because the only character of $S$ is $0$. Therefore, $S$ cannot be changed into $T$. ` The output uses $2$ operations. First, choose $i=1$. The current value of $S_1$ is $1$, so the operation is valid. $$ 11 \to 01 $$ Then choose $i=2$. The current value of $S_2$ is $1$, so the operation is valid. $$ 01 \to 10 $$ Now $S$ is equal to $T$. ` The output uses $3$ operations. First, choose $i=5$. The current value of $S_5$ is $1$, so the operation is valid. $$ 10101 \to 01010 $$ Then choose $i=2$. The current value of $S_2$ is $1$, so the operation is valid. $$ 01010 \to 10010 $$ Then choose $i=4$. The current value of $S_4$ is $1$, so the operation is valid. $$ 10010 \to 01100 $$ Now $S$ is equal to $T$. ` The output uses $2$ operations. First, choose $i=5$. The current value of $S_5$ is $1$, so the operation is valid. $$ 00001 \to 11110 $$ Then choose $i=2$. The current value of $S_2$ is now $1$, so the operation is valid. $$ 11110 \to 00110 $$ Now $S$ is equal to $T$.39:Ta2f,#include #include "testlib.h" using namespace std; struct Fenwick { int n; vector bit; Fenwick(int n = 0) : n(n), bit(n + 2, 0) {} void add(int idx, int val) { for (; idx <= n + 1; idx += idx & -idx) { bit[idx] ^= val; } } int get(int idx) { int res = 0; for (; idx > 0; idx -= idx & -idx) { res ^= bit[idx]; } return res; } void flipPrefix(int r) { add(1, 1); add(r + 1, 1); } }; static string lowerString(string s) { for (char &c : s) c = (char)tolower(c); return s; } static bool possible(const string &s, const string &target) { int n = (int)s.size(); vector d(n + 2, 0); for (int i = 1; i <= n; i++) { d[i] = (s[i - 1] != target[i - 1]); } int h = 0; for (int i = 1; i <= n; i++) { if (d[i] ^ d[i + 1]) h = i; } return h == 0 || s[h - 1] == '1'; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; tc++) { int n = inf.readInt(); string s = inf.readToken(); string target = inf.readToken(); bool can = possible(s, target); string verdict = lowerString(ouf.readToken("[A-Za-z]+", "answer verdict")); if (verdict != "yes" && verdict != "no") { quitf(_wa, "test case %d: expected Yes or No", tc); } if (verdict == "no") { if (can) { quitf(_wa, "test case %d: participant says No, but a solution exists", tc); } continue; } if (!can) { quitf(_wa, "test case %d: participant says Yes, but no solution exists", tc); } int k = ouf.readInt(0, n, "k"); Fenwick fw(n + 1); for (int j = 1; j <= k; j++) { int idx = ouf.readInt(1, n, "operation index"); int currentBit = (s[idx - 1] - '0') ^ fw.get(idx); if (currentBit != 1) { quitf(_wa, "test case %d: operation %d is invalid because S[%d] is 0", tc, j, idx); } fw.flipPrefix(idx); } for (int i = 1; i <= n; i++) { int currentBit = (s[i - 1] - '0') ^ fw.get(i); if (currentBit != target[i - 1] - '0') { quitf(_wa, "test case %d: final string differs from T at position %d", tc, i); } } } if (!ouf.seekEof()) { quitf(_wa, "extra output after all test cases"); } quitf(_ok, "all test cases are valid"); }3a:T40f,The necessary and sufficient condition is that the last position where $S$ and $T$ differ must contain $1$ in $S$. ### Why is this necessary? To change position $p$, we must flip some prefix of length at least $p$. But since $p$ is the last differing position, no operation on a prefix longer than $p$ can be used, because it would also alter later positions that already match. Therefore, we must perform the operation exactly on prefix $p$. That requires the initial value of $S_p$ to be $1$. ### Constructing the Operations First, determine which prefixes need to be flipped; call these the **good prefixes**. Then repeatedly do the following: - Perform the operation on the first good prefix such that $S_i = 1$ - After this, all good prefixes to its left will have their corresponding bits changed to $1$ - Now these prefixes can be processed from left to right. Since every chosen good prefix satisfies $S_i=1$ when it is used, all required operations can be performed. After applying all of them, $S$ becomes equal to $T$.3b:T456,First, consider the edges adjacent to vertex $n$. For every vertex $v$ adjacent to $n$, if Bob is currently at $v$, Alice should block the edge between $v$ and $n$, since otherwise Bob could immediately move to $n$. We want to compute $ans_v$ for every vertex $v$, where $ans_v$ represents the largest vertex Bob can guarantee reaching when starting from $v$. The final answer is $ans_1$. We maintain three states for each vertex: - 0 — not visited yet - 1 — the edge Alice would block has been determined - 2 — $ans_v$ has already been computed Now iterate through the vertices from $n$ down to $1$. Suppose we are currently processing vertex $v$. Assign $state_v=2$ and $ans_v=v$, then run a BFS starting from $v$ using the following transitions: For each vertex $u$ adjacent to $v$: - if $state_u=0$ set $state_u = 1$ - if $state_u=1$ set $state_u = 2$; $ans_u=ans_v$ and add $u$ to the queue The intuition is that once a vertex has been reached twice through different edges, Alice can block only one of them, so Bob can still force movement toward a vertex with the same guaranteed answer.3c:T6ee,For the only prefix, we start with an empty set. First, we insert $0$, so $S=\{0\}$. Then we use the operation and insert $\operatorname{mex}(S)=1$. Now $S=\{0,1\}$, so the final mex is $2$. ` For the prefix $[1]$, after inserting $1$, we use the operation and insert $0$. The final set contains $0$ and $1$, so the score is $2$. For the prefix $[1,0]$, first insert $1$, then use the operation to insert $0$. After that, the array also inserts $0$. The final set contains $0$ and $1$, so the score is $2$. For the prefix $[1,0,3]$, first insert $1$, then insert $0$. After that, use the operation and insert $2$. Finally, insert $3$. The final set contains $0,1,2,3$, so the score is $4$. For the prefix $[1,0,3,2]$, the same operation after inserting $0$ gives $2$. The final set contains $0,1,2,3$, so the score is $4$. ` For the full prefix $[0,2,1,0,4]$, use the first operation after inserting $0$ to insert $1$. Then insert $2$ from the array. Use the second operation to insert $3$. Finally, the array inserts $4$. The final set contains $0,1,2,3,4$, so the score is $5$. ` For the prefix $[3,3,0]$, after inserting the first $3$, use one operation to insert $0$. After inserting the second $3$, use another operation to insert $1$. After inserting $0$, use the last operation to insert $2$. The final set contains $0,1,2,3$, so the score is $4$. ` For the full prefix $[1,2,0,4,3,6,5]$, use the operations after inserting the 3rd, 4th, 6th, and 7th elements. After inserting $0$, the set contains $0,1,2$, so the operation inserts $3$. After inserting $4$, the operation inserts $5$. After inserting $6$, the operation inserts $7$. After inserting $5$, the operation inserts $8$. So the final set contains all numbers from $0$ to $8$, and the score is $9$.3d:T756,The DFS orders are $(1,2,4,3)$ and $(1,3,2,4)$. Vertex $3$ is never the third vertex, so no pair of the form $(3,j)$ is good. Vertex $2$ can be second after vertex $1$. Vertex $4$ can be fourth after all smaller vertices. Therefore the good pairs are $(2,1)$, $(4,1)$, $(4,2)$, and $(4,3)$. ` The DFS orders are $(1,2,4,5,3)$, $(1,2,5,4,3)$, $(1,3,2,4,5)$, and $(1,3,2,5,4)$. Vertex $3$ is never the third vertex. Vertex $4$ can be fourth in $(1,3,2,4,5)$, where vertices $1$, $2$, and $3$ are before it. Vertex $5$ can be fifth in $(1,3,2,4,5)$, where all smaller vertices are before it. Together with $(2,1)$, this gives $8$ good pairs. ` Vertex $4$ is never the fourth vertex. Vertex $3$ can be third, for example in $(1,2,3,4,5,6)$, but then among smaller vertices only vertex $1$ is before it. Vertex $5$ can be fifth after all smaller vertices, for example in $(1,3,4,2,5,6)$. Vertex $6$ can be sixth after all smaller vertices, for example in $(1,3,4,2,5,6)$. Therefore the answer is $1+1+4+5=11$. ` The DFS orders are $(1,2,4,5,3,6)$, $(1,2,5,4,3,6)$, $(1,3,6,2,4,5)$, and $(1,3,6,2,5,4)$. Vertex $3$ is never the third vertex. Vertex $4$ can be fourth only in orders starting with $(1,3,6,2)$, so only vertices $1$ and $2$ may be smaller vertices before it. Vertex $5$ can be fifth with vertices $1$, $2$, and $3$ before it. Vertex $6$ can be sixth after all smaller vertices, for example in $(1,2,4,5,3,6)$. Together with $(2,1)$, this gives $11$ good pairs. ` Every DFS order starts by completely visiting either the subtree of vertex $2$ or the subtree of vertex $3$. Therefore vertices $4$ and $5$ are never in their own numbered positions. Vertex $6$ can be sixth after all smaller vertices, for example in $(1,2,4,5,3,6,7)$. Vertex $7$ can be seventh after all smaller vertices, for example in $(1,2,4,5,3,6,7)$. Together with $(2,1)$, this gives $12$ good pairs.3e:Tc2c,#include #include "testlib.h" using namespace std; struct DSU { vector p, sz; DSU(int n = 0) { init(n); } void init(int n) { p.resize(n + 1); sz.assign(n + 1, 1); iota(p.begin(), p.end(), 0); } int find(int x) { if (p[x] == x) return x; return p[x] = find(p[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sz[a] < sz[b]) swap(a, b); p[b] = a; sz[a] += sz[b]; } }; bool possible(int n, const vector& l, const vector& r) { int m = (int)l.size(); if (n == 1) return true; vector ord(m); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int a, int b) { if (l[a] != l[b]) return l[a] < l[b]; return r[a] < r[b]; }); priority_queue, vector>, greater>> pq; int ptr = 0; for (int k = 1; k <= n - 1; k++) { while (ptr < m && l[ord[ptr]] <= k) { int id = ord[ptr]; pq.push({r[id], id}); ptr++; } while (!pq.empty() && pq.top().first <= k) { pq.pop(); } if (pq.empty()) return false; pq.pop(); } return true; } string to_upper(string s) { for (char &c : s) c = char(toupper((unsigned char)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(); int m = inf.readInt(); vector l(m), v(m), r(m); for (int i = 0; i < m; i++) { l[i] = inf.readInt(); v[i] = inf.readInt(); r[i] = inf.readInt(); } bool can = possible(n, l, r); string verdict = to_upper(ouf.readToken("[A-Za-z]+", "verdict")); if (verdict == "NO") { if (can) { quitf(_wa, "test case %d: contestant printed NO, but a solution exists", tc); } continue; } if (verdict != "YES") { quitf(_pe, "test case %d: expected YES or NO", tc); } if (!can) { quitf(_wa, "test case %d: contestant printed YES, but no solution exists", tc); } DSU dsu(n); for (int i = 0; i < m; i++) { int u = ouf.readInt(1, n, "u_i"); if (u < l[i] || u > r[i]) { quitf(_wa, "test case %d: u_%d = %d is outside [%d, %d]", tc, i + 1, u, l[i], r[i]); } dsu.unite(v[i], u); } int root = dsu.find(1); for (int i = 2; i <= n; i++) { if (dsu.find(i) != root) { quitf(_wa, "test case %d: the produced graph is not connected", tc); } } } // Lenient EOF: skip any leftover whitespace, only reject if real content remains while (ouf.seekEof() == false) { ouf.readToken(); } quitf(_ok, "accepted"); } 1b:["$","div",null,{"children":[["$","$L35",null,{"contestId":"69eeaea7b68e2fa971e12f48","contestNumber":6,"contestUrlId":"6","initialIsRegistered":false}],["$","$L36",null,{"contest":{"contestNumber":6,"title":"Repovive Premier Round 3","startDate":"2026-05-03T14:35:00.000Z","endDate":"2026-05-03T17:05:00.000Z","urlSlug":"$undefined","problemDisplay":"letters","requiresPremium":false,"lobbyProblemsCount":7,"isProblemSet":false,"contestType":"cp","adminOnly":false,"isWeeklyChallenge":"$undefined","weekNumber":"$undefined","ratedMaxTier":"$undefined","announcements":[]},"problems":[{"_id":"69f6bb6f9232943260e0edbe","contestId":"69eeaea7b68e2fa971e12f48","slug":"maximum-triangle-perimeter","title":"Maximum Triangle Perimeter","description":"You are given three sticks with integer lengths $a$, $b$, and $c$.\n\nYou may cut the sticks. In one cut, you choose one stick and decrease its length by a positive integer. All stick lengths must remain positive integers.\n\nFind the maximum possible perimeter of a non-degenerate triangle that can be made from the three sticks after some cuts. You may also make no cuts.\n","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le a, b, c \\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\n4 4 4\n3 4 10\n1 1 1000000\n7 2 4\n5 6 11","expectedOutput":"12\n13\n3\n11\n21","isSample":true,"hidden":false,"explanation":"The sticks are $4,4,4$. They already make a triangle, and the perimeter is $12$.\n`\nWe can cut the stick of length $10$ into length $6$. Then the sticks become $3,4,6$, and the perimeter is $13$.\n`\nWe can cut the stick of length $1000000$ into length $1$. Then the sticks become $1,1,1$, and the perimeter is $3$.\n`\nWe can cut the stick of length $7$ into length $5$. Then the sticks become $5,2,4$, and the perimeter is $11$.\n`\nWe can cut the stick of length $11$ into length $10$. Then the sticks become $5,6,10$, and the perimeter is $21$.","displayInput":"5\n`\n4 4 4\n`\n3 4 10\n`\n1 1 1000000000\n`\n7 2 4\n`\n5 6 11","displayOutput":"12\n`\n13\n`\n3\n`\n11\n`\n21"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\na \\quad b \\quad c\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\text{ans} \\; \\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":62,"attemptedCount":63,"tags":["greedy","sortings","math"],"learnPages":[{"title":"Hint 1","content":"Recall the **triangle inequality**: three positive side lengths $x \\le y \\le z$ form a non-degenerate triangle if and only if $x + y > z$.\n\nThe catch here is that you can only **shorten** sticks — never lengthen them. So the only way to fix an invalid triple is to reduce the longest stick $z$ until $x + y > z$.\n\nWhat does shortening do to the perimeter? Every cut decreases the total length, so you want to shorten as **little** as possible."},{"title":"Hint 2","content":"Sort the three lengths so that $a \\le b \\le c$.\n\n**Case 1:** $a + b > c$ already. Then no cut is needed — the original sticks already form a valid triangle. The perimeter is $a + b + c$, and since cutting can only reduce the total, this is maximal.\n\n**Case 2:** $a + b \\le c$. The only way to make a triangle is to shorten $c$ (the longest stick). The smallest valid $c'$ is $a + b - 1$ (shorten by $1$ less than the deficit). Any further shortening only reduces the perimeter further.\n\nSo the maximal perimeter in this case is $a + b + (a + b - 1) = 2(a + b) - 1$.\n\nThink about why shortening $a$ or $b$ instead would always give a smaller or equal perimeter."},{"title":"Solution","content":"$37"}],"hasLearnContent":true,"likeCount":5,"neutralCount":1,"dislikeCount":1,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-05-03T03:05:19.590Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"69f6835e8452353b8256cdc0","contestId":"69eeaea7b68e2fa971e12f48","slug":"one-cut-away","title":"Distinct Deletions","description":"You are given a string $s$ of length $n$ consisting of lowercase English letters, and an integer $k$.\n\nFor each $i$ with $1 \\le i \\le n-k+1$, erase the contiguous substring from position $i$ to position $i+k-1$, and write down the resulting string.\n\nAfter doing this for all possible values of $i$, count how many distinct strings have been written.","constraints":"- $1 \\le t \\le 10^4$\n- $2 \\le n \\le 2 \\times 10^5$\n- $1 \\le k < n$\n- $s$ consists of lowercase English letters\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$","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\n2 1\nab\n5 2\nababa\n5 3\nabcde\n7 3\nabacaba\n8 3\nabcabcaa","expectedOutput":"2\n1\n3\n5\n2","isSample":true,"hidden":false,"explanation":"Erasing the first character leaves b, and erasing the second character leaves a. These two strings are different.\n\n`\nEvery possible erasure leaves the string aba, so only one distinct string is written.\n\n`\nThe three resulting strings are de, ae, and ab. They are all different.\n\n`\nAll five possible erasures produce different strings.\n\n`\nThe first five erasures all produce abcaa. The last erasure produces abcab, so there are two distinct strings.","displayInput":"5\n`\n2 1\nab\n`\n5 2\nababa\n`\n5 3\nabcde\n`\n7 3\nabacaba\n`\n8 3\nabcabcaa","displayOutput":"2\n`\n1\n`\n3\n`\n5\n`\n2"}],"sampleCount":1,"inputFormat":"$$$t$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\quad k \\\\\ns\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":47,"attemptedCount":53,"tags":["strings"],"learnPages":[{"title":"Page 1","content":"Let $T_i$ be the string obtained after deleting the block of length $k$ starting at position $i$.\n\nSo for every $i$ with $1 \\le i \\le n-k+1$:\n\n$T_i = s_1s_2\\ldots s_{i-1} + s_{i+k}s_{i+k+1}\\ldots s_n$\n\nWe need to count how many distinct strings appear among:\n\n$T_1, T_2, \\ldots, T_{n-k+1}$\n\nBuilding all these strings directly would be too slow, because each resulting string can still have length close to $n$.\n\nInstead, we compare neighboring results: $T_i$ and $T_{i+1}$."},{"title":"Page 2","content":"Now compare $T_i$ and $T_{i+1}$.\n\nIn $T_i$, we delete:\n\n$s_i, s_{i+1}, \\ldots, s_{i+k-1}$\n\nIn $T_{i+1}$, we delete:\n\n$s_{i+1}, s_{i+2}, \\ldots, s_{i+k}$\n\nMost of these deleted characters are the same. Both deletions remove the characters from $s_{i+1}$ to $s_{i+k-1}$.\n\nThe only difference is:\n\nIn $T_i$, the character $s_i$ is deleted and $s_{i+k}$ remains.\n\nIn $T_{i+1}$, the character $s_{i+k}$ is deleted and $s_i$ remains.\n\nEverything else stays in the same order in both strings.\n\nTherefore:\n\n$T_i = T_{i+1}$ if and only if $s_i = s_{i+k}$."},{"title":"Page 3","content":"This gives us a very simple way to count the answer.\n\nWe start with $T_1$, so the answer is initially $1$.\n\nThen, for each $i$ from $1$ to $n-k$, we check whether moving the deleted block one position to the right creates a new string.\n\nFrom the previous observation:\n\nIf $s_i = s_{i+k}$, then $T_i = T_{i+1}$, so no new distinct string appears.\n\nIf $s_i \\ne s_{i+k}$, then $T_i \\ne T_{i+1}$, so one new distinct string appears.\n\nThus, the answer is:\n\n$1 +$ the number of indices $i$ such that $1 \\le i \\le n-k$ and $s_i \\ne s_{i+k}$."},{"title":"Page 4","content":"The final algorithm is straightforward.\n\nFor each test case, initialize:\n\n$ans = 1$\n\nThen iterate over all valid indices $i$ and compare $s_i$ with $s_{i+k}$.\n\nIn zero-based indexing, this means comparing $s[i]$ and $s[i+k]$ while $i+k < n$.\n\nWhenever these two characters are different, increase $ans$ by $1$.\n\nThe time complexity is $O(n)$ per test case.\n\nSince the sum of $n$ over all test cases is at most $2 \\times 10^5$, the total complexity is fast enough.\n\nThe memory usage is $O(1)$ apart from storing the input string."}],"hasLearnContent":true,"likeCount":1,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-05-02T23:06:06.604Z","updatedAt":"2026-06-28T22:22:26.596Z"},{"_id":"69f268456a0c0d94b2f2ba2c","contestId":"69eeaea7b68e2fa971e12f48","slug":"prefix-flip-transformation","title":"Prefix Flip Transformation","description":"Alice has two binary strings $S$ and $T$ of length $n$. She has a special machine that, given an index $i$ where the current $S_i$ is $1$, flips the entire prefix $S_1, S_2, \\ldots, S_i$ (changing $0$ to $1$ and $1$ to $0$). She can use this operation multiple times. Determine if she can transform $S$ into $T$ using at most $n$ operations, and if so, output any valid sequence of operations.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $S$ and $T$ are binary strings of length $n$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$","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":"5\n1\n0\n0\n1\n0\n1\n2\n11\n10\n5\n10101\n01100\n5\n00001\n00110","expectedOutput":"Yes\n0\n\nNo\nYes\n2\n1 2\nYes\n3\n5 2 4\nYes\n2\n5 2","isSample":true,"hidden":false,"explanation":"$38","displayInput":"5\n`\n1\n0\n0\n`\n1\n0\n1\n`\n2\n11\n10\n`\n5\n10101\n01100\n`\n5\n00001\n00110","displayOutput":"Yes\n0\n\n`\nNo\n`\nYes\n2\n1 2\n`\nYes\n3\n5 2 4\n`\nYes\n2\n5 2"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\nS \\\\\nT\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"For each test case, output one of the following forms:\n\n$$\n\\left.\n\\begin{array}{l}\n\\texttt{Yes} \\\\\nk \\\\\ni_1 \\; i_2 \\; \\ldots \\; i_k\n\\end{array}\n\\quad \\text{or} \\quad\n\\begin{array}{l}\n\\texttt{No}\n\\end{array}\n\\right\\} \\times t\n$$\n\nHere $k$ is the number of operations, $0 \\le k \\le n$, and $1 \\le i_j \\le n$ for every $1 \\le j \\le k$.\nThe operation indices must be valid in the given order. If there are multiple valid answers, you may output any of them.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$39"},"solvedCount":30,"attemptedCount":35,"tags":["strings","constructive"],"learnPages":[{"title":"Hint 1","content":"Find a necessary condition for transforming $S$ into $T$."},{"title":"Hint 2","content":"The necessary condition is: let $p$ be the last position where $S_p \\ne T_p$. Then $S_p = 1$."},{"title":"Hint 3","content":"Prove that this condition is also sufficient."},{"title":"Solution","content":"$3a"}],"hasLearnContent":true,"likeCount":1,"neutralCount":1,"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-04-29T20:21:25.202Z","updatedAt":"2026-06-30T21:11:23.536Z"},{"_id":"69f0ba34e84e302e82a5623a","contestId":"69eeaea7b68e2fa971e12f48","slug":"mark-and-move","title":"Cute Game on Graph","description":"Alice and Bob are playing a game on a simple undirected graph with $n$ vertices labeled from $1$ to $n$ and $m$ edges. Initially, a token is placed on vertex $1$.\n\nThey play in turns, and Alice plays first. In each turn:\n\n- Alice chooses one edge of the graph and marks it.\n- Then Bob may either keep the token on its current vertex, or move the token along one unmarked edge to an adjacent vertex.\n- After Bob's choice, the marked edge becomes unmarked again.\n\nBob may end the game at any moment, including before the first turn. When the game ends, the label of the vertex containing the token is called the outcome.\n\nAlice wants the outcome to be as small as possible. Bob wants the outcome to be as large as possible. Both players play optimally.\n\nFor each test case, determine the largest possible outcome that Bob can guarantee.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\cdot 10^5$\n- $0 \\le m \\le 2 \\cdot 10^5$\n- The sum of $n$ over all test cases does not exceed $2 \\cdot 10^5$.\n- The sum of $m$ over all test cases does not exceed $2 \\cdot 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\n1 0\n4 3\n1 2\n2 3\n3 4\n3 3\n1 2\n1 3\n2 3\n4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n6 6\n1 2\n1 3\n2 5\n2 6\n3 5\n3 6","expectedOutput":"1\n1\n2\n3\n5","isSample":true,"hidden":false,"explanation":"The token starts on the only vertex, so Bob can end the game immediately and get outcome $1$.\n\n`\nThe graph is a path. Whenever Bob is at vertex $1$, Alice can mark the only edge leaving it. Therefore Bob cannot guarantee reaching a larger label, and the answer is $1$.\n\n`\nAlice can mark only one of the two edges leaving vertex $1$. Bob can move through the other one and guarantee an outcome of at least $2$. However, Alice can stop Bob from guaranteeing vertex $3$, so the answer is $2$.\n\n`\nThe graph is complete on four vertices. Bob cannot guarantee reaching vertex $4$, because Alice can always mark the edge leading to it. But Bob can guarantee reaching either vertex $2$ or vertex $3$, so the answer is $3$.\n\n`\nBob cannot guarantee reaching vertex $6$ alone, because Alice can block the needed edge whenever there is only one way toward it. But vertices $5$ and $6$ together give Bob enough choices to force reaching a vertex with label at least $5$.","displayInput":"5\n`\n1 0\n`\n4 3\n1 2\n2 3\n3 4\n`\n3 3\n1 2\n1 3\n2 3\n`\n4 6\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n`\n6 6\n1 2\n1 3\n2 5\n2 6\n3 5\n3 6","displayOutput":"1\n`\n1\n`\n2\n`\n3\n`\n5"}],"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\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":24,"attemptedCount":27,"tags":["graphs","games"],"learnPages":[{"title":"Hint 1","content":"For each vertex, determine the largest vertex Bob can guarantee reaching when starting from it."},{"title":"Hint 2","content":"For each vertex, determine which edge Alice would block if she plays optimally."},{"title":"Solution","content":"$3b"}],"hasLearnContent":true,"likeCount":1,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-04-28T13:46:28.579Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"69f679548452353b8256cdbe","contestId":"69eeaea7b68e2fa971e12f48","slug":"mex-extension","title":"Mex Extension","description":"We define the score of an array $b_1,b_2,\\ldots,b_m$ as follows.\n\nStart with an empty set $S$.\n\nFor each $i$ from $1$ to $m$:\n\n1. Insert $b_i$ into $S$.\n2. After that, you may insert $\\operatorname{mex}(S)$ into $S$.\n\nThe second step can be used at most $k$ times in total.\nHere $\\operatorname{mex}(S)$ is the smallest non-negative integer that does not belong to $S$.\n\nThe score of the array is the maximum possible value of $\\operatorname{mex}(S)$ after all elements are processed.\n\nYou are given an array $a_1,a_2,\\ldots,a_n$.\nFor each $r$ with $1 \\le r \\le n$, output the score of the prefix $a_1,a_2,\\ldots,a_r$.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le k \\le n$\n- $0 \\le a_i \\le n$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$","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 1\n0\n4 1\n1 0 3 2\n5 2\n0 2 1 0 4\n6 3\n3 3 0 1 2 6\n7 4\n1 2 0 4 3 6 5","expectedOutput":"2\n2 3 4 5\n2 4 4 5 6\n1 2 4 4 5 7\n2 4 5 6 7 8 9","isSample":true,"hidden":false,"explanation":"$3c","displayInput":"5\n`\n1 1\n0\n`\n4 1\n1 0 3 2\n`\n5 2\n0 2 1 0 4\n`\n6 3\n3 3 0 1 2 6\n`\n7 4\n1 2 0 4 3 6 5","displayOutput":"2\n`\n2 3 4 5\n`\n2 4 4 5 6\n`\n1 2 4 4 5 7\n`\n2 4 5 6 7 8 9"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad k \\\\\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}\nf(1) \\quad f(2) \\quad \\cdots \\quad f(n)\n\\end{array}\n\\right\\} \\times t\n$$\n\nHere $f(r)$ is the score of the prefix $a_1,a_2,\\ldots,a_r$.","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":2,"attemptedCount":4,"tags":["data structures","dp"],"learnPages":[{"title":"Page 1","content":"The first observation is that, for a fixed prefix of length $r$, we can assume that all used operations are done as late as possible.\n\nLet $B_r=\\min(k,r)$. Then this prefix can use at most $B_r$ operations.\n\nIf an operation is done earlier, moving it to a later unused position cannot make the final mex smaller, because the set only gains more elements over time.\n\nSo for prefix $r$, in an optimal strategy, the operation positions are:\n\n$$\nr-B_r+1,\\ r-B_r+2,\\ldots,r\n$$"},{"title":"Page 2","content":"For each prefix $r$, define $p_r$ as the first operation position that has not been used yet.\n\nInitially,\n\n$$\np_r=r-\\min(k,r)+1\n$$\n\nIf $p_r>r$, then this prefix has no operation left.\n\nWhen we decide that prefix $r$ uses one operation, we simply do:\n\n$$\np_r \\leftarrow p_r+1\n$$"},{"title":"Page 3","content":"Now process the values $x=0,1,2,\\ldots$ in increasing order.\n\nLet $first_x$ be the first position where $x$ appears in the array. If $x$ does not appear, set:\n\n$$\nfirst_x=n+1\n$$\n\nWhen we are processing $x$, we assume all values smaller than $x$ have already been made present in the set whenever possible.\n\nFor a prefix $r$, if $p_rr\n$$\n\nand\n\n$$\nfirst_x>r\n$$\n\nThe first condition means that prefix $r$ has no operations left.\n\nThe second condition means that $x$ does not appear inside this prefix.\n\nSo $x$ cannot be inserted in any way. Since all smaller values were already inserted before, the final mex of this prefix is exactly $x$."},{"title":"Page 7","content":"We need to apply the rule above to many prefixes efficiently.\n\nFor a fixed value $x$, the prefixes that can use an operation for $x$ satisfy:\n\n$$\np_rr\n$$\n\nand\n\n$$\nr