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:T480,Consider any permutation $p_1, p_2, \dots, p_n$ of the integers $1, 2, \dots, n$. Define $p_0 = n+1$ and $p_{n+1} = n+2$. For each index $i$ ($1 \le i \le n$) we compute a character $c_i$ as follows: - Let $x$ be the index of the **nearest greater element to the left** of $i$: $x = \max\{j \mid 0 \le j < i \text{ and } p_j > p_i\}$. - Let $y$ be the index of the **nearest greater element to the right** of $i$: $y = \min\{j \mid i < j \le n+1 \text{ and } p_j > p_i\}$. - If $p_x < p_y$ then $c_i =$ `L`, otherwise $c_i$ = `R`. In other words, we look at the closest larger element on the left and the closest larger element on the right. The character `L` means the left one is smaller, `R` means the right one is smaller. Now you are given the string $s$. Determine whether there exists a permutation $p$ such that $c_i = s_i$ for every $i = 1 \dots n$. If no such permutation exists, print `No`. If it exists, print `Yes` and on the next line output **any** permutation $p$ that satisfies the condition. ## Constraints - $1 \le t \le 10^4$ - $1 \le n \le 2 \times 10^5$ - The sum of $n$ over all test cases is at most $2 \times 10^5$38:Tbc1,#include "testlib.h" #include #include using namespace std; void check_test(int test_id) { int n = inf.readInt(); string s = inf.readToken(); string j_ans = ans.readToken(); // برطرف کردن باگ: خواندن جایگشت Jury برای همگام ماندن استریم فایل جواب if (j_ans == "Yes") { for (int i = 1; i <= n; i++) { ans.readInt(); } } string p_ans = ouf.readToken(); // بررسی فرمت دقیق کلمه Yes و No if (p_ans != "Yes" && p_ans != "No") { ouf.quitf(_pe, "Testcase %d: Expected 'Yes' or 'No', found '%s'", test_id, p_ans.c_str()); } if (p_ans == "No") { if (j_ans == "Yes") { ouf.quitf(_wa, "Testcase %d: Participant answered 'No', but a valid permutation exists", test_id); } return; // هر دو No هستند، جواب درست است } if (p_ans == "Yes") { vector p(n + 2); p[0] = n + 1; p[n + 1] = n + 2; vector used(n + 1, false); for (int i = 1; i <= n; i++) { p[i] = ouf.readInt(1, n, "p_i"); if (used[p[i]]) { ouf.quitf(_wa, "Testcase %d: Permutation contains duplicate element %d", test_id, p[i]); } used[p[i]] = true; } // استفاده از Monotonic Stack برای پیدا کردن نزدیک‌ترین عنصر بزرگتر در سمت چپ vector x(n + 2), y(n + 2); vector st; st.push_back(0); for (int i = 1; i <= n; i++) { while (!st.empty() && p[st.back()] < p[i]) { st.pop_back(); } x[i] = st.back(); st.push_back(i); } // استفاده از Monotonic Stack برای پیدا کردن نزدیک‌ترین عنصر بزرگتر در سمت راست st.clear(); st.push_back(n + 1); for (int i = n; i >= 1; i--) { while (!st.empty() && p[st.back()] < p[i]) { st.pop_back(); } y[i] = st.back(); st.push_back(i); } // اعتبارسنجی پرمیوتیشن با رشته s for (int i = 1; i <= n; i++) { char expected = (p[x[i]] < p[y[i]]) ? 'L' : 'R'; if (expected != s[i - 1]) { ouf.quitf(_wa, "Testcase %d: Condition failed at index %d. Expected '%c' from rules, but string has '%c'", test_id, i, expected, s[i - 1]); } } if (j_ans == "No") { ouf.quitf(_fail, "Testcase %d: Participant found a valid permutation, but jury says 'No'", test_id); } } } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int i = 1; i <= t; i++) { check_test(i); } quitf(_ok, "Passed all %d test cases", t); return 0; } 39:T4a1,We can make at most $1$ cut. If we don't make any cuts, the sticks are $\{3, 4, 5\}$ and the difference between the longest and shortest piece is $5 - 3 = 2$. Even if we use our $1$ cut (for example, cutting the stick of length $5$ into $2$ and $3$), the new pieces would be $\{2, 3, 3, 4\}$, resulting in a difference of $4 - 2 = 2$. Thus, the minimum possible difference is $2$. ` Since $k=0$, no cuts are allowed. We simply calculate the difference between the longest and shortest initial sticks, which is $10 - 2 = 8$. ` All sticks are already the same length (all are $5$). Without making any cuts, the difference between the longest and shortest piece is $5 - 5 = 0$. ` There is only one stick. We don't even need to use our available cut; since there is only a single piece, both the longest and shortest pieces are the exact same stick, making the difference $9 - 9 = 0$. ` The initial lengths are $\{7, 8, 9\}$, giving an initial difference of $9 - 7 = 2$. Even with $2$ available cuts, there is no way to divide the sticks such that the difference between the maximum and minimum resulting pieces becomes strictly less than $2$. The minimum possible difference remains $2$. 3a:T43d,### Optional Optimization There are many edges with weight $0$ in our graph. If we have $m$ edges and $k$ non-zero edges, we can compute the shortest path in $O(k \log n + m)$. For type 1 and type 3 edges, instead of adding weighted edges between $i$ and segment tree nodes, we introduce two additional nodes $in_i$ and $out_i$, and add the following edges for each $i$: 1. $in_i \to i$ with weight $i$ 2. $i \to out_i$ with weight $i$ Now, if we want to add an edge from $i$ to a segment tree node with weight $i$, we can instead add an edge from $out_i$ to the segment tree node with weight $0$ (or from a segment tree node to $in_i$ for type 3 edges). In this way, the number of non-zero edges becomes $O(n)$. --- ### How to find the shortest path in $O(k \log n + m)$? We use an approach similar to 0-1 BFS. We maintain: - a queue for edges with weight $0$, - a priority queue for edges with non-zero weight. Each time, if the queue is not empty, we take a vertex from the queue; otherwise, we take the vertex with the smallest current distance from the priority queue.1b:["$","div",null,{"children":[["$","$L35",null,{"contestId":"69d2cf890e7e91b076b5260f","contestNumber":5,"contestUrlId":"5","initialIsRegistered":false}],["$","$L36",null,{"contest":{"contestNumber":5,"title":"Repovive Standard Round 2","startDate":"2026-04-19T13:35:00.000Z","endDate":"2026-04-19T15:35:00.000Z","urlSlug":"$undefined","problemDisplay":"letters","requiresPremium":false,"lobbyProblemsCount":6,"isProblemSet":false,"contestType":"cp","adminOnly":false,"isWeeklyChallenge":"$undefined","weekNumber":"$undefined","ratedMaxTier":"$undefined","announcements":[]},"problems":[{"_id":"69d2cf8a0e7e91b076b52610","contestId":"69d2cf890e7e91b076b5260f","slug":"problem-1","title":"TV Volume","description":"Your TV has a volume level between $0$ and $1000$. Currently, the volume is at $A$, and you want to change it to exactly $B$.\n\nThe TV remote has three buttons to control the volume:\n1. `+` button (increases the volume by $1$).\n2. `-` button (decreases the volume by $1$).\n3. `Mute` button (sets the volume instantly to $0$).\n\nWhat is the minimum number of button presses required to change the volume from $A$ to $B$?\n\n## Constraints\n- $1 \\le t \\le 10^4$\n- $0 \\le A, B \\le 1000$","constraints":"$undefined","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\n100 102\n100 5\n0 50\n","expectedOutput":"2\n6\n50\n","hidden":false,"isSample":true,"explanation":"Press the plus button $2$ times.\n`\nPress the Mute button to set the volume to $0$, then press the plus button $5$ times.\n`\nPress the plus button $50$ times.\n","displayInput":"3\n`\n100 102\n`\n100 5\n`\n0 50","displayOutput":"2\n`\n6\n`\n50"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nA \\quad B\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":46,"attemptedCount":46,"tags":["math"],"learnPages":[{"title":"Page 1","content":"In this problem, we are currently at volume $A$ and want to reach volume $B$. We have three buttons: increase by $1$, decrease by $1$, and mute instantly to $0$. To reach our goal, there are two main strategies we need to consider.\n"},{"title":"Page 2","content":"The first strategy is to move directly from $A$ to $B$ without using the Mute button. If $A > B$, we repeatedly press the decrease button, and if $A < B$, we press the increase button. The number of button presses required for this direct approach is exactly the absolute difference between the two numbers, which is $|A - B|$.\n"},{"title":"Page 3","content":"The second strategy is to use the Mute button first. Pressing this button counts as $1$ move and immediately sets the volume to $0$. From $0$, the only way to reach $B$ is to press the increase button exactly $B$ times. Therefore, the total number of moves for this strategy is $1 + B$.\n"},{"title":"Page 4","content":"Since we are looking for the minimum number of moves, we just need to calculate the required moves for both strategies and output the smaller value. The final answer is simply $\\min(|A - B|, 1 + B)$. This approach does not require any loops and solves each test case in $O(1)$ time complexity.\n"}],"hasLearnContent":true,"likeCount":4,"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-04-05T21:09:29.633Z","updatedAt":"2026-06-28T22:22:26.596Z"},{"_id":"69d2cf8a0e7e91b076b52611","contestId":"69d2cf890e7e91b076b5260f","slug":"problem-2","title":"Swap Parities","description":"You are given an array $a$ of $n$ integers. \n\nYou can perform the following operation any number of times (possibly zero):\nChoose two adjacent elements $a_i$ and $a_{i+1}$. If they have different parities (i.e., one is even and the other is odd), you can swap them.\n\nDetermine whether it is possible to sort the array in non-decreasing order using this operation.\n\n## Constraints\n- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le a_i \\le 10^9$\n- The sum of $n$ over all test cases does not exceed $2 \\times 10^5$.","constraints":"$undefined","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":"4\n3\n7 3 4\n3\n3 4 7\n4\n2 4 1 3\n2\n4 2\n","expectedOutput":"No\nYes\nYes\nNo\n","hidden":false,"isSample":true,"explanation":"We can only swap $3$ and $4$ to get $7, 4, 3$, and then swap $7$ and $4$ to get $4, 7, 3$. It is impossible to fully sort this array using the given operations.\n`\nThe array is already sorted in non-decreasing order, so no operations are needed.\n`\nWe can sort the array with the following operations:\n- Swap $4$ and $1$ (since they have different parities): $2, 1, 4, 3$\n- Swap $2$ and $1$: $1, 2, 4, 3$\n- Swap $4$ and $3$: $1, 2, 3, 4$\n\nThe array is now sorted.\n`\nBoth numbers are even, so we cannot swap them. Thus, it is impossible to sort the array.\n","displayInput":"4\n`\n3\n7 3 4\n`\n3\n3 4 7\n`\n4\n2 4 1 3\n`\n2\n4 2","displayOutput":"No\n`\nYes\n`\nYes\n`\nNo"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\na_1 \\quad a_2 \\quad \\cdots \\quad a_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\text{Yes / No}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":42,"attemptedCount":43,"tags":["greedy","sortings"],"learnPages":[{"title":"Page 1","content":"According to the problem's rules, we can only swap two adjacent elements if they have different parities. This means an even number can freely move past any odd number, and an odd number can freely move past any even number.\n"},{"title":"Page 2","content":"However, because we can never swap two numbers with the same parity, an even number can never move past another even number. Similarly, an odd number can never move past another odd number. Therefore, the relative order of all even numbers remains strictly unchanged no matter how many operations we perform, and the same applies to all odd numbers.\n"},{"title":"Page 3","content":"For the entire array to be fully sorted at the end, it is both necessary and sufficient that the sequence of even numbers is already sorted in non-decreasing order from left to right, and the sequence of odd numbers is also sorted in non-decreasing order initially.\n"},{"title":"Page 4","content":"To implement this, we can simply iterate through the given array $A$ and separate the elements into two independent lists: one containing all the even numbers and one containing all the odd numbers. Finally, we check if both lists are independently sorted. If they are, the answer is \"Yes\", otherwise \"No\". This takes $O(N)$ time.\n"}],"hasLearnContent":true,"likeCount":4,"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-04-05T21:09:29.633Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"69de1a05746d4daa1a46b68a","contestId":"69d2cf890e7e91b076b5260f","slug":"permutation-from-direction-string","title":"Permutation from Direction String","description":"$37","constraints":"$undefined","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\n3\nRLL\n3\nLRR\n1\nL\n2\nRL\n4\nRRRL","expectedOutput":"Yes\n2 3 1\nNo\nYes\n1\nYes\n1 2\nYes\n1 2 3 4","hidden":false,"isSample":true,"displayInput":"5\n`\n3\nRLL\n`\n3\nLRR\n`\n1\nL\n`\n2\nRL\n`\n4\nRRRL","displayOutput":"Yes\n2 3 1\n`\nNo\n`\nYes\n1\n`\nYes\n1 2\n`\nYes\n1 2 3 4","explanation":"- $i=1$: left greater $= p_0=4$, right greater $= p_2=3$. Since $4>3$, the direction is 'R'\n- $i=2$: left greater $= p_0=4$, right greater $= p_4=5$. Since $4<5$, the direction is 'L'\n- $i=3$: left greater $= p_2=3$, right greater $= p_4=5$. Since $3<5$, the direction is 'L'\n`\nImpossible\n`\n- $i=1$: left greater $= p_0=2$, right greater $= p_2=3$. Since $2<3$, the direction is 'L'\n`\n- $i=1$: left greater $= p_0=3$, right greater $= p_2=2$. Since $3>2$, the direction is 'R'\n- $i=2$: left greater $= p_0=3$, right greater $= p_3=4$. Since $3<4$, the direction is 'L'\n`\n- $i=1$: left greater $= p_0=5$, right greater $= p_2=2$. Since $5>2$, the direction is 'R'\n- $i=2$: left greater $= p_0=5$, right greater $= p_3=3$. Since $5>3$, the direction is 'R'\n- $i=3$: left greater $= p_0=5$, right greater $= p_4=4$. Since $5>4$, the direction is 'R'\n- $i=4$: left greater $= p_0=5$, right greater $= p_5=6$. Since $5<6$, the direction is 'L'"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\ns\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\text{Yes / No} \\\\\np_1 \\quad p_2 \\quad \\dots \\quad p_n \\quad \\text{(if answer is Yes)}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"$38"},"solvedCount":29,"attemptedCount":33,"tags":["constructive","greedy"],"learnPages":[{"title":"Page 1","content":"First, observe the condition for the last character of the string, $s_n$. For the last element $p_n$, its nearest right greater element will always be at index $n+1$, with the value $p_{n+1} = n+2$. The nearest left greater element will be at some index $x \\ge 0$, and its value will be at most $n+1$ (since $p_0 = n+1$ and the rest are $\\le n$). Since $p_x \\le n+1 < n+2 = p_y$, the condition $p_x < p_y$ is always satisfied. Therefore, $s_n$ must always be 'L'. If the given string ends with 'R', we can immediately output \"No\".\n"},{"title":"Page 2","content":"If the string ends with 'L', a valid permutation always exists. We can partition the string $s$ into contiguous blocks such that each block ends with exactly one 'L' character and contains only 'R' characters before it. For example, if $s = \\text{\"RRLLRL\"}$, the blocks will be $\\text{\"RRL\"}$, $\\text{\"L\"}$, and $\\text{\"RL\"}$.\n"},{"title":"Page 3","content":"We assign values to the permutation block by block from left to right. The first block will receive the largest available values from $\\{1, 2, \\dots, n\\}$, the second block will receive the next largest available values, and so on. Within each block, we assign these values in strictly increasing order.\n"},{"title":"Page 4","content":"Let's verify why this construction works for the 'R' characters. For any 'R' character (which is not the end of its block), the nearest greater element to its right is simply the very next element in the same block, because elements within a block are strictly increasing. The nearest greater element to its left will be the last element of the previous block (or $p_0 = n+1$ if it is in the first block). By our construction, values in previous blocks are strictly larger than values in the current block. Since the left greater element is larger than the right greater element ($p_x > p_y$), the resulting character is 'R', which matches our requirement.\n"},{"title":"Page 5","content":"Finally, let's verify the 'L' characters. An 'L' character is the last element of its block. Since we assign progressively smaller values to subsequent blocks, all elements to the right of this 'L' character are strictly smaller than it. Therefore, the nearest greater element to its right will always be the boundary element $p_{n+1} = n+2$, which is the absolute maximum value. The nearest greater element to its left will be from a previous block or $p_0 = n+1$. Because $p_{n+1} = n+2$ is strictly greater than any possible left greater element, $p_x < p_y$ holds true, correctly yielding the character 'L'.\n"}],"hasLearnContent":true,"likeCount":4,"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-14T10:42:13.974Z","updatedAt":"2026-06-30T21:11:23.536Z"},{"_id":"69d2cf8a0e7e91b076b52613","contestId":"69d2cf890e7e91b076b5260f","slug":"problem-4","title":"Remove Mountain","description":"You are given a permutation $p_1, p_2, \\ldots, p_n$ of integers from $1$ to $n$.\n\nIn one operation, you can choose an index $i$ such that $1 < i < |p|$ (where $|p|$ is the current length of the permutation), $p_i > p_{i-1}$ and $p_i > p_{i+1}$, and remove $p_i$ from the sequence. After removing $p_i$, the remaining elements are concatenated without changing their relative order.\n\nFind the number of different subsets of numbers that can remain after applying this operation any number of times (possibly zero). Since the answer can be very large, print it modulo $998244353$.\n\n## Constraints\n- $1 \\le t \\le 10^4$\n- $2 \\le n \\le 2 \\times 10^5$\n- The sum of $n$ over all test cases does not exceed $2 \\times 10^5$.","constraints":"$undefined","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":"3\n4\n1 3 2 4\n5\n5 3 4 2 1\n5\n1 4 5 2 3\n","expectedOutput":"2\n2\n3\n","hidden":false,"isSample":true,"explanation":"The initial permutation is 1 3 2 4. We can either do no operations and keep 1 3 2 4, or we can choose the element 3 (since 3 > 1 and 3 > 2) and remove it, resulting in 1 2 4. No further operations are possible. So there are 2 valid subsets.\n`\nThe sequence is 5 3 4 2 1. We can remove 4 (since 4 > 3 and 4 > 2), resulting in 5 3 2 1. We cannot remove any other elements. So the valid subsets are 5 3 4 2 1 and 5 3 2 1.\n`\nThe sequence is 1 4 5 2 3. The valid subsets are:\n1) 1 4 5 2 3 (0 operations)\n2) 1 4 2 3 (removing 5)\n3) 1 2 3 (removing 5, then removing 4 from the remaining sequence)\nTotal 3 valid subsets.\n","displayInput":"3\n`\n4\n1 3 2 4\n`\n5\n5 3 4 2 1\n`\n5\n1 4 5 2 3","displayOutput":"2\n`\n2\n`\n3"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\np_1 \\quad p_2 \\quad \\ldots \\quad p_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\text{ans}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":21,"attemptedCount":24,"tags":["dp","data structures"],"learnPages":[{"title":"Page 1","content":"Let's consider any two consecutive elements $p_i$ and $p_j$ ($i < j$) that remain in our final sequence. We need to determine the exact condition under which it is possible to successfully remove all elements strictly between them.\n"},{"title":"Page 2","content":"The condition is that every element between $p_i$ and $p_j$ must be greater than $\\max(p_i, p_j)$ (i.e., greater than both of the two boundaries). Let's prove this by contradiction. Suppose there is an element between them that is smaller than one of $p_i$ and $p_j$. The minimum of such elements will act as a local minimum. Since an element can only be deleted if it is strictly greater than its current left and right neighbors, this local minimum will always be smaller than one of ots adjacent elements (or the boundaries), making it impossible to ever remove.\n"},{"title":"Page 3","content":"Because no element between $p_i$ and $p_j$ can be smaller than one of them, it establishes a direct structural relationship between them. Specifically, for any two valid consecutive remaining elements, either the left element $p_i$ must be the first element to the left of $p_j$ that is smaller than $p_j$, or the right element $p_j$ must be the first element to the right of $p_i$ that is smaller than $p_i$.\n"},{"title":"Page 4","content":"Now that we have established this necessary and sufficient transition condition, we can solve the problem using Dynamic Programming. Let $dp[i]$ be the number of valid remaining subsets where the last unremoved element is exactly $p_i$.\n"},{"title":"Page 5","content":"To calculate $dp[i]$, we can maintain a strictly decreasing monotonic stack of indices. When processing $p_i$, we pop elements from the stack that are smaller than $p_i$. For each popped index $j$, $p_i$ is the first smaller element to its right, making $j \\to i$ a valid transition. After popping, the current top of the stack is the first element to the left that is smaller than $p_i$, making it another valid transition. We simply sum the $dp$ values of these valid states to compute $dp[i]$.\n"}],"hasLearnContent":true,"likeCount":3,"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-05T21:09:29.633Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"69de9fbac8079454c9774f89","contestId":"69d2cf890e7e91b076b5260f","slug":"stick-division","title":"Stick Division","description":"You are given $n$ sticks of integer lengths $a_1, a_2, \\ldots, a_n$.\n\nYou can perform at most $k$ cuts in total. In a single cut, you can choose a stick of integer length $L > 1$ and divide it into two sticks of integer lengths $x$ and $y$ such that $x > 0$, $y > 0$, and $x + y = L$. \n\nAfter performing at most $k$ cuts, your goal is to minimize the difference between the maximum and minimum lengths among all the resulting sticks. \n\nFind the minimum possible difference between the length of the longest stick and the shortest stick.\n\n## Constraints\n- $1 \\le t \\le 100$\n- $1 \\le n \\le 10^5$\n- $1 \\le a_i \\le 10^5$\n- $0 \\le k \\le 10^9$\n- The sum of $n$ over all test cases is at most $10^5$.","constraints":"$undefined","difficulty":"hard","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\n3 1\n3 4 5\n2 0\n10 2\n4 100\n5 5 5 5\n1 1\n9\n3 2\n7 8 9\n","expectedOutput":"2\n8\n0\n0\n2","hidden":false,"isSample":true,"explanation":"$39","displayInput":"5\n`\n3 1\n3 4 5\n`\n2 0\n10 2\n`\n4 100\n5 5 5 5\n`\n1 1\n9\n`\n3 2\n7 8 9","displayOutput":"2\n`\n8\n`\n0\n`\n0\n`\n2"}],"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}\nans\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":3,"memoryLimit":512,"checker":{"type":"wcmp"},"solvedCount":12,"attemptedCount":18,"tags":["binary search","greedy","math","data structures"],"learnPages":[{"title":"Page 1","content":"To split a stick of length $x$ into $t$ pieces, the largest piece will be $\\lceil x/t \\rceil$ and the smallest will be $\\lfloor x/t \\rfloor$.\nThis means we can control both the maximum and minimum sizes by choosing how many pieces to create.\n"},{"title":"Page 2","content":"Fix that the maximum length would be at most $i$. If we want all pieces to have length at most $i$, we need to split each stick so that $\\lceil x/t \\rceil \\le i$.\nThe minimum number of pieces needed is $t = \\lceil x/i \\rceil$, so cuts needed are $\\lceil x/i \\rceil - 1$.\nThe total cuts for target maximum $i$ is defined $f_i = \\sum (\\lceil x/i \\rceil - 1)$.\nThe achievable minimum piece size is defined $g_i = \\min \\lfloor x/t \\rfloor$. \nAnswer is $\\min(i - g_i)$ for all $i$ where $f_i \\le k$.\n"},{"title":"Page 3","content":"As $i$ increases (becomes larger), $\\lceil x/i \\rceil$ decreases and changes only $O(\\sqrt{x})$ times for each stick.\nThis is because $\\lceil x/i \\rceil$ drops by 1 in two patterns: when $i > \\sqrt{x}$ it changes slowly, and when $i \\le \\sqrt{x}$ it changes frequently.\nWe only need to check values of $i$ where $\\lceil x/i \\rceil$ actually changes.\n"},{"title":"Page 4","content":"For each stick $x$, we track when its number of required pieces will decrease.\nCreate $\\text{events}[i]$ = list of sticks whose $\\lceil x/i \\rceil$ value changes when target drops to $i$.\nInitialize stick $x$ at $\\text{events}[x-1]$ because that's the first $i$ where $t = \\lceil x/(x-1) \\rceil = 2$ (needs at least 1 cut).\nIterate $i$ from $\\text{max\\_a} - 1$ down to $1$.\n"},{"title":"Page 5","content":"When we process stick $x$ at event $i$:\n- Old number of pieces when target was $i+1$: $t_{\\text{old}} = \\lceil x/(i+1) \\rceil = (x-1)/(i+1) + 1$\n- New number of pieces when target is $i$: $t_{\\text{new}} = \\lceil x/i \\rceil = (x-1)/i + 1$\n- The difference in cuts is $(t_{\\text{new}} - 1) - (t_{\\text{old}} - 1) = (x-1)/i - (x-1)/(i+1)$\n- Update total cuts $f_i$ and minimum piece size $g_i = \\min(x / t_{\\text{new}})$.\n- Schedule next event when pieces decrease again: $\\text{next\\_i} = \\lceil x/(t_{\\text{new}}-1) \\rceil - 1$.\n"},{"title":"Page 6","content":"If $f_i \\le k$, target $i$ is achievable with at most $k$ cuts.\nThe current difference is $i - g_i$ (largest minus smallest piece).\nSince $i$ decreases as we iterate, $f_i$ only increases, so we can break when $f_i > k$.\n"},{"title":"Page 7","content":"Each stick triggers $O(\\sqrt{x})$ events because $\\lceil x/i \\rceil$ changes $O(\\sqrt{x})$ times.\nTotal time complexity: $O(n \\cdot \\sqrt{A})$ where $A = \\max(a_i)$.\nTotal space complexity: $O(n + A)$.\n"}],"hasLearnContent":true,"likeCount":0,"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-14T20:12:42.936Z","updatedAt":"2026-06-30T19:07:21.375Z"},{"_id":"69d2cf8a0e7e91b076b52615","contestId":"69d2cf890e7e91b076b5260f","slug":"problem-6","title":"Shortest Path on Intervals","description":"You are given $n$ intervals. The $i$-th interval is represented by $[l_i, r_i]$.\n\nWe construct an undirected graph with $n$ vertices, where each vertex represents one of the intervals. There is an edge between vertex $i$ and vertex $j$ ($i \\neq j$) if and only if their corresponding intervals intersect (i.e., $\\max(l_i, l_j) \\le \\min(r_i, r_j)$). The weight of this edge is defined as $\\min(i, j)$.\n\nYour task is to find the length of the shortest path from vertex $1$ to vertex $n$ in this graph. If there is no path between them, output $-1$.\n\n## Constraints\n- $1 \\le t \\le 100$\n- $2 \\le n \\le 10^5$\n- $1 \\le l_i \\le r_i \\le 2n$\n- The sum of $n$ over all test cases does not exceed $10^5$.","constraints":"$undefined","difficulty":"hard","order":6,"label":"$undefined","releaseDay":"$undefined","points":3000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"3\n3\n1 2\n4 5\n5 6\n4\n1 3\n3 5\n2 6\n5 7\n5\n1 2\n2 3\n3 4\n4 5\n5 6\n","expectedOutput":"-1\n3\n10\n","hidden":false,"explanation":"There is no intersection between the first interval and any other interval, so it is impossible to reach the destination.\n`\nThe optimal path is to move from the first interval to the second interval (with a cost of $\\min(1, 2) = 1$), and then from the second interval to the fourth interval (with a cost of $\\min(2, 4) = 2$). The total cost is $1 + 2 = 3$.\n`\nTo reach the fifth interval, the path must go through all intervals sequentially. The path goes from the first interval to the second, then the third, fourth, and finally the fifth. The costs of traversing these edges are $1$, $2$, $3$, and $4$, respectively, resulting in a total cost of $10$.\n","isSample":true,"displayInput":"3\n`\n3\n1 2\n4 5\n5 6\n`\n4\n1 3\n3 5\n2 6\n5 7\n`\n5\n1 2\n2 3\n3 4\n4 5\n5 6","displayOutput":"-1\n`\n3\n`\n10"}],"sampleCount":1,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\nl_1 \\quad r_1 \\\\\nl_2 \\quad r_2 \\\\\n\\vdots \\\\\nl_n \\quad r_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":3,"memoryLimit":512,"checker":{"type":"wcmp"},"solvedCount":5,"attemptedCount":7,"tags":["graphs","shortest paths","data structures"],"learnPages":[{"title":"Page 1","content":"### When do intervals intersect?\n\nTwo intervals intersect **iff** at least one left endpoint lies inside the other interval.\n\n**Short proof:** Assume $l_i \\le l_j$. If they intersect, then $l_j \\le r_i$, so: $l_j \\in [l_i, r_i]$\n\nThus every intersection satisfies one of:\n\n1. $l_j \\in [l_i, r_i]$\n2. $l_i \\in [l_j, r_j]$\n"},{"title":"Page 2","content":"### Simplifying the edges\n\nThe original graph has an undirected edge between $i$ and $j$ with weight $\\min(i, j)$, We replace each undirected edge with four directed edges:\n\n1. $i \\to j$ with weight $i$\n2. $i \\to j$ with weight $j$\n3. $j \\to i$ with weight $i$\n4. $j \\to i$ with weight $j$\n\nThe larger weight is never useful, but keeping both options makes the construction much easier.\n\nNow we only need to add edges between every $i$ and $j$ such that $l_i \\le l_j \\le r_i$ : one with weight $i$ and one with weight $j$."},{"title":"Page 3","content":"### Edges with weight $i$\n\nFor every interval $i$, we want to efficiently connect interval $i$ to all intervals $j$ whose **left endpoint** lies in $[l_i, r_i]$ with weight $i$.\n\n**Type 1 edges:**\n\nBuild a downward segment tree, add parent to child edges with weight $0$. For every interval $j$ add an edge from the leaf corresponding to $l_j$ to $j$ with weight $0$.\n\nFor each interval $i$, Decompose $[l_i, r_i]$ into $O(\\log n)$ segment tree nodes, Then add edges with weight $i$ from $i$ to all of these nodes.\n\n\n**Type 3 edges:**\n\nIt is similar to type 1 edges, except that we reverse the edge directions (i.e., we build an upward segment tree)."},{"title":"Page 4","content":"\n### Edges with weight $j$\n\nNow for every interval $i$, we want to connect interval $i$ to all intervals $j$ whose **left endpoint** lies in $[l_i, r_i]$ with weight $j$.\n\n**Type 2 edges:**\n\nBuild another downward segment tree, add parent to child edges with weight $0$. This time for every interval $j$ add an edge from the leaf corresponding to $l_j$ to $j$ with weight $j$.\n\nFor each interval $i$, Decompose $[l_i, r_i]$ into $O(\\log n)$ segment tree nodes, Then add edges with weight $0$ from $i$ to all of these nodes.\n\n\n**Type 4 edges:**\n\nAgain it is similar to type 2 edges, except that we reverse the edge directions.\n"},{"title":"Page 5","content":"### Finding shortest path\n\nNow we have a graph with $O(n)$ vertices and $O(n\\log n)$ edges, we can run Dijkstra's algorithm to compute the shortest path from vertex 1 to vertex n.\n\nThe time complexity is $O(n\\log^2n)$.\n\nCan you improve this to $O(n\\log n)$? "},{"title":"Page 6","content":"$3a"}],"hasLearnContent":true,"likeCount":0,"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":"6910e97ff1adda1971305d31","name":"Hamed Ghaffari"}],"statementOverrides":"$undefined","createdAt":"2026-04-05T21:09:29.633Z","updatedAt":"2026-06-30T19:07:21.375Z"}],"contestId":"69d2cf890e7e91b076b5260f","contestUrlId":"5","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":7200000}]]}]

ATV Volume	500	46/46
BSwap Parities	1000	42/43
CPermutation from Direction String	1500	29/33
DRemove Mountain	2000	21/24
EStick Division	2500	12/18
FShortest Path on Intervals	3000	5/7