37:I[290370,["/_next/static/immutable/chunks/3ug-ir7rz2so3.js","/_next/static/immutable/chunks/2fcecmiom-yvu.js","/_next/static/immutable/chunks/07tue-l4qhy1z.js","/_next/static/immutable/chunks/1gw-s2qr8_kwk.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/20gnsl3b8ay94.js","/_next/static/immutable/chunks/0vj574x3q80w8.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/3hr7horz176f3.js","/_next/static/immutable/chunks/3tw_xszkea-1d.js","/_next/static/immutable/chunks/1luxevw57bu34.js","/_next/static/immutable/chunks/22r4sosu4htjq.js","/_next/static/immutable/chunks/1caz--y7xrvl7.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/103b5z0pgu--4.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/3ht6tg8rhp4yg.js","/_next/static/immutable/chunks/0ynq5guyzm7n0.js","/_next/static/immutable/chunks/0kmsecthdxvjy.js","/_next/static/immutable/chunks/0b2wn-kj1hpzy.js"],"default"] 38:I[218728,["/_next/static/immutable/chunks/3ug-ir7rz2so3.js","/_next/static/immutable/chunks/2fcecmiom-yvu.js","/_next/static/immutable/chunks/07tue-l4qhy1z.js","/_next/static/immutable/chunks/1gw-s2qr8_kwk.js","/_next/static/immutable/chunks/2ol9wyej_s9h-.js","/_next/static/immutable/chunks/20gnsl3b8ay94.js","/_next/static/immutable/chunks/0vj574x3q80w8.js","/_next/static/immutable/chunks/437mepgwkzb8b.js","/_next/static/immutable/chunks/3hr7horz176f3.js","/_next/static/immutable/chunks/3tw_xszkea-1d.js","/_next/static/immutable/chunks/1luxevw57bu34.js","/_next/static/immutable/chunks/22r4sosu4htjq.js","/_next/static/immutable/chunks/1caz--y7xrvl7.js","/_next/static/immutable/chunks/3vuhqfn8nseb-.js","/_next/static/immutable/chunks/2ke2tvdiokend.js","/_next/static/immutable/chunks/103b5z0pgu--4.js","/_next/static/immutable/chunks/1atq4abfx_cwi.js","/_next/static/immutable/chunks/3ht6tg8rhp4yg.js","/_next/static/immutable/chunks/0ynq5guyzm7n0.js","/_next/static/immutable/chunks/0kmsecthdxvjy.js","/_next/static/immutable/chunks/0b2wn-kj1hpzy.js"],"default"] 39:T47c,Also, after one operation on a pair $(a_i, b_i)$, they move to some index $j$ in arrays $a$ and $b$ such that *$i$ and $j$ have different parity*. After a second operation on this pair, they move to some index $k$ such that *$i$ and $k$ have the same parity*. Continuing the same logic shows us that an odd number of operations on a pair moves it to an index with different parity, and an even number of operations moves it to an index with the same parity. Merging the facts from this page and the previous one shows that a pair $(a_i, b_i)$ will be swapped when it ends up at an index with different parity than $i$, and it will be unswapped otherwise. For convenience, call pairs with even $i$ **even pairs**, and pairs with odd $i$ **odd pairs**. Let $X$ be the number of odd pairs that end up in an even index after all operations, and $Y$ the number of even pairs that end up in an odd index. If $X \neq Y$, then the number of pairs occupying odd indices after all operations would differ from the number at the start, which is impossible — every odd index always contains exactly one pair, and the number of odd indices has not changed.3a:Td63,#include #include "testlib.h" using namespace std; struct SegTree { int n; vector one, lazy; SegTree(const string &s) { n = (int)s.size() - 1; one.assign(4 * n + 5, 0); lazy.assign(4 * n + 5, 0); build(1, 1, n, s); } void build(int id, int l, int r, const string &s) { if (l == r) { one[id] = s[l] - '0'; return; } int mid = (l + r) >> 1; build(id << 1, l, mid, s); build(id << 1 | 1, mid + 1, r, s); one[id] = one[id << 1] + one[id << 1 | 1]; } void apply(int id, int l, int r) { one[id] = (r - l + 1) - one[id]; lazy[id] ^= 1; } void push(int id, int l, int r) { if (!lazy[id] || l == r) return; int mid = (l + r) >> 1; apply(id << 1, l, mid); apply(id << 1 | 1, mid + 1, r); lazy[id] = 0; } void flip(int ql, int qr) { flip(1, 1, n, ql, qr); } void flip(int id, int l, int r, int ql, int qr) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { apply(id, l, r); return; } push(id, l, r); int mid = (l + r) >> 1; flip(id << 1, l, mid, ql, qr); flip(id << 1 | 1, mid + 1, r, ql, qr); one[id] = one[id << 1] + one[id << 1 | 1]; } int get(int pos) { return get(1, 1, n, pos); } int get(int id, int l, int r, int pos) { if (l == r) return one[id]; push(id, l, r); int mid = (l + r) >> 1; if (pos <= mid) return get(id << 1, l, mid, pos); return get(id << 1 | 1, mid + 1, r, pos); } }; bool possible(const string &s, const string &t) { int n = (int)s.size() - 1; int l = 1; while (l <= n && s[l] == t[l]) l++; if (l > n) return true; int r = n; while (s[r] == t[r]) r--; return s[l] == '1' && t[l] == '0' && s[r] == '0' && t[r] == '1'; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int tc = inf.readInt(); for (int testCase = 1; testCase <= tc; testCase++) { setTestCase(testCase); int n = inf.readInt(); string s = " " + inf.readToken(); string t = " " + inf.readToken(); bool can = possible(s, t); int k = ouf.readInt(-1, n, "k"); if (k == -1) { if (can) { quitf(_wa, "test case %d is possible, but contestant printed -1", testCase); } continue; } SegTree seg(s); for (int i = 1; i <= k; i++) { int l = ouf.readInt(1, n, "l_i"); int r = ouf.readInt(1, n, "r_i"); if (l >= r) { quitf(_wa, "test case %d, operation %d has l >= r", testCase, i); } if (seg.get(l) != 1) { quitf(_wa, "test case %d, operation %d has S_l = 0", testCase, i); } if (seg.get(r) != 0) { quitf(_wa, "test case %d, operation %d has S_r = 1", testCase, i); } seg.flip(l, r); } for (int i = 1; i <= n; i++) { if (seg.get(i) != t[i] - '0') { quitf(_wa, "test case %d does not end with T", testCase); } } } if (!ouf.seekEof()) { quitf(_pe, "extra output found"); } quitf(_ok, "accepted"); }3b:T609,Consider a star with $ 3 \leq k $ vertices. It's easy to see we can set value of all vertices to 2 except one leaf ( and it becomes 1) (with the aforementioned operations). so we can achieve total sum $2k - 1$ for such trees. We are going to proof it's maximum achievable value for these trees ( notice in these cases, we assumed that we are going to change all vertices at least once) **Proof:** suppose that we can achieve $2k$ and make all vertices 2. Call our star's center vertex $c$. Now we are going to introduce 2 Lemma : **Lemma 1: just before last operation, $c$ and some leaf called $u$, had values $0$ and $1$** - **Proof:** consider last operation. It will apply on our star's center ( call it $c$ ) and one leaf named $u$. and we know just before the last operation, $MEX({a_c,a_u}) = 2$, because they will be 2 at the end. so they are $0$ and $1$. **Lemma 2: Just before the last operation, value of $c$ was equal to value of at least one leaf:** - **Proof:** consider second last operation. (as we know $ 3 \leq k$, such operation exists). after this operation, values of $c$ and some leaf were equal ( because we applied this operation on them ) **Contradiction:** these two Lemma give us a contradiction. since before the last operation, at most one leaf's value going to change, so other leaves are equal to 2 . and the last leaf is either $0$ or $1$ and $c$'s value is the opposite, which contradicts Lemma 2. therefore we claimed for a star of size $k$ size will be at most $2k-1$ and also it's achievable. 3c:T62c,Now are going to split our tree in some marked and unmarked vertices such that : - Each marked component has size at least $2$ - For each unmarked vertex, we add it's initial value to answer - For each unmarked component of size $k$ , we will follow these rules : 1. if the component is an edge,add $max(MEX({a_u,a_v}),1) \cdot 2$ to answer 2. if the component is a star of size $ 3 \leq k $, add $2k-1$ to answer 3. otherwise, for a component of size $k$, $2k$ is achievable, add it to answer They all can be done with DP on tree's . there are several DP solutions for this. One of them is you can maintain these values for **each** vertex: ( In my opinion this method is less likely to cause bugs) `int d[4][3],f,g` `d[j][k]` for vertex $u$ means in $u$'s subtree, what is maximum sum if we suppose $u$ will be a marked vertex, and $min(diam,3)$ equals to `j` and $min(far,2)$ equals to `k` ( and only $u$'s component could be a single vertex, but for other vertices, rules are the same as we mentioned above) . where $diam$ is $u$'s component diameter and $far$ is distance of $u$ with the farthest vertex on it's component. `f` for vertex $u$ means in $u$'s subtree, what is maximum sum if we suppose $u$ will be an unmarked vertex. `g` for vertex $u$ means in $u$'s subtree, what is maximum sum if we suppose $u$ will be a marked vertex and it's component is an edge such that $MEX$ of their initial values is equal to $2$ These values could update together, so we will run a dfs and compute these values. Time Complexity is $O(n)$ with a High-constant factor. 19:["$","div",null,{"children":[["$","$L37",null,{"contestId":"6a079673e722ebe7820751cb","contestType":"cp","contestNumber":9,"contestUrlId":"9","initialIsRegistered":false}],["$","$L38",null,{"contest":{"contestNumber":9,"title":"Repovive Premier Round 4","startDate":"2026-05-24T14:35:00.000Z","endDate":"2026-05-24T17:05: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":"6a1176105a730f0fc88c73ac","contestId":"6a079673e722ebe7820751cb","slug":"max-mod","title":"Max Mod","description":"You are given an array $a_1, \\dots, a_n$.\n\nThe closeness between two indices $1 \\leq i \\neq j \\leq n$ is equal to $a_i \\bmod a_j$.\n\nFind the maximum possible closeness between two indices in the given array.","constraints":"- $1 \\leq t \\leq 10^4$\n- $2 \\leq n \\leq 2 \\times 10^5$\n- $1 \\leq a_i \\leq 10^9$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$","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":"3\n3\n1 5 6\n4\n2 2 5 1\n5\n1 1 1 1 1\n","expectedOutput":"5\n2\n0","isSample":true,"hidden":false,"explanation":"The closeness between indices 2 and 3 is 5, since $5 \\bmod 6 = 5$.\n\n`The closeness between indices 1 and 3 is 2, since $2 \\bmod 5 = 2$.\n\n`All numbers are equal, so the closeness between any two indices is 0, since $x \\bmod x = 0$.","displayInput":"3\n`3\n1 5 6\n`4\n2 2 5 1\n`5\n1 1 1 1 1","displayOutput":"5\n`2\n`0"}],"sampleCount":1,"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":"$$$\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":117,"attemptedCount":120,"tags":["math"],"learnPages":[{"title":"Hint","content":"$$x \\bmod y \\leq \\min(x, y)$"},{"title":"Page 2","content":"We prove the answer is always the second greatest number in the array (after removing duplicates). Let's call it $X$. To prove the answer is at most $X$, we have two cases for choosing two indices $1 \\leq i \\neq j \\leq n$:\n\n- $\\min(a_i, a_j) \\leq X$. In this case, using Hint 1 we can see the closeness is at most $X$.\n- $X < a_i, a_j$. Since the only number larger than $X$ in the array is the greatest number of the array, we have $a_i = a_j = \\max(a)$. So $a_i \\bmod a_j = a_i \\bmod a_i = 0$, which again makes the closeness at most $X$.\n\nNow we just need to find a pair with closeness equal to $X$. This pair will be the number $X$ and the maximum of the whole array. Since $x \\bmod y = x$ when $x < y$, we have $X \\bmod \\max(a) = X$.\n\nAlso, if every number in the array is equal, then $X$ is undefined. In that case, the answer is simply $0$."}],"hasLearnContent":true,"likeCount":78,"neutralCount":29,"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":"6910dbd9f636aa34a20ab8b2","name":"Bahamin Shafaghi"}],"statementOverrides":"$undefined","createdAt":"2026-05-23T09:40:32.257Z","updatedAt":"2026-06-01T19:33:57.975Z"},{"_id":"6a12ed86971a5b7fc95dc213","contestId":"6a079673e722ebe7820751cb","slug":"mex-weighted-split","title":"Meximus Minimus","description":"You are given two arrays $a_1, a_2, \\ldots, a_n$ and $b_1, b_2, \\ldots, b_n$.\n\nFor a subset $S$, define its score as:\n\n$$\nmex(\\{b_i \\mid i \\in S\\}) \\times \\sum_{i \\in S} a_i\n$$\n\nHere, $mex$ of a multiset of integers is the smallest non-negative integer that does not appear in it.\n\nNow Meximus Minimus Decimus Meridius, Prime Minister of Repovive land, wants to partition set $\\{1,2,,\\ldots,n\\}$ into exactly $k$ none-empty subsets such that sum of scores of these subsets is minimized. Find this minimum value.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le k \\le n \\le 2 \\times 10^5$\n- $0 \\le a_i \\le 10^6$\n- $0 \\le b_i \\le n$\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\n4 1\n2 3 1 5\n0 1 3 1\n5 2\n10 4 7 2 8\n0 2 1 0 3\n3 2\n5 6 7\n1 2 3\n4 3\n1 2 3 4\n0 0 0 0\n5 1\n1 2 3 4 5\n0 1 2 3 4\n","expectedOutput":"22\n12\n0\n10\n75","isSample":true,"hidden":false,"explanation":"All indices must be placed in one subset. The MEX of the values $0,1,3,1$ is $2$, and the sum of the corresponding $a_i$ values is $11$, so the score is $22$.\n`\nOne optimal partition is $\\{1,4\\}$ and $\\{2,3,5\\}$. The first subset has score $1 \\times 12 = 12$, and the second subset has MEX $0$, so its score is $0$.\n`\nThere is no index with $b_i=0$. Therefore, both subsets can have MEX $0$, and the total score is $0$.\n`\nEvery index has $b_i=0$. No matter how the indices are partitioned, each subset has MEX $1$, so the total score is $1+2+3+4=10$.\n`\nAll indices must be placed in one subset. The MEX of the values $0,1,2,3,4$ is $5$, and the sum of the corresponding $a_i$ values is $15$, so the score is $75$.","displayInput":"5\n`4 1\n2 3 1 5\n0 1 3 1\n`5 2\n10 4 7 2 8\n0 2 1 0 3\n`3 2\n5 6 7\n1 2 3\n`4 3\n1 2 3 4\n0 0 0 0\n`5 1\n1 2 3 4 5\n0 1 2 3 4","displayOutput":"`22\n`12\n`0\n`10\n`75"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\quad k \\\\\na_1 \\quad a_2 \\quad \\cdots \\quad a_n \\\\\nb_1 \\quad b_2 \\quad \\cdots \\quad b_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":91,"attemptedCount":95,"tags":["math"],"learnPages":[{"title":"Hint 1","content":"consider case $k = 1$, in this case answer is obvious, just MEX of $b_i$'s multiply to sum of $a_i$'s."},{"title":"Hint 2","content":"Otherwise, look at indices $i$ such that $b_i = 0$\n\nLet put such indices into a subset named $R$ \n\n\nEach subsequence that contains at least one index from $R$, Its MEX is at least 1. so our total answer is at least \n$\\sum_{i \\in R} a_i$ "},{"title":"solution","content":"So for case $k=1$ everything is straightforward. \n\nOtherwise our answer is at least $\\sum_{i \\in R} a_i$ . and also there is a partition with this total value . let $x=|R|$ . \n\n**Case 1 :** $ x >= k-1 $ :\nwe can put all elements in $R$ into $k-1$ subsequence in an arbitrary way and then put all remaining elements to $k$'th subsequence. \n\n**Case 2 :** $ x < k-1 $ : we can put each element in $R$ into one subsequence ( as a single element ) and distribute all remaining elements arbitrarily among the other $k - x$ subsequences. \n\nso when $k$ is at least 2, answer is just $\\sum_{i \\in R} a_i$."}],"hasLearnContent":true,"likeCount":60,"neutralCount":17,"dislikeCount":6,"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":"692c8d654025526e26fb9c49","name":"mohammadsam ansaripoor"}],"statementOverrides":"$undefined","createdAt":"2026-05-24T12:22:30.168Z","updatedAt":"2026-06-10T00:21:37.410Z"},{"_id":"6a1175fc5a730f0fc88c73ab","contestId":"6a079673e722ebe7820751cb","slug":"weird-swaps","title":"Weird Swaps","description":"You are given two arrays $a_1, a_2, \\dots, a_n$ and $b_1, b_2, \\dots, b_n$.\n\nIn each operation you can choose two numbers $l$ and $r$ such that:\n- $1 \\leq l < r \\leq n$ \n- $r - l + 1$ is even\n\nThen for every $l \\leq i \\leq r$, swap $a_i$ with $b_{l + r - i}$.\n\nFind the maximum sum of array $a$ after any number of operations (including zero).","constraints":"- $1 \\leq t \\leq 10^4$\n- $1 \\leq n \\leq 2 \\times 10^5$ \n- $0 \\leq a_i, b_i \\leq 10^9$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$\n","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":"4\n3\n1 1 1\n2 2 2\n5\n5 1 2 2 4\n1 9 3 3 4\n4\n3 9 9 0\n2 0 4 2\n4\n9 3 9 0\n0 2 4 2\n","expectedOutput":"5\n24\n22\n21","isSample":true,"hidden":false,"explanation":"An operation on segment $[1, 2]$ will swap $a_1 \\leftrightarrow b_2$ and $a_2 \\leftrightarrow b_1$, resulting in $a = [2, 2, 1]$ with sum equal to 5.\n\n`An operation on segment $[2, 5]$ will swap $a_2 \\leftrightarrow b_5, a_3 \\leftrightarrow b_4, a_4 \\leftrightarrow b_3$ and $a_5 \\leftrightarrow b_2$, resulting in $a = [5, 4, 3, 3, 9]$ with sum equal to 24.\n\n`One operation on segment $[1, 4]$ will result in $a = [2, 4, 0, 2], b = [0, 9, 9, 3]$. Another operation on segment $[2, 3]$ will result in $a = [2, 9, 9, 2]$ with sum equal to 22.\n\n`No operation needed.","displayInput":"4\n`3\n1 1 1\n2 2 2\n`5\n5 1 2 2 4\n1 9 3 3 4\n`4\n3 9 9 0\n2 0 4 2\n`4\n9 3 9 0\n0 2 4 2","displayOutput":"5\n`24\n`22\n`21"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\na_1 \\quad a_2 \\quad \\cdots \\quad a_n \\\\\nb_1 \\quad b_2 \\quad \\cdots \\quad b_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":48,"attemptedCount":55,"tags":["greedy","sortings"],"learnPages":[{"title":"Page 1","content":"Let's track numbers $a_i$ and $b_i$. After an operation $a_i$ will go to $b_j$ for some index $j$. It can be seen $b_i$ will also go to $a_j$. Repeating the same logic, it can be seen that numbers $a_i$ and $b_i$ are stuck together: if one of them ends up at the $j$-th index of array $a$, the other one will surely be at the $j$-th index of array $b$.\n\nNow call a pair $(a_i, b_i)$ **swapped** if after all operations, $a_i$ is in array $b$ and $b_i$ is in array $a$.\n\nBased on the previous fact, the sum of $a$ is the sum of $a_i$ for unswapped pairs plus the sum of $b_i$ for swapped pairs."},{"title":"Page 2","content":"Imagine a new operation in which we can choose two indices $i$ and $j$ such that:\n- $1 \\leq i < j \\leq n$\n- $i \\not \\equiv j \\pmod{2}$\n\nand swap $a_i \\leftrightarrow b_j$ and $a_j \\leftrightarrow b_i$. It can be shown that this operation and the one given in the problem are equivalent, and thus the maximum sum reachable using this new operation is equal to the answer of the problem."},{"title":"Page 3","content":"To prove the equivalence, we first show how to create the new operation using the problem's operation. There are two cases:\n- The new operation is applied at two indices $i$ and $i + 1$. In this case, applying the problem's operation on segment $[i, i + 1]$ gives the same result.\n- The new operation is applied at two indices $i$ and $j$ such that $i < j - 2$. In this case, applying the problem's operation first on segment $[i, j]$ and then on segment $[i + 1, j - 1]$ gives the same result.\n\nNow we prove we can create the problem's operation using the new operation. Suppose the problem's operation is applied on segment $[l, r]$. You just need to repeatedly apply the new operation on pairs of indices $(i, l + r - i)$ for all $l \\leq i \\leq \\frac{l + r - 1}{2}$."},{"title":"Page 4","content":"From now on we only discuss the new operation. \n\nLet's again track a pair $(a_i, b_i)$ which is unswapped at first. After the first operation on this pair, it becomes swapped. After the second operation on this pair, it becomes unswapped again. Continuing the same logic shows us that an odd number of operations on a pair makes it swapped, and an even number of operations makes it unswapped."},{"title":"Page 5","content":"$39"},{"title":"Page 6","content":"So we proved the number of swapped odd pairs should be equal to the number of swapped even pairs. Now take a set $S$ of pairs with this condition. Imagine there are both $X$ odd pairs and $X$ even pairs. Apply $X$ operations each time on one of the odd pairs and one of the even pairs such that at the end an operation is applied to all pairs in $S$. Since the number of odd pairs and even pairs are equal there is exactly one operation applied to all pairs in $S$ and no operation applied to pairs outside of $S$. So all the swapped pairs are exactly the ones inside $S$.\n\nSo we prove that it is necessary and sufficient that the number of swapped odd pairs and swapped even pairs are equal."},{"title":"Page 7","content":"Finally, to calculate the answer, we can first set all pairs as unswapped and then compute the gain from turning a pair swapped, which is simply $b_i - a_i$. Now we go through all $1 \\leq i \\leq \\frac{n}{2}$: add the $i$ largest differences from odd indices and the $i$ largest differences from even indices to the all-unswapped sum. The answer is the maximum among the numbers obtained this way."}],"hasLearnContent":true,"likeCount":34,"neutralCount":9,"dislikeCount":3,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"6910dbd9f636aa34a20ab8b2","name":"Bahamin Shafaghi"}],"statementOverrides":"$undefined","createdAt":"2026-05-23T09:40:12.087Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6a123ca150db7da5bacc2fa6","contestId":"6a079673e722ebe7820751cb","slug":"flip-one-then-zero","title":"Flip 1...0","description":"You are given two binary strings $S$ and $T$, both of length $n$.\n\nIn one operation, you may choose two indices $l$ and $r$ such that $1 \\le l < r \\le n$, $S_l = 1$, and $S_r = 0$ in the current string. Then you invert every bit in the segment $S_l, S_{l+1}, \\ldots, S_r$.\n\nIn other words, every $0$ in this segment becomes $1$, and every $1$ becomes $0$.\n\nYour task is to transform $S$ into $T$ using at most $n$ operations, or determine that it is impossible.\n\nIf there are multiple valid answers, you may output any of them.","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":4,"label":"$undefined","releaseDay":"$undefined","points":2000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n4\n1010\n0001\n3\n110\n100\n5\n01010\n01010\n4\n1100\n0101\n6\n111000\n010101\n","expectedOutput":"2\n1 2\n2 4\n-1\n0\n2\n2 3\n1 4\n3\n2 4\n1 5\n3 6","isSample":true,"hidden":false,"explanation":"After applying operation $[1,2]$, the string becomes $0110$. Then applying operation $[2,4]$ changes it to $0001$.\n\n`\nIt is impossible to transform $110$ into $100$ using valid operations.\n\n`\nThe initial string is already equal to the target string, so no operation is needed.\n\n`\nAfter applying operation $[2,3]$, the string becomes $1010$. Then applying operation $[1,4]$ changes it to $0101$.\n\n`\nAfter applying operation $[2,4]$, the string becomes $100100$. Then applying operation $[1,5]$ changes it to $011010$. Finally, applying operation $[3,6]$ changes it to $010101$.","displayInput":"5\n`\n4\n1010\n0001\n`\n3\n110\n100\n`\n5\n01010\n01010\n`\n4\n1100\n0101\n`\n6\n111000\n010101","displayOutput":"2\n1 2\n2 4\n`\n-1\n`\n0\n`\n2\n2 3\n1 4\n`\n3\n2 4\n1 5\n3 6"}],"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, if it is impossible to transform $S$ into $T$, output:\n\n$$\n-1\n$$\n\nOtherwise, output an integer $k$, the number of operations.\n\nThen output $k$ lines. In the $i$-th line, output two integers $l_i$ and $r_i$, meaning that the $i$-th operation is applied to the segment $[l_i, r_i]$.\n\nThe operations must be valid when they are applied, and after applying all operations the string must become equal to $T$.\n\nIt must hold that $0 \\le k \\le n$.\n\nIf there are multiple valid answers, you may output any of them.","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$3a"},"solvedCount":8,"attemptedCount":9,"tags":["strings","constructive"],"learnPages":[{"title":"Page 1","content":"Let $S$ be the current string.\n\nIf $S = T$, we need $0$ operations.\n\nOtherwise, let $L$ be the first index from the left such that $S_L \\ne T_L$.\n\nAlso let $R$ be the first index from the right such that $S_R \\ne T_R$.\n\nFor a transformation to be possible, we must have:\n\n$S_L = 1$ and $T_L = 0$\n\nand\n\n$S_R = 0$ and $T_R = 1$.\n\nIf one of these conditions is false, the answer is impossible."},{"title":"Page 2","content":"Why are these conditions necessary?\n\nIn one operation, we choose $[l,r]$ with current $S_l = 1$ and current $S_r = 0$.\n\nAfter flipping this segment, position $l$ changes from $1$ to $0$.\n\nSo the first changed position from the left must be of type $1 \\to 0$.\n\nSimilarly, position $r$ changes from $0$ to $1$.\n\nSo the first changed position from the right must be of type $0 \\to 1$."},{"title":"Page 3","content":"Now we prove that these conditions are sufficient.\n\nWe use induction on the length of the segment $[L,R]$.\n\nInside $[L,R]$, let $x$ be the first index after $L$ such that $S_x = T_x$.\n\nAlso let $y$ be the first index before $R$ from the right such that $S_y = T_y$.\n\nIf there is no such index, then every position in $[L,R]$ is different between $S$ and $T$.\n\nSo one operation on $[L,R]$ flips all of them, and the transformation is finished."},{"title":"Page 4","content":"Suppose $x$ exists and $S_x = T_x = 0$.\n\nThen the operation $[L,x]$ is valid, because current $S_L = 1$ and current $S_x = 0$.\n\nAfter applying it, position $L$ becomes correct.\n\nPosition $x$ becomes different, and now it is of type $1 \\to 0$.\n\nThe right endpoint condition at $R$ is still $0 \\to 1$.\n\nSo the remaining problem on $[x,R]$ again satisfies the same necessary and sufficient conditions.\n\nWe solve it by induction."},{"title":"Page 5","content":"Similarly, suppose $y$ exists and $S_y = T_y = 1$.\n\nThen the operation $[y,R]$ is valid, because current $S_y = 1$ and current $S_R = 0$.\n\nAfter applying it, position $R$ becomes correct.\n\nPosition $y$ becomes different, and now it is of type $0 \\to 1$.\n\nThe left endpoint condition at $L$ is still $1 \\to 0$.\n\nSo the remaining problem on $[L,y]$ again satisfies the same conditions.\n\nWe solve it by induction."},{"title":"Page 6","content":"The only remaining case is:\n\n$S_x = T_x = 1$\n\nand\n\n$S_y = T_y = 0$.\n\nFirst apply the operation $[L,R]$.\n\nThis operation is valid because $S_L = 1$ and $S_R = 0$.\n\nAfter this operation, $L$ and $R$ become correct.\n\nAlso, $x$ becomes different of type $0 \\to 1$, and $y$ becomes different of type $1 \\to 0$."},{"title":"Page 7","content":"Now the remaining different segment is inside $[x,y]$.\n\nFrom the left, the first different position is $x$.\n\nFrom the right, the first different position is $y$.\n\nBut after flipping $[L,R]$, we have:\n\ncurrent $S_x = 0$, $T_x = 1$\n\nand\n\ncurrent $S_y = 1$, $T_y = 0$.\n\nSo if we look at this segment in the opposite direction, it has exactly the same structure.\n\nEquivalently, we can apply the same recursive construction to the segment $[x,y]$ after reversing its direction.\n\nThis finishes the proof."},{"title":"Page 8","content":"The recursive construction always reduces the active segment.\n\nIn the first case, $L$ moves to $x$.\n\nIn the second case, $R$ moves to $y$.\n\nIn the last case, the segment becomes $[x,y]$, which is strictly smaller than $[L,R]$.\n\nTherefore, after at most $n$ recursive steps, the process stops.\n\nEach step adds at most one operation.\n\nSo the number of operations is at most $n$."},{"title":"Page 9","content":"Implementation idea:\n\nMaintain the current string $S$.\n\nAt each step, find the first and last positions where $S$ and $T$ differ.\n\nThen find $x$ and $y$ as described.\n\nApply one of the three cases and store the operation.\n\nA segment tree with lazy propagation can maintain:\n\nwhether $S_i = T_i$\n\nand the current value of $S_i$.\n\nThis allows all searches and flips in $O(\\log n)$.\n\nThe total complexity is $O(n \\log n)$."}],"hasLearnContent":true,"likeCount":13,"neutralCount":5,"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-23T23:47:45.338Z","updatedAt":"2026-06-30T21:11:23.536Z"},{"_id":"6a10c6bf4cb96a9f56f6a0a9","contestId":"6a079673e722ebe7820751cb","slug":"meximus","title":"Meximus Decimus","description":"In the land of Repovive, there are $n$ cities numbered $1$ through $n$, connected by roads that form a tree. Initially, city $i$ has $a_i$ soldiers.\n\nMeximus Decimus Meridius wants to maximize the country's total military strength. As you can see on his name, he really likes MEX. So he may perform the following operation as many times as he wishes:\n\n- Pick two adjacent cities $u$ and $v$. Let $x$ and $y$ be their current soldier counts, respectively. \n- Then replace both $a_u$ and $a_v$ with $\\operatorname{mex}(\\{x, y\\})$ — the smallest non-negative integer that does **not** appear in $\\{x, y\\}$.\n\nWhat is the maximum possible value of $\\sum_{i=1}^n a_i$ after any sequence of operations?","constraints":"- $ 1 \\le t \\le 1000 $ \n- $1 \\leq n \\leq 3 \\times 10^5$\n- $0 \\leq a_i \\leq 10^9$\n- the sum of $n$ over all test cases is at most $3 \\times 10^5$","difficulty":"hard","order":5,"label":"$undefined","releaseDay":"$undefined","points":3000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n2\n3 0\n1 2\n6\n6 0 1 0 1 1\n1 2\n2 3\n1 4\n4 5\n1 6\n6\n6 0 0 0 0 1\n1 2\n2 3\n1 4\n4 5\n1 6\n","expectedOutput":"3\n15\n12","isSample":true,"hidden":false,"explanation":"No operation can increase the sum. Initially $a = [3, 0]$ with sum $3$. Operating on the two cities gives $\\operatorname{mex}(\\{3, 0\\}) = 1$, replacing both with $1$ and reducing the sum to $2$. So the maximum is the initial sum $3$.`Pair each $0$ with a $1$: $\\operatorname{mex}(\\{0, 1\\}) = 2$. After two such operations we get $[6, 2, 2, 2, 2, 1]$, yielding sum $6 + 2 + 2 + 2 + 2 + 1 = 15$.`it's possible to make $[2, 2, 2, 2, 2, 2]$","displayInput":"3\n`\n2\n3 0\n1 2\n`\n6\n6 0 1 0 1 1\n1 2\n2 3\n1 4\n4 5\n1 6\n`\n6\n6 0 0 0 0 1\n1 2\n2 3\n1 4\n4 5\n1 6","displayOutput":"3\n`\n15\n`\n12"}],"sampleCount":1,"inputFormat":"$$$t$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\na_1 \\quad a_2 \\quad \\ldots \\quad a_n \\\\\nu_1 \\quad v_1 \\\\\nu_2 \\quad v_2 \\\\\n\\vdots \\\\\nu_{n-1} \\quad v_{n-1}\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$ans \\; \\} \\times t$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":3,"attemptedCount":6,"tags":["trees","dp"],"learnPages":[{"title":"Hint 1","content":"Consider all vertices that they were on at least one operation, we call them **marked**. consider marked vertices on tree, They form some components in tree and components are independent. so if we fix marked vertices, we should just solve each component independently and then sum up answers. also notice that because MEX of two numbers is at most 2, marked vertices have value at most 2 at the end. "},{"title":"Hint 2 ","content":"So consider we are going to change all values of a tree, will we achieve value 2 for all of them? "},{"title":"Hint 3","content":"**Basic Operations**:\n\n**First**: It's obvious we can change value of two adjacent vertex to $[0,0]$. (Either their MEX is 0 , or they become two equal number, then we can make them 0) \n\n**Second**:\nwe can choose three vertices $u,v,w$ such that they form a path of length 2. we can change values of this path to $[1,2,2]$ in order. (regardless of their initial values)\n\n**by this way:**\n\n\n\n$[a_u,a_v,a_w] \\Rightarrow [0,0,a_w] \\Rightarrow [0,0,0] \\Rightarrow [0,1,1] \\Rightarrow [2,2,1]$ "},{"title":"Solving a path with length at least 3","content":"Consider a path with at least 4 vertex. We will make all of them 2 (regardless of their initial values). Consider our path contains vertices $[a_1,a_2,\\ldots,a_k]$ such that $ 4 \\le k $ .\n\nAt first, we make all of them to $0$ . Then do the operation that we said on the paths in order : \n\nFirst make $a_{k-2},a_{k-1},a_k$ to $[1,2,2]$ \n\n\nSecond make $a_{k-3},a_{k-2},a_{k-1}$ to $[1,2,2]$ \n\n$\\ldots$\n\nFinally make $a_2,a_3,a_4$ to $[1,2,2]$\n\nNow all vertices $a_i$ such that $ 3 \\leq i $ are equal to $2$ . And we have $a_2 = 1$ and $a_1 = 0$ . So it's easy to make them $2$ too!"},{"title":"Solving a tree with diameter at least 3 ","content":"Consider a tree with diameter at least 3. We can take a leaf named $u$ , and take a path of length 2 that ends in $u$ and set their values to $[1,2,2]$ in order, so $a_u$ becomes 2 and we can remove it from our tree. \n\n**Claim:** By repeating this process for leaves that they don't lie on diameter, We set the values of all vertices to 2 except vertices of diameter. and then eventually set the values of vertices of diameter to 2 by the previous page's solution. "},{"title":"solving a star with size at least 3","content":"$3b"},{"title":"Solving an edge","content":"This one is easy (unlike the last one). Either we are going to do 2 operation's or more, In this case our values will be at most 1, Or we are going to do exactly 1 operation, and our values will become $MEX({a_u,a_v)}$ . both are achievable. so our maximum sum is :\n\n\n- $max(MEX({a_u,a_v}),1) \\cdot 2$"},{"title":"Solve whole problem","content":"$3c"}],"hasLearnContent":true,"likeCount":2,"neutralCount":3,"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":"692c8d654025526e26fb9c49","name":"mohammadsam ansaripoor"}],"statementOverrides":"$undefined","createdAt":"2026-05-22T21:12:31.038Z","updatedAt":"2026-06-13T14:06:37.833Z"},{"_id":"6a12dd07971a5b7fc95dc212","contestId":"6a079673e722ebe7820751cb","slug":"max-inversions","title":"Expected Beauty","description":"You are given an array $a_1, a_2, \\ldots, a_n$.\n\nYou perform the following operation exactly $k$ times.\n\nChoose two integers $l$ and $r$ uniformly at random among all pairs satisfying $1 \\le l \\le r \\le n$, then reverse the subarray $a_l, a_{l+1}, \\ldots, a_r$.\n\nThe operations are independent.\n\nThe beauty of an array $b$ is defined as\n\n$$\n\\sum_{1 \\le x < y \\le n} \\max(0, b_x - b_y).\n$$\n\nCompute the expected value of the beauty of the final array modulo $998244353$.\n\nFormally, if the expected value can be written as an irreducible fraction $\\frac{p}{q}$, output $p \\times q^{-1}$ modulo $998244353$.\n","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 10^6$\n- The sum of $n$ over all test cases is at most $10^6$\n- $0 \\le k \\le 10^9$\n- $1 \\le a_i \\le 10^9$","difficulty":"hard","order":6,"label":"$undefined","releaseDay":"$undefined","points":3250,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n1 100\n7\n2 0\n5 2\n2 1\n5 2\n3 1\n3 1 2\n10 3\n10 1 9 2 8 3 7 4 6 5\n","expectedOutput":"0\n3\n2\n499122179\n969444607","isSample":true,"hidden":false,"explanation":"The array has only one element, so the beauty is always $0$.\n\n`\nNo operation is performed, so the beauty remains $3$.\n\n`\nThere are $3$ possible segments, and the expected beauty is $2$.\n\n`\nAfter one operation, the expected beauty is $\\frac{5}{2}$.\n\n`\nThis is a larger sample with $n=10$ and $k=3$.","displayInput":"5\n`\n1 100\n7\n`\n2 0\n5 2\n`\n2 1\n5 2\n`\n3 1\n3 1 2\n`\n10 3\n10 1 9 2 8 3 7 4 6 5","displayOutput":"0\n`\n3\n`\n2\n`\n499122179\n`\n969444607"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\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}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":4,"attemptedCount":4,"tags":["probabilities","sortings","math"],"learnPages":[],"hasLearnContent":false,"likeCount":7,"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":"693ec41cee31b76718456be1","name":"Mohammad Shayan"}],"statementOverrides":"$undefined","createdAt":"2026-05-24T11:12:07.963Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6a12364b50db7da5bacc2fa5","contestId":"6a079673e722ebe7820751cb","slug":"xor-rank-path","title":"Path XOR Rank","description":"You are given a tree with $n$ vertices. Vertex $i$ has a value $a_i$.\n\nFor every ordered pair of vertices $(u,v)$ with $1 \\le u,v \\le n$, write down the xor of all values on the simple path from $u$ to $v$.\n\nThere are exactly $n^2$ written numbers.\n\nFind the $k$-th smallest number among them.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le k \\le n^2$\n- $0 \\le a_i < 2^{30}$\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$\n- The given edges form a tree","difficulty":"hard","order":7,"label":"$undefined","releaseDay":"$undefined","points":3500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n1 1\n5\n2 3\n5 3\n1 2\n3 5\n1 2 4\n1 2\n2 3\n4 7\n0 7 7 1\n1 2\n1 3\n3 4\n5 12\n2 2 5 1 4\n1 2\n1 3\n3 4\n3 5\n","expectedOutput":"5\n6\n4\n6\n3","isSample":true,"hidden":false,"explanation":"The written numbers are:\n$(1,1)$: path $1$, xor $5$.\nAfter sorting, the first one is $5$.\n`\nThe written numbers are:\n$(1,1)$: path $1$, xor $5$.\n$(1,2)$: path $1,2$, xor $5 \\oplus 3 = 6$.\n$(2,1)$: path $2,1$, xor $3 \\oplus 5 = 6$.\n$(2,2)$: path $2$, xor $3$.\nAfter sorting them as $3, 5, 6, 6$, the third one is $6$.\n`\nThe sorted written numbers are $1, 2, 3, 3, 4, 6, 6, 7, 7$. The fifth one is $4$.\n`\nThe sorted written numbers are $0, 0, 0, 1, 1, 1, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7$. The seventh one is $6$.\n`\nThe sorted written numbers are $0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7$. The twelfth one is $3$."}],"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 \\\\\nu_1 \\quad v_1 \\\\\nu_2 \\quad v_2 \\\\\n\\vdots \\\\\nu_{n-1} \\quad v_{n-1}\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":4.7,"memoryLimit":512,"checker":{"type":"wcmp"},"solvedCount":4,"attemptedCount":6,"tags":["trees","bitmasks"],"learnPages":[{"title":"Page 1","content":"We want the $k$-th smallest value among all $n^2$ ordered paths.\n\nInstead of generating all values, we build the answer bit by bit from high to low.\n\nSuppose we already fixed the higher bits of the answer. For the current bit, we first try to keep it equal to $0$.\n\nLet $b$ be the current bit. We count how many ordered paths have:\n\n$pathXor >> b = pref$\n\nwhere $pref$ is the prefix of the answer if the current bit is $0$.\n\nIf this count is at least $k$, then the current bit is $0$.\n\nOtherwise, the current bit is $1$, and we subtract this count from $k$."},{"title":"Page 2","content":"Now we need to count paths with a given xor prefix.\n\nUse centroid decomposition.\n\nFor a centroid $c$, define for every vertex $v$ in its current component:\n\n$x_v = xor(c \\rightarrow v)$\n\nIf the path from $u$ to $v$ passes through $c$, then:\n\n$xor(u \\rightarrow v) = x_u \\oplus x_v \\oplus a_c$\n\nSo for a fixed prefix $pref$ and bit $b$, we need:\n\n$(x_u >> b) \\oplus (x_v >> b) = pref \\oplus (a_c >> b)$\n\nThis becomes a standard xor-pair counting problem inside a list of numbers."},{"title":"Page 3","content":"For each centroid $c$, collect these lists:\n\n$all_c$: values $x_v$ for all vertices in the current centroid component.\n\nFor each child component after removing $c$, collect a list $part_i$.\n\nCounting pairs in $all_c$ counts all paths whose endpoints are in the centroid component.\n\nBut paths whose two endpoints are inside the same $part_i$ do not pass through $c$, so we subtract them.\n\nTherefore the number of unordered non-single paths whose highest prefix is $pref$ and whose responsible centroid is $c$ is:\n\n$count(all_c) - \\sum count(part_i)$\n\nEach non-single path is counted exactly once in centroid decomposition."},{"title":"Page 4","content":"For a list $L$, we need to count pairs $(i,j)$ with $i < j$ such that:\n\n$(L_i >> b) \\oplus (L_j >> b) = target$\n\nThis can be done with a frequency map:\n\nFor every value $x$ in the list, let $y = x >> b$.\n\nBefore inserting $y$, add the number of previous values equal to $y \\oplus target$.\n\nThen insert $y$.\n\nThis counts unordered pairs inside the list."},{"title":"Page 5","content":"The problem asks about ordered paths.\n\nFor every non-single path between two distinct vertices, both orders $(u,v)$ and $(v,u)$ exist and have the same xor.\n\nSo after counting unordered non-single paths, we multiply their contribution by $2$.\n\nSingle paths $(v,v)$ are counted separately. Their xor is simply $a_v$.\n\nSo for a prefix $pref$ and bit $b$:\n\n$total = singles + 2 \\times nonSingle$\n\nwhere $singles$ is the number of vertices with:\n\n$a_v >> b = pref$"},{"title":"Page 6","content":"Algorithm:\n\n1. Build centroid decomposition.\n\n2. For every centroid, store:\n $all_c$\n all lists $part_i$\n\n3. Initialize $ans = 0$.\n\n4. For $b = 29, 28, \\ldots, 0$:\n Try keeping bit $b$ equal to $0$.\n Count how many ordered paths have xor prefix equal to this candidate.\n If the count is at least $k$, keep the bit $0$.\n Otherwise, set bit $b$ to $1$ and subtract the count from $k$.\n\n5. After all bits, $ans$ is the $k$-th smallest path xor."},{"title":"Page 7","content":"Why it is correct:\n\nThe bit-by-bit process is the usual order-statistic construction.\n\nAt each step, all values with the candidate prefix are smaller than all values with the same higher prefix but current bit equal to $1$.\n\nSo if there are at least $k$ values with the candidate prefix, the answer must stay there.\n\nOtherwise, all those values are before the answer, so we skip them and continue with the current bit equal to $1$.\n\nThe centroid decomposition counting is correct because every non-single path has a unique first centroid that separates its two endpoints. That centroid counts it once, and no other centroid counts it again."},{"title":"Page 8","content":"Complexity:\n\nEach vertex appears in $O(\\log n)$ centroid levels.\n\nFor each bit, the total size of all processed centroid lists is $O(n \\log n)$.\n\nThere are $30$ bits.\n\nSo the total complexity is:\n\n$O(30 \\cdot n \\log n)$\n\nMemory usage is:\n\n$O(n \\log n)$"}],"hasLearnContent":true,"likeCount":3,"neutralCount":1,"dislikeCount":3,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"6910e97ff1adda1971305d31","name":"Hamed Ghaffari"}],"statementOverrides":"$undefined","createdAt":"2026-05-23T23:20:43.398Z","updatedAt":"2026-08-20T14:44:46.629Z"}],"contestId":"6a079673e722ebe7820751cb","contestUrlId":"9","isAdmin":false,"isTester":false,"isStarted":true,"isRegistered":false,"canRegister":false,"problemStatusMap":{},"isPremiumBlocked":false,"sponsorshipSnapshot":"$18:props:children:1:props:children:0:props:sponsorshipSnapshot","recentRoundParticipantCounts":[70,96,113],"participationMode":null,"virtualStartTime":null,"contestDurationMs":9000000}]]}]

AMax Mod	500	117/120
BMeximus Minimus	1000	91/95
CWeird Swaps	1500	48/55
DFlip 1...0	2000	8/9
EMeximus Decimus	3000	3/6
FExpected Beauty	3250	4/4
GPath XOR Rank	3500	4/6