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:T913,#include "testlib.h" #include using namespace std; struct DSU { vector parent, size; explicit DSU(int n) : parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); } int find(int v) { while (v != parent[v]) { parent[v] = parent[parent[v]]; v = parent[v]; } return v; } bool unite(int u, int v) { u = find(u); v = find(v); if (u == v) return false; if (size[u] < size[v]) swap(u, v); parent[v] = u; size[u] += size[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(); vector x(n); vector required(n), degree(n, 0); for (auto &value : x) value = inf.readLong(); for (int &value : required) value = inf.readInt(); // Compute the optimum independently of the jury construction. long long optimal = 0, balance = 1; for (int i = 0; i + 1 < n; ++i) { balance += required[i] - 2; optimal += (x[i + 1] - x[i]) * (1 + abs(balance)); } DSU dsu(n); long long cost = 0; for (int i = 0; i < n - 1; ++i) { int u = ouf.readInt(1, n, "u") - 1; int v = ouf.readInt(1, n, "v") - 1; if (!dsu.unite(u, v)) { quitf(_wa, "test case %d: a self-loop, repeated edge, or cycle", tc); } ++degree[u]; ++degree[v]; cost += abs(x[u] - x[v]); } // An acyclic graph on n vertices with n-1 edges is connected. for (int i = 0; i < n; ++i) { if (degree[i] != required[i]) { quitf(_wa, "test case %d: vertex %d has degree %d, expected %d", tc, i + 1, degree[i], required[i]); } } if (cost != optimal) { quitf(_wa, "test case %d: cost %lld, minimum cost %lld", tc, cost, optimal); } } // seekEof skips trailing whitespace, but detects extra tokens. if (!ouf.seekEof()) quitf(_wa, "extra non-whitespace tokens in the output"); quitf(_ok, "all trees are valid and have minimum cost"); } 38:T1200,Call a vertex a leaf if its required degree is $1$, and call every other vertex an internal vertex. We will construct an optimal tree in $O(n)$ time. ## Construction For $n=2$, output the only possible edge. Otherwise, list all internal vertices in increasing order of their coordinates and connect consecutive vertices in this list. This forms a path through the internal vertices. Subtract the degrees used by this path from their required degrees. Each remaining unit of degree at an internal vertex is a slot for one leaf. List the slots in increasing coordinate order, repeating an internal vertex as many times as its remaining degree. Match the leaves, also in increasing coordinate order, to these slots in order. There is no need to explicitly store the list of slots. A pointer to the first internal vertex with positive remaining degree is sufficient. ## Why the result is a valid tree Let $h$ be the number of internal vertices and $L$ the number of leaves. A valid degree sequence has positive entries and total degree $2(n-1)$. For $n>2$, at least one internal vertex exists. The internal path uses at most two units of degree at each internal vertex, so no remaining degree becomes negative. The number of remaining slots is $$ \sum_{d_i\ge 2} d_i-2(h-1) =2(n-1)-L-2(h-1) =L. $$ Consequently, every leaf receives exactly one edge, and every internal vertex attains its required degree. The internal vertices form a connected path, and every other vertex is attached to this path by one edge. Hence the result is a tree. ## A lower bound for each gap Consider the gap between $x_i$ and $x_{i+1}$, where $1\le ic_v$, no assignment exists. There are $\binom{c_v}{d}$ choices when the sizes are equal, and $2\binom{c_v}{d}$ otherwise, since either end can receive the smaller group. Multiply $W$ by this factor, replace $(x,y)$ with $(v+d,v+c_v-d)$, and increase $k$ by two. Although we keep the ends in sorted order, all counted placements have the same remaining problem. Their orientations and the identities of already placed people do not change the possible groups still to be placed. ## Finish with actual ages Let $v$ be the last distinct report and $c=c_v$. Once again, require $v=x$. If $xm$. Therefore the final answer is - $W\binom{m}{k+1}$ if $x\n#include \n#include \nusing namespace std;\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 array area;\n for (auto &x : area) x = inf.readLong();\n sort(area.begin(), area.end());\n string expected = area[0] * area[3] == area[1] * area[2] ? \"yes\" : \"no\";\n string actual = ouf.readToken();\n for (char &ch : actual) ch = char(tolower(static_cast(ch)));\n if (actual != \"yes\" && actual != \"no\")\n quitf(_wa, \"Test case %d: expected Yes or No\", tc);\n if (actual != expected)\n quitf(_wa, \"Test case %d: expected %s, found %s\", tc, expected.c_str(), actual.c_str());\n }\n if (!ouf.seekEof()) quitf(_wa, \"Extra non-whitespace output\");\n quitf(_ok, \"All %d answers are correct\", t);\n}\n"},"solvedCount":59,"attemptedCount":68,"tags":["math"],"learnPages":[{"title":"Opposite pieces","content":"Let the two widths be $x,y$ and the two heights be $u,v$. The four areas, in their grid positions, are $xu,yu,xv,yv$. The products of diagonally opposite areas are equal, since $(xu)(yv)=(yu)(xv)$.\n\nThis condition is also sufficient. Suppose the desired grid has top row $p,q$ and bottom row $r,s$, where $ps=qr$. Choose widths $p,q$ and heights $1,r/p$. The areas are then $p,q,r,qr/p$, and the last one equals $s$. All dimensions are positive, and fractional dimensions are allowed.\n\n# Three possible pairings\n\nThere are only three ways to split four numbers into two pairs. Therefore, output Yes if at least one of $ab=cd$, $ac=bd$, or $ad=bc$ holds; otherwise, output No.\n\nUse 64-bit integers for multiplication: a product can be as large as $10^{18}$.\n\nThe solution takes $O(1)$ time and $O(1)$ extra space per test case, or $O(t)$ time overall."}],"hasLearnContent":true,"likeCount":2,"neutralCount":0,"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-09-05T22:40:07.436Z","updatedAt":"2026-09-06T02:58:45.514Z"},{"_id":"6a9ca17210da1f0dc6d2d497","contestId":"6a9663e11c611662a15b197b","slug":"opposite-workflows","title":"Opposite Workflows","description":"A workshop has two machines, $A$ and $B$, and needs to prepare $n$ pieces.\n\nPiece $i$ must be processed for $a_i$ minutes on **each** machine. Its processing order is determined by $s_i$:\n\n- If $s_i$ is `A`, it must be processed on machine $A$ first, then on machine $B$.\n- If $s_i$ is `B`, it must be processed on machine $B$ first, then on machine $A$.\n\nEach machine can process at most one piece at a time. Once processing a piece on a machine starts, it cannot be interrupted. A piece may wait between its two stages. The machines may work simultaneously on different pieces.\n\nAll pieces are available at time $0$. You may choose when to start each stage, subject to these rules.\n\nFind the minimum time by which all pieces can finish processing on both machines.","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_i$ is either `A` or `B`.\n- The sum of $n$ over all test cases is at most $2 \\times 10^5$.","difficulty":"easy","order":6,"label":"B","releaseDay":"$undefined","points":1000,"vivePrize":"$undefined","submissionKind":"code","proofJudgeTier":"$undefined","proofJudgeCount":"$undefined","proofSubmissionMode":"$undefined","proofLeanStatement":"$undefined","answerFormat":"$undefined","testCases":[{"input":"2\n1\n4 A\n2\n3 A\n3 B\n","expectedOutput":"8\n6\n","isSample":true,"hidden":false,"explanation":"The only piece needs 4 minutes on A followed by 4 minutes on B, so it finishes at time 8.\n`\nProcess piece 1 on A and piece 2 on B from time 0 to time 3. Then swap the pieces between the machines and process them from time 3 to time 6. Each piece needs 6 minutes in total, so finishing earlier is impossible.\n","displayOutput":"8\n`\n6","displayInput":"2\n`\n1\n4 A\n`\n2\n3 A\n3 B"},{"input":"3\n3\n2 A\n2 A\n2 A\n3\n6 A\n2 B\n1 B\n3\n3 A\n2 A\n4 B\n","expectedOutput":"8\n12\n9\n","isSample":true,"hidden":false,"explanation":"A processes pieces 1, 2, and 3 during $[0, 2]$, $[2, 4]$, and $[4, 6]$. B processes them during $[2, 4]$, $[4, 6]$, and $[6, 8]$. Machine B cannot start before time 2 and needs 6 minutes of processing, so finishing earlier than time 8 is impossible.\n`\nA processes piece 1 during $[0, 6]$, piece 2 during $[6, 8]$, and piece 3 during $[8, 9]$. B processes piece 2 during $[0, 2]$, piece 3 during $[2, 3]$, and piece 1 during $[6, 12]$. Piece 1 alone needs 12 minutes across its two stages, so this schedule is optimal.\n`\nA processes pieces 1, 2, and 3 during $[0, 3]$, $[3, 5]$, and $[5, 9]$. B processes pieces 3, 1, and 2 during $[0, 4]$, $[4, 7]$, and $[7, 9]$. Each machine has 9 minutes of work, so this schedule is optimal.\n","displayOutput":"8\n`\n12\n`\n9","displayInput":"3\n`\n3\n2 A\n2 A\n2 A\n`\n3\n6 A\n2 B\n1 B\n`\n3\n3 A\n2 A\n4 B"}],"sampleCount":2,"inputFormat":"$$$\nt\n$$\n$$\n\\left.\n\\begin{array}{l}\nn \\\\\na_1 \\quad s_1 \\\\\na_2 \\quad s_2 \\\\\n\\vdots \\\\\na_n \\quad s_n\n\\end{array}\n\\right\\} \\times t\n$$","outputFormat":"$$$\n\\left.\n\\begin{array}{l}\n\\text{minimum completion time}\n\\end{array}\n\\right\\} \\times t\n$$","interactionFormat":"$undefined","timeLimit":2,"memoryLimit":256,"checker":{"type":"wcmp"},"solvedCount":42,"attemptedCount":49,"tags":["greedy","math"],"learnPages":[{"title":"Workload and the longest piece","content":"$3b"}],"hasLearnContent":true,"likeCount":1,"neutralCount":0,"dislikeCount":0,"isInteractive":false,"interactor":"$undefined","hidden":false,"sampleTestCases":"$undefined","samplesDiverged":"$undefined","sourceAttribution":"$undefined","source":"$undefined","validatorSource":"$undefined","correctSolution":"$undefined","generators":"$undefined","genDataContent":"$undefined","readiness":"$undefined","linkedBuildSessionId":"$undefined","isLinked":"$undefined","authors":[{"_id":"692eca62f11e323ac6f94d25","name":"AmirMohammad Shahrezaei (AmShZ)"}],"statementOverrides":"$undefined","createdAt":"2026-09-05T23:10:42.155Z","updatedAt":"2026-09-06T02:58:45.624Z"}],"contestId":"6a9663e11c611662a15b197b","contestUrlId":"22","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}]]}]

AFour Pieces, One Sheet	500	59/68
BOpposite Workflows	1000	42/49
CPrefix Painting	1500	31/32
DMoving the Sand	2000	26/28
EAge Reports	2500	9/16
FShortest Wiring	3000	7/10