#graph-matchings
CF 1773A - Amazing Trick
CF 1773A - Amazing Trick Rating: 1900 Tags: constructive algorithms, graph matchings, math, probabilities Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a permutation $a$ of size $n$, meaning every number from $1$ to $n$ appears exactly once. We are allowed to apply two permutations $q$ first and then $p$, so that the final position $i$ receives the value originally at position $p[q[i]]$. In other words,...
CF 1184B2 - The Doctor Meets Vader (Medium)
CF 1184B2 - The Doctor Meets Vader (Medium) Rating: 2200 Tags: flows, graph matchings, graphs, shortest paths, sortings Solve time: 2m 6s Verified: yes Solution Problem Understanding The galaxy is a small graph of planets connected by wormholes, where distance between planets is measured as the minimum number of edges in this graph. On top of this infrastructure, there are two kinds of actors: empire ships and rebel bases. Each...
CF 1510C - Cactus Not Enough
CF 1510C - Cactus Not Enough Rating: 2900 Tags: dfs and similar, graph matchings, graphs Solve time: 3m 19s Verified: no Solution Problem Understanding The problem gives us a cactus graph, which is a connected undirected graph where each edge belongs to at most one simple cycle. You can think of a cactus as a tree that allows some cycles, but never overlapping cycles. The input represents these cacti in...
CF 1510B - Button Lock
CF 1510B - Button Lock Rating: 2600 Tags: flows, graph matchings, graphs Solve time: 3m 7s Verified: yes Solution Problem Understanding The problem gives us a push-button combination lock with d buttons labeled from 0 to d-1 . Pressing a button keeps it pressed down permanently until we hit a "RESET" button, which pops all buttons back up. The lock opens instantly when a specific set of buttons is pressed...
CF 1765J - Hero to Zero
CF 1765J - Hero to Zero Rating: 2900 Tags: graph matchings, math Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given two arrays, a and b , both of length n . From these, we can build a matrix c where each entry c[i][j] is the absolute difference |a[i] - b[j]| . The goal is to reduce this matrix to a zero matrix, where every element is...
CF 1765A - Access Levels
CF 1765A - Access Levels Rating: 2400 Tags: bitmasks, dsu, flows, graph matchings Solve time: 2m 29s Verified: no Solution Problem Understanding Each document is described by which developers should be able to open it. So every column of the input matrix is a subset of developers: those rows where the value is one form the “approved set” for that document. We are allowed to compress this binary matrix into...
CF 1773D - Dominoes
CF 1773D - Dominoes Rating: 2600 Tags: combinatorics, flows, graph matchings, greedy Solve time: 1m 49s Verified: yes Solution Bug Diagnosis Now we finally see a real logical failure rather than a wrapper issue. The produced output: 2 3 2 2 2 2 is structurally consistent but numerically wrong, which tells us the implementation is computing something uniform per position instead of position-dependent reachability. The core mistake is in how...
CF 1906I - Contingency Plan 2
CF 1906I - Contingency Plan 2 Rating: 2900 Tags: graph matchings Solve time: 1m 39s Verified: yes Solution Problem Understanding The network is a tree, so initially there is exactly one simple path between every pair of computers. Each edge, when put into emergency mode, becomes a directed constraint: one endpoint must come before the other in a global ordering of all nodes. A permutation of all nodes is valid...
CF 2061H1 - Kevin and Stones (Easy Version)
CF 2061H1 - Kevin and Stones (Easy Version) Rating: 3500 Tags: flows, graph matchings, graphs Solve time: 1m 32s Verified: no Solution Problem Understanding Kevin has a graph where each vertex may initially contain a stone or be empty. He also has a target configuration indicating where the stones need to end up. On each move, Kevin can simultaneously move each stone from its current vertex to an adjacent vertex,...