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:T5d5,Make a left and a right copy of every graph vertex. For every original edge $uv$, add the bipartite edges $u_Lv_R$ and $v_Lu_R$. A partition into edges and triangles gives a perfect matching between the copies: swap the endpoints of every edge, and cyclically map the three vertices of every triangle. Conversely, a perfect matching defines a permutation of the vertices in which every vertex maps to a neighbor. Its cycles cover all vertices and have length at least two. An even cycle splits into pairs along its edges. For an odd cycle, direct every original edge from the smaller position to the larger position. Two consecutive cycle edges must form a directed path: otherwise their directions would alternate around an odd cycle, which is impossible. These three vertices form an increasing subsequence, since both positions and values increase along the path. Use them as one triple, and pair the remaining even-length path along its edges. Thus a perfect matching also gives a good partition. By Hall's theorem, a perfect matching fails to exist exactly when some set $A$ satisfies $|N(A)| < |A|$. Here the left and right copies are identified with their original vertices; $A$ and $N(A)$ may overlap. Set $S=A\setminus N(A)$. Its vertices have no neighbors in $A$, so $S$ is independent and $N(S)\subseteq N(A)\setminus A$. Consequently, $|S|-|N(S)|\ge |A|-|N(A)|>0$. We have proved that the array is not good exactly when a nonempty decreasing subsequence $S$ has $|N(S)|<|S|$.38:T4c8,Consider a directed path from a present symbol $u$ to an absent symbol $v$. We can transfer the hole from $v$ to $u$ without changing the presence of any other vertex on the path. To see this even when the path contains other holes, list its present vertices in path order. Move the last present symbol forward to $v$, through the intervening holes. Then move the preceding present symbol to the position just vacated, and continue backwards. Only $u$ becomes absent and $v$ becomes present. Inside a strongly connected component, there is a directed path between any two vertices. Consequently, if the component contains a hole, we can make any of its present vertices absent without creating another hole. We can visit every vertex and execute all its outgoing commands while it is absent. We can also rearrange any fixed number of holes to any desired positions in the component by exchanging an unwanted hole with a desired one. Contract the strongly connected components. The resulting graph is a DAG. Call a component **required** if it contains a vertex with an outgoing edge. The only components that are not required are singleton sinks. One visit by a hole is enough to process a required component completely.39:T72c,Process the starting components of the forward routes in topological order. For each route, create a hole at its last component, then move it backwards along the route to its starting component. Whenever the hole visits a component, use the internal moves described earlier to process all its commands. Why can we create that hole? All holes left by earlier groups are in earlier components. Every component strictly after the current starting component is therefore full. In a full nontrivial component, an internal command creates a hole. In a full singleton required component, an outgoing command creates one; its destination is also full. If the entire route stays in its starting component and that component already has a hole, no new hole is needed: that component has already been processed, so we can skip this route. To move a hole across a DAG edge $A\to B$, make its endpoint in $B$ absent and its source in $A$ present, then execute the command. The hole moves into $A$. Intermediate components are full before the new hole reaches them. The final component may already contain holes, but it still has a present vertex whenever another hole is needed: the routes assigned to this component have distinct starting vertices, so there are at most as many as its size. Internal moves can place that present symbol at the required source. After finishing a group, rearrange its holes onto its chosen starting vertices. If some routes were skipped, use a subset of those vertices, so the loss only decreases. Later groups cannot visit this component, because their routes start later in the DAG. All required components are processed, and the final loss is at most the cost of the route family. Together with the reverse-journey argument, this proves that minimizing route cost is exactly our original optimization problem.3a:T6c8,Let the required components be $C_1,\ldots,C_k$. If several routes visit a component, assign that component to just one of them. On each route, keep only the assigned components in order. Consecutive retained components need only be reachable from one another; they need not have a direct edge. Each required component now has exactly one predecessor of one of two kinds: - Another required component earlier on the same route. Each component can be the predecessor of at most one other component. - The original vertex $v$ at which its route starts. Each original vertex can start at most one route, and using it costs $a_v$. This is a rectangular minimum-cost assignment. Make one row for each required component and $k+n$ columns: - Component column $C_j$ can serve row $C_i$ at cost $0$ if $C_j\ne C_i$ and $C_j$ can reach $C_i$. - Vertex column $v$ can serve row $C_i$ at cost $a_v$ if the component containing $v$ can reach $C_i$, including the case where they are the same component. Every row must use one column, and each column can be used at most once. All other assignments are forbidden. Any route family gives such an assignment of no greater cost by discarding routes with no assigned components. Conversely, an assignment links the required components into chains: each has one predecessor and at most one successor, and a cycle is impossible because component-to-component links go strictly forward in the DAG. Following predecessors must end at a vertex column. These chains define the routes we need, with exactly the assignment cost. The distinction between the column types is essential: a component cannot precede itself for free, but an original vertex may start a route in its own component at cost $a_v$.3b:T74d,Consider three distinct vertices $u,w,v$ on a two-edge path. Suppose $u$ is odd and $v$ is even. We can swap their parities while leaving the parity of $w$ unchanged: - If their parities are $100$, use $100\to111\to001$. - If their parities are $110$, use $110\to000\to011$. Each arrow flips equal parities on an edge. In the first sequence, the reserve supplies the first change and is recovered by the second. In the second sequence, the first change creates a pair for the second. Thus both sequences are legal, and the number of pairs is unchanged at the end. Define an auxiliary graph $H$: two distinct vertices are adjacent in $H$ if they share a neighbor in the original graph. The sequences above let us move an odd marker to an empty vertex along an edge of $H$, while keeping a reserve pair after each completed move. On a connected graph, such moves connect all marker placements of the same size. To see this, take a spanning tree and fix its leaves one at a time. If a leaf needs a marker, choose a nearest marker and slide it through the empty vertices toward the leaf. If the leaf needs to be empty, bring a nearest empty position toward it by sliding markers in the opposite direction. Remove the fixed leaf and continue. The required marker or empty position exists because the current and desired numbers of markers agree. The components of $H$ have a simple description: - If the original graph is bipartite, they are exactly $L$ and $R$. Every two-edge step stays in one part, and an even-length path connects any two vertices in that part. - Otherwise, $H$ is connected. An odd cycle allows us to change the parity of the length of a walk: detour to the cycle, traverse it, and return. Thus any two vertices have an even-length walk between them, which breaks into two-edge steps. We only use $H$ in the proof; the algorithm never builds it.3c:T61d,Start by obtaining a reserve pair as described earlier. If there are $k$ odd vertices, the remaining $S-k$ balls form $(S-k)/2$ pairs. As long as $k$ stays fixed, moving odd markers keeps at least one reserve pair available. **Bipartite graph.** If both parts contain an odd marker, rearrange the markers within their respective components of $H$ so that the endpoints of a fixed original edge are both odd. Change $11\to00$ there. This removes one marker from each part and creates another pair. Repeat until one part has no markers. Exactly $|D|$ markers remain, all in the part determined by the sign of $D$. Move them to a fixed set of $|D|$ vertices in that part, for example the vertices with the smallest labels. Finally, collect every pair at vertex $1$. This final configuration depends only on $S$ and $D$. Therefore, any two active configurations with the same $S$ and $D$ can reach the same configuration. Reversibility then gives a sequence between them. **Non-bipartite graph.** Here $H$ is connected. Whenever at least two odd markers remain, rearrange them so that both endpoints of a fixed original edge are odd, then remove those two markers. Eventually, $S\bmod2$ markers remain. If one remains, move it to vertex $1$, and collect all pairs there too. Thus every active configuration with total $S$ can reach the configuration with all $S$ balls at vertex $1$. Equal totals are sufficient in this case. The counts in intermediate configurations may exceed the input bound $10^9$. This is allowed: that bound restricts only the given arrays.3d:T51e,Start at height $h=0$ and consider positive cups in their original order. We may choose cup $i$ when $P_{i-1}\le h0$ units. Stop choosing cups as soon as an endpoint reaches or exceeds $D$. The suffix after this last cup also has nonpositive sum, namely $D-P_i$. Reduce it in the same way and let the last chosen cup empty it. That cup retains $D-h>0$ units. Every operation empties a negative cup or a cup inside a gap, so all operations obey the original rule. Thus the answer is exactly the minimum number of these extensions needed to reach $D$. The original order of the intervals matters.3e:T6c5,#include "testlib.h" #include using namespace std; bool readArrangement(InStream& stream, int n, int m, const vector& a, const vector& b, int tc) { int first = stream.readInt(-1, n, "first output token"); if (first == -1) return false; if (first == 0) stream.quitf(_wa, "case %d: dish index 0", tc); vector p(n), used(n + 1, 0), starts(m + 1, 0); p[0] = first; for (int i = 1; i < n; ++i) p[i] = stream.readInt(1, n, "dish index"); for (int id : p) { if (used[id]++) stream.quitf(_wa, "case %d: dish %d occurs twice", tc, id); } for (int i = 0; i < n; ++i) { int cur = p[i], prev = p[(i + n - 1) % n]; for (int v : {a[cur], b[cur]}) { if (v != a[prev] && v != b[prev] && ++starts[v] > 1) stream.quitf(_wa, "case %d: sauce %d has multiple blocks", tc, v); } } return true; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); int t = inf.readInt(); for (int tc = 1; tc <= t; ++tc) { int n = inf.readInt(), m = inf.readInt(); vector a(n + 1), b(n + 1); for (int i = 1; i <= n; ++i) a[i] = inf.readInt(), b[i] = inf.readInt(); bool jury = readArrangement(ans, n, m, a, b, tc); bool participant = readArrangement(ouf, n, m, a, b, tc); if (jury && !participant) quitf(_wa, "case %d: an arrangement exists", tc); if (!jury && participant) quitf(_fail, "case %d: participant found an arrangement", tc); } if (!ans.seekEof()) quitf(_fail, "extra tokens in jury output"); if (!ouf.seekEof()) quitf(_wa, "extra tokens in participant output"); quitf(_ok, "all arrangements are valid"); } 3f:T46e,Within a connected component, its core is connected whenever it is nonempty. Indeed, every internal vertex of a path joining two core vertices also has degree at least two. A connected graph of maximum degree two is a path, a single vertex, or a cycle. Therefore, after the previous check, each component containing edges has one of these forms: - A single edge, with an empty core. - A path of core vertices, with leaves attached to them. A single core vertex is allowed. - A cycle of core vertices, with leaves attached to them. There is one extra restriction: a cycle component must be the only component containing edges. To see why, suppose another component has an edge. Cut the circular order at that edge. The blocks of all cycle vertices now become ordinary intervals. Consider the first cycle edge $uv$ in this linear order. Both $u$ and $v$ have another cycle edge later, so the next edge must contain both $u$ and $v$ to keep both intervals unbroken. This would be another copy of $uv$, but the graph is simple. Hence such an order cannot exist. Unused sauce vertices have no edges and do not affect this restriction.40:T40e,Duplicate pairs can be grouped without sorting. Normalize each pair to $up_j$. The crucial property is $N(j)\\cap N(S)=N(j)\\cap N(i)$.\n\nTo see this, take an earlier member $h$ of $S$, with $hp_i>p_j$. A common neighbor of $h$ and $j$ is either before $h$ with value below $p_j$, or after $j$ with value above $p_h$. In either case it is also a neighbor of $i$. The reverse inclusion holds because $i\\in S$.\n\nTherefore, appending $j$ adds exactly $\\deg(j)-c(i,j)$ new neighbors, where $c(i,j)=|N(i)\\cap N(j)|$. It also adds one member to $S$, giving the transition $dp_j=\\min(dp_j,dp_i+\\deg(j)-c(i,j)-1)$.\n\nProcess positions from left to right and try every eligible predecessor. The answer is $\\max(0,1+\\min_j dp_j)$."},{"title":"Counting in quadratic time and linear space","content":"For $ip_j$, their common neighbors are precisely:\n\n- positions before $i$ whose values are smaller than $p_j$;\n- positions after $j$ whose values are greater than $p_i$.\n\nFix $j$. Keep a presence array for the values at positions after $j$, and compute its suffix sums $R[v]$, the number of those values greater than $v$, in $O(n)$ time.\n\nCount $L$, the number of elements before $j$ smaller than $p_j$. Then $\\deg(j)=L+R[p_j]$.\n\nScan $i=j-1,j-2,\\ldots,1$. Whenever $p_ip_j$, the current $L$ counts exactly the values below $p_j$ before $i$, so $c(i,j)=L+R[p_i]$ and the transition takes constant time.\n\nEach position takes $O(n)$ time, for $O(n^2)$ total time and $O(n)$ auxiliary memory. Across all test cases, the time is $O(\\sum n^2)$, which is bounded by $O((\\sum n)^2)$."}],"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-09-15T18:46:10.354Z","updatedAt":"2026-09-16T18:59:28.751Z"},{"_id":"6aaae8bc69b40741ba11f27c","contestId":"6aa6ea4e982e23f8568a79d3","slug":"surviving-symbols","title":"Surviving Symbols","description":"You have a sequence $s$ of length $n$, initially equal to $(1,2,\\ldots,n)$.\n\nFor each symbol $i$, you are given a positive integer $a_i$, its value.\n\nThere are $m$ commands. Command $j$ is specified by two distinct symbols $x_j$ and $y_j$. Executing it simultaneously replaces every current occurrence of $x_j$ in $s$ with $y_j$. If $x_j$ does not occur in $s$, the sequence remains unchanged, but the command still counts as executed.\n\nYou may execute a finite sequence of commands in any order. Each command may be executed multiple times, but every given command must be executed at least once.\n\nLet $D$ be the set of symbols occurring in $s$ after you finish. The final value is $\\sum_{i\\in D} a_i$: each distinct symbol contributes its value exactly once, regardless of its number of occurrences.\n\nFind the maximum possible final value.","constraints":"- $1 \\le t \\le 10$\n- $1 \\le n \\le 500$\n- $0 \\le m \\le n(n-1)$\n- $1 \\le a_i \\le 10^9$\n- $1 \\le x_j,y_j \\le n$\n- $x_j \\ne y_j$\n- The ordered pairs $(x_j,y_j)$ are pairwise distinct within each test case.\n- The sum of $n$ over all test cases is at most $500$.","difficulty":"hard","order":3,"label":"F","releaseDay":"$undefined","points":3000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2\n3 2\n8 5 3\n1 2\n2 3\n3 3\n4 9 6\n1 2\n2 3\n3 1\n","expectedOutput":"8\n15\n","isSample":true,"hidden":false,"explanation":"Execute $2\\to3$, then $1\\to2$. The final sequence is $(2,3,3)$, with value $5+3=8$. Symbol $1$ must be absent at the end because its outgoing command must be executed and no command can produce it.\n`\nExecute $1\\to2$, $3\\to1$, $2\\to3$, and $1\\to2$ again. The final sequence is $(3,3,2)$, with value $6+9=15$. The first command executed makes at least one symbol absent, and the number of distinct symbols can never increase. Since the smallest symbol value is $4$, the value cannot exceed $4+9+6-4=15$.\n","displayInput":"2\n`\n3 2\n8 5 3\n1 2\n2 3\n`\n3 3\n4 9 6\n1 2\n2 3\n3 1\n","displayOutput":"8\n`\n15\n"},{"input":"3\n4 0\n1000000000 7 1000000000 3\n4 5\n2 8 5 9\n1 2\n2 1\n1 3\n3 4\n4 3\n5 6\n10 4 8 3 7\n1 2\n1 4\n2 3\n3 2\n4 5\n5 4\n","expectedOutput":"2000000010\n22\n19\n","isSample":true,"hidden":false,"explanation":"There are no commands, so every symbol remains present. Their total value is $2000000010$.\n`\nExecute $3\\to4$, $4\\to3$, $3\\to4$, $1\\to3$, $1\\to2$, $2\\to1$, and $1\\to2$. The final sequence is $(3,2,4,4)$, so the value is $5+8+9=22$. The command $1\\to2$ executed while $1$ is absent still counts as executed. At least one symbol must become absent, so losing only the smallest value, $2$, is optimal.\n`\nExecute $2\\to3$, $3\\to2$, $2\\to3$, $1\\to2$, $1\\to4$, $4\\to5$, $5\\to4$, and $4\\to5$. The final sequence is $(2,3,3,5,5)$, with value $4+8+7=19$.\n\nSymbol $1$ must be absent at the end. Each of the pairs $\\{2,3\\}$ and $\\{4,5\\}$ must lose a symbol when one of its internal commands is first executed. Only a command with source $1$ can restore a missing symbol in either pair, and such a command can change the sequence at most once. Therefore at least one additional symbol must remain absent. The shown execution loses values $10$ and $3$, the smallest possible total loss.\n","displayInput":"3\n`\n4 0\n1000000000 7 1000000000 3\n`\n4 5\n2 8 5 9\n1 2\n2 1\n1 3\n3 4\n4 3\n`\n5 6\n10 4 8 3 7\n1 2\n1 4\n2 3\n3 2\n4 5\n5 4","displayOutput":"2000000010\n`\n22\n`\n19"}],"sampleCount":2,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad m \\\\\na_1 \\quad a_2 \\quad \\ldots \\quad a_n \\\\\nx_1 \\quad y_1 \\\\\nx_2 \\quad y_2 \\\\\n\\vdots \\\\\nx_m \\quad y_m\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\mathrm{answer}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":3,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":6,"attemptedCount":8,"tags":["graph","matching"],"learnPages":[{"title":"Follow the missing symbols","content":"Build a directed graph with an edge $x_j\\to y_j$ for every command. Only the presence of a symbol matters, not its number of occurrences.\n\nCall an absent symbol a **hole**. Initially there are no holes. Executing $x\\to y$ has three possible effects:\n\n- If $x$ is absent, nothing changes.\n- If $x$ and $y$ are present, a new hole appears at $x$.\n- If $x$ is present and $y$ is absent, the hole moves from $y$ to $x$.\n\nThus holes are created but never destroyed, and they move **against the edges**. If the final holes form a set $H$, our loss is $\\sum_{v\\in H}a_v$.\n\nEvery vertex with an outgoing edge must be a hole at some moment: immediately after executing that edge, its source is absent. Conversely, whenever a vertex is a hole, we can execute all of its outgoing commands without changing anything.\n\nSo our task is to visit every vertex with outgoing edges using holes, while minimizing the total value of their final positions."},{"title":"One hole can visit a whole component","content":"$38"},{"title":"Reverse the journey of each hole","content":"Track each hole from its creation to its final position. After contracting components, its journey follows a path against the DAG edges. Reverse that journey: it is now a forward route starting at the component of a final missing symbol.\n\nTherefore every valid execution gives a family of forward routes with these properties:\n\n- Every required component lies on at least one route.\n- Every route starts at a distinct original vertex $v$, whose value $a_v$ is paid.\n- Several routes may start in the same component, provided they use different original vertices. Routes may also share intermediate components.\n\nWe may stop a route at its last required component. A route covering no required component can be discarded.\n\nThese conditions are also sufficient to obtain a loss no larger than the sum of the route costs. The next page explains how to realize the routes. This matters: forcing routes to be vertex-disjoint, or allowing only one final hole per component, would change the answer."},{"title":"Realizing the routes","content":"$39"},{"title":"Turn route coverage into an assignment","content":"$3a"},{"title":"Compute the minimum lost value","content":"Compute reachability with Floyd--Warshall. Vertices $u,v$ belong to the same strongly connected component exactly when each can reach the other, so the same table also identifies the components and all allowed assignments.\n\nBuild the cost matrix from the previous page and find a minimum-cost assignment using the rectangular Hungarian algorithm. A finite assignment always exists: assign each required component a distinct vertex from within that component.\n\nIf its cost is $L$, the answer is $\\sum_{i=1}^{n}a_i-L$.\n\nThere are $k\\le n$ rows and $n+k\\le 2n$ columns. Hungarian takes $O(k^2(n+k))$ time, and reachability takes $O(n^3)$ time. The total complexity is **$O(n^3)$ time and $O(n^2)$ memory** per test case. Use 64-bit integers for costs, potentials, and the answer.\n\nIf there are no commands, there are no required components and $L=0$."}],"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-09-16T19:06:36.292Z","updatedAt":"2026-09-20T14:34:26.356Z"},{"_id":"6aaaed74f81dfd38209d27a5","contestId":"6aa6ea4e982e23f8568a79d3","slug":"one-ball-stays","title":"One Ball Stays","description":"You are given a simple connected undirected graph with $n$ vertices and $m$ edges. Initially, vertex $v$ contains $a_v$ balls.\n\nIn one operation, choose two adjacent vertices and keep one ball at one of them. Swap all the remaining balls between the two vertices.\n\nFormally, choose an ordered pair of adjacent vertices $(u,v)$ such that vertex $u$ currently contains at least one ball. If their current numbers of balls are $x$ and $y$, respectively, replace them simultaneously by $y+1$ and $x-1$. All other vertices remain unchanged.\n\nDetermine whether, after zero or more operations, every vertex $v$ can contain exactly $b_v$ balls.","constraints":"- $1 \\le t \\le 10^4$\n- $2 \\le n \\le 2 \\times 10^5$\n- $n-1 \\le m \\le 2 \\times 10^5$\n- $0 \\le a_v,b_v \\le 10^9$\n- $1 \\le u_i,v_i \\le n$\n- The graph is simple, connected, and undirected.\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$.\n- The sum of $m$ over all test cases is at most $2 \\times 10^5$.","difficulty":"medium","order":4,"label":"D","releaseDay":"$undefined","points":2000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2\n2 1\n4 1\n2 3\n1 2\n2 1\n1 0\n0 1\n1 2\n","expectedOutput":"YES\nNO\n","isSample":true,"hidden":false,"explanation":"Choose vertices 1 and 2, keeping one ball at vertex 1. The counts change from (4,1) to (2,3), which is the required configuration.\n`\nThe only legal choice keeps the ball at vertex 1 and leaves the configuration unchanged. The ball can never reach vertex 2.\n","displayOutput":"Yes\n`\nNo","displayInput":"2\n`\n2 1\n4 1\n2 3\n1 2\n`\n2 1\n1 0\n0 1\n1 2"},{"input":"3\n3 3\n3 0 0\n0 3 0\n1 2\n2 3\n1 3\n3 2\n3 0 0\n0 3 0\n1 2\n2 3\n3 2\n1 0 1\n1 0 1\n1 2\n2 3\n","expectedOutput":"YES\nNO\nYES\n","isSample":true,"hidden":false,"explanation":"One possible sequence of configurations is (3,0,0), (1,2,0), (1,1,1), (2,1,0), (0,3,0). In these four operations, the ordered pairs of chosen vertices are (1,2), (2,3), (1,3), and (2,1), respectively; the first vertex of each pair keeps one ball.\n`\nThe counts are the same as in the preceding example, but vertices 1 and 3 are not adjacent. No sequence of legal operations reaches the required configuration.\n`\nThe initial configuration already equals the required configuration, so zero operations suffice.\n","displayOutput":"Yes\n`\nNo\n`\nYes","displayInput":"3\n`\n3 3\n3 0 0\n0 3 0\n1 2\n2 3\n1 3\n`\n3 2\n3 0 0\n0 3 0\n1 2\n2 3\n`\n3 2\n1 0 1\n1 0 1\n1 2\n2 3"}],"sampleCount":2,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\quad m \\\\\na_1 \\quad a_2 \\quad \\ldots \\quad a_n \\\\\nb_1 \\quad b_2 \\quad \\ldots \\quad b_n \\\\\nu_1 \\quad v_1 \\\\\nu_2 \\quad v_2 \\\\\n\\vdots \\\\\nu_m \\quad v_m\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\texttt{Yes} \\;\\text{or}\\; \\texttt{No}\n\\end{array}\n\\right\\} \\times t\n$$\n\nThe answer is case-insensitive. Any capitalization of the letters is accepted, including $\\texttt{YES}$, $\\texttt{yes}$, and $\\texttt{YeS}$.","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"custom","sourceCode":"#include \"testlib.h\"\n#include \nusing namespace std;\n\nstring readAnswer(InStream &stream) {\n string token = upperCase(stream.readToken());\n if (token != \"YES\" && token != \"NO\")\n stream.quitf(_wa, \"Expected YES or NO\");\n return token;\n}\n\nint main(int argc, char* argv[]) {\n registerTestlibCmd(argc, argv);\n int t = inf.readInt();\n for (int tc = 1; tc <= t; ++tc) {\n string expected = readAnswer(ans);\n string found = readAnswer(ouf);\n if (expected != found)\n quitf(_wa, \"Wrong answer in test case %d\", tc);\n }\n if (!ouf.seekEof()) quitf(_wa, \"Extra output tokens\");\n quitf(_ok, \"%d answers\", t);\n}\n"},"solvedCount":15,"attemptedCount":24,"tags":["graphs"],"learnPages":[{"title":"When every operation does nothing","content":"The total number of balls is preserved, so different totals immediately give NO. If the two arrays are identical, zero operations give YES.\n\nCall a configuration **frozen** if every count is $0$ or $1$ and no two occupied vertices are adjacent. Every legal operation then acts on $(1,0)$ and returns $(1,0)$, so the configuration never changes.\n\nEvery other configuration can change. A vertex with at least two balls can use any incident edge. Otherwise, two adjacent occupied vertices have counts $(1,1)$, which can become $(2,0)$.\n\nThe operation is reversible: applying it again while keeping a ball at the same vertex gives $(x,y)\\to(y+1,x-1)\\to(x,y)$. The reverse is legal because $y+1\\ge1$.\n\nConsequently, a frozen configuration cannot be reached from a different configuration either. After handling equality, reject if either configuration is frozen. From now on, both configurations are **active** and have the same total $S$."},{"title":"A pair can travel anywhere","content":"Suppose an edge has counts $(x,y)$ with $x\\ge2$. Keep a ball first at the first endpoint and then at the second endpoint:\n\n$$\n(x,y)\\longrightarrow(y+1,x-1)\\longrightarrow(x-2,y+2).\n$$\n\nBoth operations are legal. Thus we can transfer exactly two balls along any edge while leaving all other counts unchanged.\n\nThink of each count as several pairs plus one possible leftover ball. A pair can travel along any path. Therefore, for a fixed set of odd-count vertices, we can distribute the pairs arbitrarily throughout the connected graph.\n\nEvery active configuration can obtain at least one pair. Either some vertex already has two balls, or we apply $(1,1)\\to(2,0)$ on an occupied edge.\n\nWe will use such a pair as a movable reserve. Its location does not matter, because we can bring it to any vertex without changing any parity."},{"title":"What an operation does to parity","content":"Let $p_v$ be the parity of the count at vertex $v$. On an edge $(u,v)$, an operation changes\n\n$$\n(p_u,p_v)\\longrightarrow(1-p_v,1-p_u).\n$$\n\nDifferent parities stay unchanged. Equal parities change as $00\\leftrightarrow11$.\n\nThe change $11\\to00$ is always possible: both endpoints have a ball. It decreases the number of odd vertices by two, so it creates one additional pair.\n\nFor $00\\to11$, bring a reserve pair to one endpoint first. That endpoint has at least two balls, so the operation is legal. This change uses one pair.\n\nIf the graph is bipartite with parts $L$ and $R$, every such change adds or removes one odd vertex in each part. Hence\n\n$$\nD=\\sum_{v\\in L}p_v-\\sum_{v\\in R}p_v\n$$\n\nis invariant. Equal totals alone are therefore insufficient on bipartite graphs. We still need to prove that there are no further restrictions on active configurations."},{"title":"Moving an odd vertex by two edges","content":"$3b"},{"title":"Reducing to the same configuration","content":"$3c"},{"title":"Checking the conditions in linear time","content":"For each test case:\n\n1. If $a=b$, output YES.\n2. If $\\sum a_v\\ne\\sum b_v$, output NO.\n3. Check whether either configuration is frozen. A configuration is active precisely when some count is at least two, or some edge has two positive endpoints. If either is frozen, output NO.\n4. Two-color the graph using BFS or an iterative DFS. If it is not bipartite, output YES.\n5. Otherwise, compute $D(a)$ and $D(b)$ using the two color classes. Output YES exactly when they are equal.\n\nThe previous reductions prove that every accepted pair is reachable, and the total, frozen-state condition, and bipartite invariant prove that every rejected pair is unreachable.\n\nThe time complexity is $O(n+m)$ per test case, and the memory complexity is $O(n+m)$. Use 64-bit integers for the totals, which can be as large as $2\\times10^{14}$."}],"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-09-16T19:26:44.940Z","updatedAt":"2026-09-19T22:13:11.810Z"},{"_id":"6aaed9dd60c33cf7fdf4b909","contestId":"6aa6ea4e982e23f8568a79d3","slug":"last-sip","title":"Last Sip","description":"There are $n$ cups in a row. Cup $i$ contains $a_i$ units of either tea or coffee. A string $s$ describes their drinks: $s_i=\\texttt{T}$ means tea, and $s_i=\\texttt{C}$ means coffee.\n\nIn one operation, choose two adjacent cups containing different drinks. If their current amounts are $x$ and $y$, drink $\\min(x,y)$ units from **each** cup. Remove every cup that becomes empty, and close the gaps in the row.\n\nFind the minimum number of cups that can remain after any number of operations.","constraints":"- $1 \\le t \\le 10^4$\n- $1 \\le n \\le 2 \\times 10^5$\n- $1 \\le a_i \\le 10^9$\n- $s$ has length $n$ and consists only of the characters $\\texttt{T}$ and $\\texttt{C}$.\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$.","difficulty":"medium","order":5,"label":"C","releaseDay":"$undefined","points":1500,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2\n3\nTCT\n2 1 1\n3\nTCC\n3 1 2\n","expectedOutput":"1\n0\n","isSample":true,"hidden":false,"explanation":"Choose cups 2 and 3. Both become empty, leaving only cup 1. The initial row contains 2 more units of tea than coffee, so it cannot become empty.\n`\nChoose cups 1 and 2 and drink 1 unit from each. The remaining cups contain 2 units of tea and 2 units of coffee. One more operation empties both.\n","displayInput":"2\n`\n3\nTCT\n2 1 1\n`\n3\nTCC\n3 1 2","displayOutput":"1\n`\n0"},{"input":"3\n1\nC\n7\n8\nTTTCCTTT\n1 1 2 2 2 2 1 1\n4\nTTTT\n2 5 1 4\n","expectedOutput":"1\n3\n4\n","isSample":true,"hidden":false,"explanation":"There is only one cup, so no operation is possible.\n`\nUsing original cup numbers, first choose cups 3 and 4, emptying both. Next, choose cups 2 and 5, then cups 1 and 5. This leaves cups 6, 7, and 8. Four units of tea must remain. To keep only two cups, both cups 3 and 6 would have to remain with their full 2 units. But while cup 3 survives, the tea in cups 1 and 2 cannot reach any coffee. Thus two remaining cups are impossible.\n`\nEvery cup contains tea, so no operation is possible and all four cups remain.\n","displayInput":"3\n`\n1\nC\n7\n`\n8\nTTTCCTTT\n1 1 2 2 2 2 1 1\n`\n4\nTTTT\n2 5 1 4","displayOutput":"1\n`\n3\n`\n4"}],"sampleCount":2,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\ns \\\\\na_1 \\quad a_2 \\quad \\ldots \\quad a_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\mathrm{answer}\n\\end{array}\n\\right\\} \\times t\n$$\n\nFor each test case, print the minimum number of cups that can remain.","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":23,"attemptedCount":33,"tags":["greedy"],"learnPages":[{"title":"The drink that remains","content":"Give tea a positive sign and coffee a negative sign: let $x_i=a_i$ for tea and $x_i=-a_i$ for coffee. An operation preserves the sum $D=\\sum x_i$.\n\nAs long as both drinks remain, some two adjacent cups contain different drinks, so another operation is possible. Thus an optimal final row contains only one drink.\n\nIf $D=0$, continuing until no operation is possible empties the entire row. Otherwise, the remaining drink has the sign of $D$. Negate all $x_i$ if necessary so that $D>0$. We now want as few positive cups as possible, containing $D$ units in total."},{"title":"Where a survivor can fit","content":"Let $P_0=0$ and $P_i=x_1+\\cdots+x_i$.\n\nSuppose cup $i$ survives with $r>0$ units, and the surviving cups before it contain $h$ units in total. No operation can connect cups on opposite sides of cup $i$, because it never disappears.\n\nLet $L$ and $R$ be the amounts cup $i$ supplies to negative cups on its left and right. All other cancellations on each side preserve that side's signed sum, so $P_{i-1}=h-L$ and $P_i=h+r+R$. Consequently, $[h,h+r]$ lies inside $[P_{i-1},P_i]$.\n\nTherefore, the surviving positive cups, in their original order, must cover consecutive pieces of $[0,D]$ with their intervals $[P_{i-1},P_i]$. This is a necessary condition; next we turn it into a construction using legal operations."},{"title":"Extend as far as possible","content":"$3d"},{"title":"A DP over heights","content":"Process cups from left to right. Let $dp[h]$ be the minimum number of chosen cups in a chain ending at height $h$, using only cups already processed. Initially $dp[0]=0$ and all other states are unreachable.\n\nA negative cup gives no transition. For a positive cup, set $l=\\max(0,P_{i-1})$ and $r=\\min(D,P_i)$. If $l\\ge r$, skip it. Otherwise, we may extend any chain whose endpoint satisfies $l\\le hX}q)$, with the inner maximum omitted when there are no remaining pairs.\n\nAs $X$ increases, this value of $Y$ changes only when $X$ reaches some $p$. Between two such values, increasing $X$ only makes $X+Y$ larger. It is therefore enough to try $X=A$ and all pair values $p>A$.\n\nSort the pairs by $p$ and build suffix maxima of $q$, including $B$ in every maximum. Sweep the candidate values of $X$. After skipping all pairs with $p\\le X$, the suffix maximum gives the required $Y$ in constant time. Take the minimum of $X+Y$.\n\nWith $m$ opposite pairs, this takes $O(n+m\\log(m+1))$ time and $O(n+m)$ memory. Since $m\\le n^2/4$, the worst-case bounds are $O(n^2\\log n)$ time and $O(n^2)$ memory."}],"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-09-20T13:19:34.873Z","updatedAt":"2026-09-20T13:19:50.338Z"}],"contestId":"6aa6ea4e982e23f8568a79d3","contestUrlId":"24","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}]]}]

ATissue Rush	500	75/77
BSauce Circle	1000	29/42
CLast Sip	1500	23/33
DOne Ball Stays	2000	15/24
ETea or Coffee First	2500	12/12
FSurviving Symbols	3000	6/8
GBreaking the Partition	3250	2/2