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:T47f,## Adjacent Pairs A block of two adjacent positions is easy to handle. For positions $i$ and $i+1$, put $p_i = i+1$ and $p_{i+1} = i$. Both positions move by exactly $1$, and $1$ is a power of two. Therefore, every even number of positions can be completely covered by such adjacent pairs. ## The Odd Case If $n$ is odd, pairing all positions would leave one position unused. Instead, we first handle the first three positions together. Set $p_1 = 2$, $p_2 = 3$, and $p_3 = 1$. The differences are $1$, $1$, and $2$, so all of them are powers of two. After these three positions are handled, the number of remaining positions is even. We can cover all remaining positions using adjacent pairs. ## Construction If $n$ is even, swap every pair $(1,2), (3,4), \ldots$. If $n$ is odd, first use $(2,3,1)$ for positions $1,2,3$, then swap every pair $(4,5), (6,7), \ldots$. The construction assigns every number from $1$ to $n$ exactly once, so the result is a permutation. Each position moves by either $1$ or $2$, both of which are powers of two. ## Complexity Each test case is constructed in $O(n)$ time. The memory complexity is $O(n)$.38:T935,#include #include "testlib.h" using namespace std; static bool existsAnswer(int n, const vector& a) { vector> seen(n, {-1, -1}); int d = (int)a.size(); for (int i = 0; i < d; i++) { for (int j = i + 1; j < d; j++) { int s = (a[i] + a[j]) % n; if (seen[s].first != -1) { return true; } seen[s] = {a[i], a[j]}; } } return false; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; tc++) { int n = inf.readInt(); int d = inf.readInt(); vector a(d); vector isPoint(n, 0); for (int i = 0; i < d; i++) { a[i] = inf.readInt(); if (a[i] < 0 || a[i] >= n) { quitf(_fail, "case %d: point %d is out of range in input", tc, i + 1); } isPoint[a[i]] = 1; } bool hasAnswer = existsAnswer(n, a); string first = ouf.readToken(); if (first == "-1") { if (hasAnswer) { quitf(_wa, "case %d: participant printed -1, but an answer exists", tc); } continue; } int x1, y1, x2, y2; try { x1 = stoi(first); } catch (...) { quitf(_wa, "case %d: first output token is neither -1 nor an integer", tc); } y1 = ouf.readInt(); x2 = ouf.readInt(); y2 = ouf.readInt(); vector p = {x1, y1, x2, y2}; for (int x : p) { if (x < 0 || x >= n) { quitf(_wa, "case %d: point %d is out of range", tc, x); } if (!isPoint[x]) { quitf(_wa, "case %d: point %d is not among the given points", tc, x); } } sort(p.begin(), p.end()); for (int i = 1; i < 4; i++) { if (p[i] == p[i - 1]) { quitf(_wa, "case %d: the four endpoints are not distinct", tc); } } if ((x1 + y1) % n != (x2 + y2) % n) { quitf(_wa, "case %d: the two segments are not parallel", tc); } } if (!ouf.seekEof()) { quitf(_pe, "extra output found"); } quitf(_ok, "all answers are valid"); }39:T451,An array is called edible if all of the following conditions hold: - its length is at least $n$; - every element is one of $0$, $1$, and $2$; - its first and last elements are nonzero. The tastiness of an edible array is the number of maximal contiguous blocks consisting only of zeros. Hamid chooses an edible array of length exactly $n$ uniformly at random among all possible edible arrays of length $n$. Then he changes the array $k$ times. Assume the current edible array is $a$ and its length is $L$. To construct the next array, first add one $0$ to the beginning of $a$ and one $0$ to the end of $a$. More formally, define $x_0 = 0$, $x_{L+1} = 0$, and $x_i = a_i$ for $1 \le i \le L$. The new array $b$ has length $L+1$, and for each $1 \le i \le L+1$: $$ b_i = (x_{i-1} + x_i)^2 \bmod 3. $$ The new array is also edible. Find the expected value of the sum of tastiness values of all $k+1$ edible arrays Hamid sees, including the initial array. Output the answer modulo $998244353$. More precisely, if the expected value is equal to $\frac{P}{Q}$, output $P \cdot Q^{-1} \bmod 998244353$.3a:Tc25,#include #include "testlib.h" using namespace std; const int MAXC = 1000000; struct Domino { int t, x, y; bool operator<(const Domino& other) const { if (t != other.t) return t < other.t; if (x != other.x) return x < other.x; return y < other.y; } }; vector> cells(const Domino& d) { if (d.t == 1) { return {{d.x, d.y}, {d.x + 1, d.y}}; } return {{d.x, d.y}, {d.x, d.y + 1}}; } bool validAnchor(const Domino& d) { return 0 <= d.x && d.x <= MAXC && 0 <= d.y && d.y <= MAXC; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int q = inf.readInt(); map color; map, Domino> owner; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; for (int i = 1; i <= q; i++) { string op = inf.readToken(); int t = inf.readInt(); int x = inf.readInt(); int y = inf.readInt(); if (op != "+" && op != "-") { quitf(_fail, "unknown operation in the input at operation %d", i); } if (t != 1 && t != 2) { quitf(_fail, "invalid domino type in the input at operation %d", i); } Domino d{t, x, y}; if (!validAnchor(d)) { quitf(_fail, "invalid anchor in the input at operation %d", i); } vector> c = cells(d); if (op == "+") { if (color.count(d)) { quitf(_fail, "the input adds an already active domino at operation %d", i); } if (owner.count(c[0]) || owner.count(c[1])) { quitf(_fail, "the input places a domino on a non-empty cell at operation %d", i); } int newColor = ouf.readInt(1, 4, "color"); for (auto cell : c) { for (int dir = 0; dir < 4; dir++) { pair nearCell = {cell.first + dx[dir], cell.second + dy[dir]}; auto it = owner.find(nearCell); if (it == owner.end()) { continue; } const Domino& other = it->second; auto jt = color.find(other); if (jt == color.end()) { quitf(_fail, "internal checker error at operation %d", i); } if (jt->second == newColor) { quitf(_wa, "operation %d gives color %d, equal to an adjacent active domino", i, newColor); } } } color[d] = newColor; owner[c[0]] = d; owner[c[1]] = d; } else { if (!color.count(d)) { quitf(_fail, "the input removes a non-active domino at operation %d", i); } color.erase(d); owner.erase(c[0]); owner.erase(c[1]); } } if (!ouf.seekEof()) { quitf(_pe, "extra output found"); } quitf(_ok, "all added dominoes were colored correctly"); }1b:["$","div",null,{"children":[["$","$L35",null,{"contestId":"6a2ebe62fd08f5a5e3eef89d","contestNumber":13,"contestUrlId":"13","initialIsRegistered":false}],["$","$L36",null,{"contest":{"contestNumber":13,"title":"Repovive Premier Round 5","startDate":"2026-06-21T14:35:00.000Z","endDate":"2026-06-21T17: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":"6a37f4100ccb617c645a43ed","contestId":"6a2ebe62fd08f5a5e3eef89d","slug":"power-permutation","title":"Power Permutation","description":"You are given an integer $n$.\n\nYour task is to construct a permutation $p_1, p_2, \\ldots, p_n$ of the numbers $1, 2, \\ldots, n$ such that for every $i$ with $1 \\le i \\le n$, the value $|i - p_i|$ is a power of two.\n\nThe number $0$ is not considered a power of two.\n\nIt is guaranteed that for every test case satisfying the constraints, at least one valid permutation exists.","constraints":"- $1 \\le t \\le 10^5$\n- $2 \\le n \\le 2 \\times 10^5$\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":"4\n2\n3\n4\n5\n","expectedOutput":"2 1\n2 3 1\n2 1 4 3\n2 3 1 5 4\n","isSample":true,"hidden":false,"explanation":"For $i = 1$, $|1 - 2| = 1$.\nFor $i = 2$, $|2 - 1| = 1$.\nAll obtained values are powers of two.\n`\nFor $i = 1$, $|1 - 2| = 1$.\nFor $i = 2$, $|2 - 3| = 1$.\nFor $i = 3$, $|3 - 1| = 2$.\nAll obtained values are powers of two.\n`\nFor $i = 1$, $|1 - 2| = 1$.\nFor $i = 2$, $|2 - 1| = 1$.\nFor $i = 3$, $|3 - 4| = 1$.\nFor $i = 4$, $|4 - 3| = 1$.\nAll obtained values are powers of two.\n`\nFor $i = 1$, $|1 - 2| = 1$.\nFor $i = 2$, $|2 - 3| = 1$.\nFor $i = 3$, $|3 - 1| = 2$.\nFor $i = 4$, $|4 - 5| = 1$.\nFor $i = 5$, $|5 - 4| = 1$.\nAll obtained values are powers of two.","displayInput":"4\n`\n2\n`\n3\n`\n4\n`\n5","displayOutput":"2 1\n`\n2 3 1\n`\n2 1 4 3\n`\n2 3 1 5 4"}],"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}\np_1 \\quad p_2 \\quad \\cdots \\quad p_n\n\\end{array}\n\\right\\} \\times t\n$$\n\nFor each test case, the printed sequence must be a valid permutation of the numbers $1, 2, \\ldots, n$.\n\nIf there are multiple valid answers, you may print any of them.","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"#include \"testlib.h\"\nusing namespace std;\n\nbool isPowerOfTwo(int x) {\n return x > 0 && (x & (x - 1)) == 0;\n}\n\nint main(int argc, char* argv[]) {\n registerTestlibCmd(argc, argv);\n\n int t = inf.readInt();\n\n for (int tc = 1; tc <= t; tc++) {\n int n = inf.readInt();\n vector used(n + 1, 0);\n\n for (int i = 1; i <= n; i++) {\n int x = ouf.readInt(1, n, (\"p_\" + to_string(i)).c_str());\n\n if (used[x]) {\n quitf(_wa, \"test case %d: value %d appears more than once\", tc, x);\n }\n\n used[x] = 1;\n\n int diff = abs(i - x);\n if (!isPowerOfTwo(diff)) {\n quitf(_wa, \"test case %d: for i = %d, |i - p_i| = %d is not a power of two\", tc, i, diff);\n }\n }\n }\n\n if (!ouf.seekEof()) {\n quitf(_pe, \"extra output found\");\n }\n\n quitf(_ok, \"valid permutation\");\n}\n"},"solvedCount":83,"attemptedCount":84,"tags":["constructive","implementation"],"learnPages":[{"title":"solution","content":"$37"}],"hasLearnContent":true,"likeCount":54,"neutralCount":0,"dislikeCount":13,"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-06-21T14:24:16.578Z","updatedAt":"2026-08-20T14:43:33.165Z"},{"_id":"6a37114d548c52d3aa5c4bfb","contestId":"6a2ebe62fd08f5a5e3eef89d","slug":"crossfire-friends","title":"Crossfire Friends","description":"There are $2n$ musketeers standing on a coordinate grid.\n\nFor each $i$ with $1 \\le i \\le n$, one musketeer stands at $(0, i)$ and shoots a bullet parallel to the positive direction of the $x$-axis.\n\nFor each $i$ with $1 \\le i \\le n$, one musketeer stands at $(i, 0)$ and shoots a bullet parallel to the positive direction of the $y$-axis.\n\nAll bullets are shot at the same time. The speed of the bullet shot from $(0, i)$ is $h_i$ units per second, and the speed of the bullet shot from $(i, 0)$ is $v_i$ units per second.\n\nBullets pass through each other and continue moving. If at some real time $t$ with $0 \\le t \\le n$ two bullets are at the same point, the two musketeers who shot them become friends.\n\nFor each test case, find the number of pairs of musketeers that become friends.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le h_i, v_i \\le 10^9$\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\n1\n1\n1\n2\n1 1\n1 1\n3\n3 1 2\n1 3 2\n4\n4 2 4 1\n4 1 6 1\n5\n5 3 2 10 1\n1 3 2 10 5\n","expectedOutput":"1\n2\n2\n6\n5\n","isSample":true,"hidden":false,"explanation":"The only two bullets meet at point (1, 1) after 1 second.\n`\nThere are two friendly pairs. The bullets from (0, 1) and (1, 0) meet at (1, 1), and the bullets from (0, 2) and (2, 0) meet at (2, 2).\n`\nThe bullet from (0, 3) meets the bullets from (2, 0) and (3, 0). No other pair meets during the first 3 seconds.\n`\nSix pairs meet. The bullets from (0, 1), (0, 2), and (0, 4) each meet the bullets from (1, 0) and (4, 0).\n`\nFive pairs meet. Four of them come from the two bullets starting at (0, 2) and (0, 3) meeting the two bullets starting at (2, 0) and (3, 0). The bullet from (0, 4) also meets the bullet from (4, 0).\n","displayInput":"5\n`\n1\n1\n1\n`\n2\n1 1\n1 1\n`\n3\n3 1 2\n1 3 2\n`\n4\n4 2 4 1\n4 1 6 1\n`\n5\n5 3 2 10 1\n1 3 2 10 5","displayOutput":"1\n`\n2\n`\n2\n`\n6\n`\n5"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\nh_1 \\quad h_2 \\quad \\cdots \\quad h_n \\\\\nv_1 \\quad v_2 \\quad \\cdots \\quad v_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\operatorname{ans}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":62,"attemptedCount":64,"tags":["math","sortings","two pointers"],"learnPages":[{"title":"Where can two bullets meet?","content":"Two bullets shot from the same axis move on parallel lines, so they can never be at the same point.\n\nSo we only need to consider one bullet from $(0, i)$ and one bullet from $(j, 0)$.\n\nThe first bullet always has $y$-coordinate $i$, and the second bullet always has $x$-coordinate $j$. Therefore, if they ever meet, the meeting point must be exactly $(j, i)$."},{"title":"Removing time","content":"Let the speed of the bullet from $(0, i)$ be $h_i$, and the speed of the bullet from $(j, 0)$ be $v_j$.\n\nTo reach $(j, i)$, the first bullet needs time $j / h_i$, and the second bullet needs time $i / v_j$.\n\nThey meet if these two times are equal. Instead of comparing fractions, multiply both sides by $h_i v_j$ and get $i h_i = j v_j$.\n\nAlso, because all speeds are at least $1$ and all coordinates are at most $n$, every such meeting happens no later than time $n$."},{"title":"Counting equal values","content":"For every horizontal bullet from $(0, i)$, compute the value $i h_i$.\n\nFor every vertical bullet from $(j, 0)$, compute the value $j v_j$.\n\nA pair becomes friends exactly when these two values are equal. Therefore, for each value $x$, if it appears $a_x$ times among horizontal bullets and $b_x$ times among vertical bullets, it contributes $a_x b_x$ pairs.\n\nWe can sort both lists and count equal blocks, or use a map. Sorting is simple and deterministic."},{"title":"Algorithm","content":"Build two arrays:\n\n- $A_i = i h_i$ for $1 \\le i \\le n$.\n- $B_i = i v_i$ for $1 \\le i \\le n$.\n\nSort both arrays. Then use two pointers to process equal values. If the current value appears $c_1$ times in $A$ and $c_2$ times in $B$, add $c_1 c_2$ to the answer.\n\nThe values can be as large as $2 \\times 10^{14}$, so they should be stored in 64-bit integers.\n\nThe time complexity is $O(n \\log n)$ per test case, and the memory complexity is $O(n)$."}],"hasLearnContent":true,"likeCount":37,"neutralCount":0,"dislikeCount":8,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"6910edb50cda69581e13124c","name":"Hamid Shafi"}],"statementOverrides":"$undefined","createdAt":"2026-06-20T22:16:45.586Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"6a371438548c52d3aa5c4bfd","contestId":"6a2ebe62fd08f5a5e3eef89d","slug":"parallel-chords","title":"Parallel Chords","description":"There are $n$ positions on a circle, numbered from $0$ to $n-1$ in clockwise order. The positions are equally spaced.\n\nExactly $d$ of these positions contain a point. You are given the sorted array $a_1, a_2, \\ldots, a_d$ of these positions.\n\nFind two line segments such that:\n\n- each endpoint of each segment is one of the given points;\n- the four endpoints are all distinct;\n- the two segments are parallel.\n\nIf there is no such pair of segments, report that it is impossible.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le d \\le n$\n- $1 \\le n \\le 5 \\times 10^5$\n- The sum of $n$ over all test cases is at most $5 \\times 10^5$\n- $0 \\le a_1 < a_2 < \\cdots < a_d < 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":"5\n4 4\n0 1 2 3\n5 3\n0 1 3\n6 4\n0 1 3 4\n8 5\n0 1 2 4 6\n7 4\n0 1 2 4\n","expectedOutput":"0 1 2 3\n-1\n0 1 3 4\n0 6 2 4\n-1\n","isSample":true,"hidden":false,"explanation":"All four points are available. Pair $(0,1)$ gives sum $1$, and $(2,3)$ also gives sum $1$ — the chords $(0,1)$ and $(2,3)$ are parallel.`Only three points are available. The three pairwise sums are $1$, $3$, and $4$ — all distinct, so no two chords can be parallel.`Points $\\{0,1,3,4\\}$. Pair $(0,1)$ and $(3,4)$ both have sum $1$ — the chords $(0,1)$ and $(3,4)$ are parallel.`Points $\\{0,1,2,4,6\\}$. Pair $(0,6)$ has sum $6$, and $(2,4)$ also has sum $6$ — those two chords are parallel.`Points $\\{0,1,2,4\\}$. The six pairwise sums are $1,2,4,3,5,6$ — all distinct modulo $7$, so no parallel chords exist.","displayInput":"`\n5\n`\n4 4\n0 1 2 3\n`\n5 3\n0 1 3\n`\n6 4\n0 1 3 4\n`\n8 5\n0 1 2 4 6\n`\n7 4\n0 1 2 4\n","displayOutput":"0 1 2 3\n`\n-1\n`\n0 1 3 4\n`\n0 6 2 4\n`\n-1\n"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n\n$$\n\\left.\n\\begin{array}{l}\nn \\quad d \\\\\na_1 \\quad a_2 \\quad \\cdots \\quad a_d\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"For each test case, output the answer in one line.\n\nIf there is no valid pair of segments, output $-1$.\n\nOtherwise, output four distinct integers $x_1, y_1, x_2, y_2$, meaning that the segment with endpoints $x_1$ and $y_1$ is parallel to the segment with endpoints $x_2$ and $y_2$.\n\nEach of these four positions must be one of the given points.\n\nIf there are multiple valid answers, you may output any of them.\n\n$$\n\\left.\n\\begin{array}{l}\n-1 \\quad \\text{or} \\quad x_1 \\quad y_1 \\quad x_2 \\quad y_2\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$38"},"solvedCount":36,"attemptedCount":43,"tags":["geometry","brute force","math"],"learnPages":[{"title":"parallel segments and equal chords","content":"Assume two segments $ab$ and $cd$ are parallel, and their endpoints appear in clockwise order as $a,b,c,d$.\n\nUsing the theorem about angles formed by parallel lines with a transversal, together with the fact that inscribed angles standing on the same arc are equal, we get that the chords $bc$ and $ad$ are equal.\n\nSo every valid answer forces the existence of two equal chords whose endpoints are among the given points."},{"title":"equal chords are enough","content":"Now suppose two chords $wx$ and $yz$ are equal and their endpoints appear in clockwise order as $w,x,y,z$.\n\nEqual chords in the same circle subtend equal arcs. By comparing the triangles formed by these arcs and using equal inscribed angles, the two remaining segments $xy$ and $wz$ are parallel.\n\nIf the two equal chords intersect, we can replace them by the two chords obtained from the corresponding symmetric arc differences. These new chords are still equal and have four distinct endpoints without crossing. Therefore, finding two disjoint pairs of points with the same chord length is enough to construct an answer."},{"title":"grouping by distance","content":"The points lie on $n$ equally spaced positions. For two positions $a$ and $b$, the chord length is determined only by the shorter circular distance between them:\n\n`dist(a, b) = min(abs(a - b), n - abs(a - b))`.\n\nTherefore, two pairs of points define equal chords if and only if their `dist` values are equal.\n\nWe group all pairs of given points by this value. Whenever we find two pairs in the same group with four distinct endpoints, we can construct two parallel segments from them and output the answer."},{"title":"why the bruteforce stops quickly","content":"There are only $\frac{n}{2}+1$ possible distance values.\n\nFor a fixed distance, before an answer is found, every two stored pairs with that distance must share an endpoint. On a regular cycle, each point has at most two points at any fixed distance. Hence such a family can contain at most three pairs; the extremal case is an equilateral triangle on the circle.\n\nSo, while processing all pairs, each distance group is checked only a constant number of times before either an answer is found or the group remains small. This gives total time $O(n+d)$ over one test case, and $O(\text{sum } n + \text{sum } d)$ over all test cases.\n\nThe memory usage is $O(n)$."}],"hasLearnContent":true,"likeCount":21,"neutralCount":0,"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":"6910edb50cda69581e13124c","name":"Hamid Shafi"}],"statementOverrides":"$undefined","createdAt":"2026-06-20T22:29:12.529Z","updatedAt":"2026-08-20T14:43:22.660Z"},{"_id":"6a3715b1548c52d3aa5c4c00","contestId":"6a2ebe62fd08f5a5e3eef89d","slug":"tasty-arrays","title":"Tasty Arrays","description":"$39","constraints":"- $1 \\le t \\le 10^5$\n- $2 \\le n \\le 10^9$\n- $1 \\le k \\le 10^9$","difficulty":"medium","order":4,"label":"$undefined","releaseDay":"$undefined","points":2000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"5\n2 1\n3 1\n4 2\n5 3\n6 100\n","expectedOutput":"499122177\n831870295\n499122178\n203346074\n665496238\n","isSample":true,"hidden":false,"explanation":"There are four possible initial arrays. The initial tastiness is always $0$. After one change, exactly two of them have one zero block, so the expected sum is $\\frac{1}{2}$.\n`\nThe expected tastiness of the initial array is $\\frac{1}{3}$, and the expected tastiness after the change is $\\frac{1}{2}$. Their sum is $\\frac{5}{6}$.\n`\nFor the three arrays Hamid sees, the expected tastiness values are $\\frac{5}{9}$, $\\frac{7}{9}$, and $\\frac{1}{6}$. The total is $\\frac{3}{2}$.\n`\nThe expected total tastiness of the four arrays is $\\frac{113}{54}$.\n`\nAfter enough changes, all later arrays have tastiness $0$. For this case, the expected total tastiness is $\\frac{8}{3}$.\n","displayInput":"5\n`\n2 1\n`\n3 1\n`\n4 2\n`\n5 3\n`\n6 100","displayOutput":"499122177\n`\n831870295\n`\n499122178\n`\n203346074\n`\n665496238"},{"input":"5\n2 1\n3 1\n4 2\n5 3\n6 100\n","expectedOutput":"499122177\n831870295\n499122178\n203346074\n665496238\n","isSample":true,"hidden":false,"explanation":"There are four possible initial arrays. The initial tastiness is always $0$. After one change, exactly two of them have one zero block, so the expected sum is $\\frac{1}{2}$.\n`\nThe expected tastiness of the initial array is $\\frac{1}{3}$, and the expected tastiness after the change is $\\frac{1}{2}$. Their sum is $\\frac{5}{6}$.\n`\nFor the three arrays Hamid sees, the expected tastiness values are $\\frac{5}{9}$, $\\frac{7}{9}$, and $\\frac{1}{6}$. The total is $\\frac{3}{2}$.\n`\nThe expected total tastiness of the four arrays is $\\frac{113}{54}$.\n`\nAfter enough changes, all later arrays have tastiness $0$. For this case, the expected total tastiness is $\\frac{8}{3}$.\n"},{"input":"5\n2 1\n3 1\n4 2\n5 3\n6 100\n","expectedOutput":"499122177\n831870295\n499122178\n203346074\n665496238\n","isSample":true,"hidden":false,"explanation":"There are four possible initial arrays. The initial tastiness is always $0$. After one change, exactly two of them have one zero block, so the expected sum is $\\frac{1}{2}$.\n`\nThe expected tastiness of the initial array is $\\frac{1}{3}$, and the expected tastiness after the change is $\\frac{1}{2}$. Their sum is $\\frac{5}{6}$.\n`\nFor the three arrays Hamid sees, the expected tastiness values are $\\frac{5}{9}$, $\\frac{7}{9}$, and $\\frac{1}{6}$. The total is $\\frac{3}{2}$.\n`\nThe expected total tastiness of the four arrays is $\\frac{113}{54}$.\n`\nAfter enough changes, all later arrays have tastiness $0$. For this case, the expected total tastiness is $\\frac{8}{3}$.\n"}],"sampleCount":3,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad k\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\mathrm{ans}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":1,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":7,"attemptedCount":9,"tags":["probabilities","combinatorics","math"],"learnPages":[{"title":"solving the unlimited case","content":"First solve the version where $k=infty$, meaning that we keep applying operations until every zero block has completely disappeared.\n\nThis version is easier because after a zero block appears, we do not need to know the exact time when it disappears. We can count its whole future contribution at once.\n\nAfter computing this unlimited answer, we will subtract the part that was counted too many times because the real number of operations is only $k$."},{"title":"after the first operation","content":"Let the initial array be $x_1,x_2,\\ldots,x_n$, and define $x_0=x_{n+1}=0$.\n\nAfter the first operation, the new array $c$ is defined by $c_i=(x_{i-1}+x_i)^2 \\bmod 3$.\n\nA square modulo $3$ is always either $0$ or $1$, so from this point on the array is binary.\n\nFor binary values $u$ and $v$, the value $(u+v)^2 \\bmod 3$ is $0$ only when $u=v=0$. In all other cases it is $1$.\n\nSo every later operation acts exactly like OR on adjacent positions. From now on, the only thing that matters is how zero blocks shrink."},{"title":"how zero blocks shrink","content":"Consider a maximal zero block of length $L$ in a binary array.\n\nBecause later operations are adjacent OR, the two ends of this block are eaten by the neighboring ones, and the block becomes shorter by one after each operation.\n\nSo a block of length $L$ contributes one zero block now, then one again after the next operation, and so on, for exactly $L$ arrays in total.\n\nTherefore, in the unlimited version, this block contributes $L$ to the total tastiness.\n\nIf only $k$ operations are available after the initial array, the same block can be seen only $\\min(L,k)$ times among the arrays after the first operation."},{"title":"the overcount","content":"The unlimited version counts a zero block of length $L$ exactly $L$ times, while the real process counts it $\\min(L,k)$ times.\n\nSo the overcount of this block is $L-\\min(L,k)=\\max(0,L-k)$.\n\nThis number has a useful interpretation. If $L>k$, then a string of length $L$ contains exactly $L-k$ windows of length $k+1$.\n\nThus $\\max(0,L-k)$ is exactly the number of all-zero windows of length $k+1$ inside this zero block.\n\nSo instead of summing over all long block lengths separately, we only need to subtract the expected number of all-zero windows of length $k+1$ in the array after the first operation."},{"title":"where the windows come from","content":"Now translate an all-zero window of length $k+1$ in $c$ back to the initial array.\n\nThe condition $c_i=c_{i+1}=\\cdots=c_{i+k}=0$ means that every adjacent pair in the segment $x_{i-1},x_i,\\ldots,x_{i+k}$ has sum $0$ modulo $3$.\n\nThis segment has length $k+2$.\n\nA sequence with every adjacent pair summing to $0$ modulo $3$ must be one of these three types:\n\n- all zeros;\n- alternating $1,2,1,2,\\ldots$;\n- alternating $2,1,2,1,\\ldots$.\n\nSo the finite-$k$ correction is just the expected number of length $k+2$ segments of these three forms in the initial array."},{"title":"the unlimited answer","content":"First count the initial array itself.\n\nFor $n=2$, the initial array has no zero position, so its expected tastiness is $0$.\n\nFor $n\\ge 3$, position $2$ starts a zero block with probability $1/3$. Each position $3,4,\\ldots,n-1$ starts a zero block when the current value is $0$ and the previous value is nonzero, which has probability $2/9$.\n\nSo the expected tastiness of the initial array is $(2n-3)/9$.\n\nNow count the unlimited future after the first operation. Every zero in $c$ contributes exactly once to the total future contribution, because a zero block of length $L$ contributes $L$.\n\nFor $n=2$, the only middle value of $c$ is zero with probability $1/2$.\n\nFor $n\\ge 3$, each of the $n-1$ relevant adjacent pairs of the initial array has sum $0$ modulo $3$ with probability $1/3$.\n\nTherefore, the unlimited answer is $1/2$ for $n=2$, and $(2n-3)/9+(n-1)/3$ for $n\\ge 3$."},{"title":"subtracting the finite part","content":"If $k\\ge n-1$, no zero block after the first operation can survive for more than $k$ operations, so there is nothing to subtract.\n\nOtherwise, set $m=k+2$. We need to count length $m$ segments of the initial array that are all zeros or alternating between $1$ and $2$.\n\nIf $m 0$ for $1 \\le i < n$."},{"title":"The sequence we count","content":"The problem is now equivalent to counting sequences $d_1, d_2, \\ldots, d_n$ with the following properties:\n\n- each $d_i$ is one of $-2, -1, 0, 1, 2$,\n- exactly two values are odd,\n- every proper prefix sum is positive,\n- the total sum is $0$.\n\nThe reverse direction is also possible. If such a sequence is given, we know for every vertex how many edges must go to smaller labels and how many must go to greater labels. Sweeping from left to right, we can match open edge ends greedily. The positivity of prefix sums guarantees that we never run out of open ends before the last position, and the total sum $0$ guarantees that all ends are closed at the end.\n\nSo from now on, we only count these valid difference sequences."},{"title":"Removing zero steps","content":"First ignore all zero values of the sequence. The remaining sequence is called its skeleton.\n\nA skeleton contains only values from $\\{-2, -1, 1, 2\\}$, has exactly two odd steps, stays positive before the end, and has total sum $0$.\n\nAfter we count skeletons, we can insert zero steps back.\n\nSuppose a skeleton has length $k$. In the original sequence of length $n$, the first and last positions cannot be zero: the first step must leave height $0$, and the last step must return to height $0$.\n\nSo among the $n-2$ middle positions, we choose which $k-2$ positions contain the remaining non-zero steps.\n\nTherefore a skeleton of length $k$ contributes $\\binom{n-2}{k-2}$ full sequences.\n\nIf $num_k$ is the number of valid skeletons of length $k$, then the final answer is $\\sum_{k=2}^{n} \\binom{n-2}{k-2} num_k$."},{"title":"Dividing even steps","content":"Inside a skeleton, exactly two steps are odd. These two steps are either $1$ or $-1$.\n\nAll other steps are $2$ or $-2$. Divide those even steps by $2$, so they become ordinary steps $1$ and $-1$.\n\nNow the two odd steps are special, and everything else is an ordinary up/down path.\n\nThere are four possible sign patterns for the two special steps:\n\n- $1, 1$,\n- $1, -1$,\n- $-1, 1$,\n- $-1, -1$.\n\nWe count these cases using Catalan numbers.\n\nLet $C_k$ be the $k$-th Catalan number, so $C_k = \\frac{1}{k+1}\\binom{2k}{k}$.\n\nA positive block of length $2k$ has $C_{k-1}$ possibilities for $k \\ge 1$. A non-negative block of length $2k$ has $C_k$ possibilities."},{"title":"Useful block arrays","content":"We use a few arrays to write the formulas compactly.\n\nLet $P_k = 2k C_{k-1}$ for $k \\ge 1$, and $P_0 = 0$.\n\nThis counts a positive Catalan block of length $2k$ with one chosen position.\n\nLet $Q_k = C_k$.\n\nThis counts a non-negative Catalan block of length $2k$.\n\nLet $R_k = (2k+1)C_k$.\n\nThis counts a non-negative block with one chosen gap or boundary position.\n\nLet $S_k = \\frac{(2k)(2k+1)}{2} C_{k-1}$ for $k \\ge 1$, and $S_0 = 0$.\n\nThis counts a positive block with two ordered chosen positions of the type needed in the equal-sign cases.\n\nAll these values are computed modulo $998244353$."},{"title":"Opposite signs","content":"First consider the cases where the two special steps have opposite signs.\n\nFor the pattern $1, -1$, the skeleton has the form $a, 1, b, -1, c$.\n\nHere $a$ must stay positive, $b$ may touch zero, and $c$ must stay positive. We fix the first and last internal touches of zero. This decomposes the path into two marked positive blocks and one non-negative block, which gives the convolution $P * P * Q$.\n\nFor the pattern $-1, 1$, the skeleton has the form $a, -1, b, 1, c$.\n\nHere all three parts must stay positive after the natural height shift. This gives the direct term $C_{k-1}((2k)^2 + (2k-1))$.\n\nLet $X_k$ be the number of opposite-sign skeletons of length $2k+2$. Then $X_0 = 1$, and for $k \\ge 1$ we have $X_k = (P * P * Q)_k + C_{k-1}((2k)^2 + (2k-1))$."},{"title":"Equal signs","content":"Now consider the cases where the two special steps have the same sign.\n\nFor the pattern $1, 1$, the skeleton has the form $a, 1, b, 1, c$.\n\nHere $a$ must stay positive, while $b$ and $c$ may touch zero. We fix the first internal touch of zero, and the path splits into Catalan blocks.\n\nFor the pattern $-1, -1$, the skeleton has the form $a, -1, b, -1, c$.\n\nHere $a$ and $b$ must stay positive, and $c$ must stay above height $1$ after shifting. This is symmetric to the previous case, so the total is multiplied by $2$.\n\nLet $Y_k$ be the number of equal-sign skeletons of length $2k+3$. Then $Y_k = 2([k=0] + (P * R)_k + (S * Q)_k)$.\n\nSo $num_{2k+3} = Y_k$."},{"title":"Skeleton counts","content":"The skeleton counts are obtained from $X$ and $Y$:\n\nFor even skeleton lengths, $num_{2k+2} = X_k$.\n\nFor odd skeleton lengths, $num_{2k+3} = Y_k$.\n\nThe convolutions $P * P$, $(P * P) * Q$, $P * R$, and $S * Q$ are computed using NTT.\n\nWe only need coefficients up to about $n/2$, because the skeleton length cannot exceed $n$.\n\nAfter computing all $num_k$, we insert zero steps back using the formula from before:\n\n$ans_n = \\sum_{k=2}^{n} \\binom{n-2}{k-2} num_k$.\n\nThe binomial coefficients are computed using factorials and inverse factorials modulo $998244353$."},{"title":"Complexity","content":"The solution has three main parts.\n\nFirst, we precompute factorials, inverse factorials, and Catalan numbers. This takes $O(n)$ time.\n\nSecond, we compute the arrays $X$ and $Y$. They require a constant number of polynomial convolutions, so this takes $O(n \\log n)$ time with NTT.\n\nThird, we compute the final summation $\\sum_{k=2}^{n} \\binom{n-2}{k-2} num_k$, which takes $O(n)$ time for one value of $n$.\n\nFor multiple test cases, we compute everything up to the maximum given $n$ once, and then answer each test case.\n\nThe total time complexity is $O(N \\log N + t)$, where $N$ is the maximum value of $n$ over all test cases.\n\nThe memory complexity is $O(N)$."}],"hasLearnContent":true,"likeCount":5,"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":"695106610a6bf472a03d67bf","name":"Amirali Asgari"}],"statementOverrides":"$undefined","createdAt":"2026-06-20T21:38:31.691Z","updatedAt":"2026-06-30T19:07:21.375Z"}],"contestId":"6a2ebe62fd08f5a5e3eef89d","contestUrlId":"13","isAdmin":false,"isTester":false,"isStarted":true,"isRegistered":false,"canRegister":false,"problemStatusMap":{},"isPremiumBlocked":false,"sponsorshipSnapshot":"$1a:props:children:1:props:children:0:props:sponsorshipSnapshot","recentRoundParticipantCounts":[92,108,96],"participationMode":null,"virtualStartTime":null,"contestDurationMs":9000000}]]}]

APower Permutation	500	83/84
BCrossfire Friends	1000	62/64
CParallel Chords	1500	36/43
DTasty Arrays	2000	7/9
EDomino Painter	2500	14/17
FMonochrome Levels	3000	7/7
GPermutation Cut Profiles	3500	3/4