#dp
CF 2222A - A Wonderful Contest
CF 2222A - A Wonderful Contest Rating: - Tags: brute force, dp, math Solve time: 4m 29s Verified: no Solution Problem Understanding Each problem in the contest is worth at most 100 points. If a problem has $a_i$ subtasks, then every solved subtask contributes $$\frac{100}{a_i}$$ points, and $a_i$ is guaranteed to divide 100. This means every problem contributes one of the values $$0,\ \frac{100}{a_i},\ 2\cdot\frac{100}{a_i},\ \ldots,\ 100.$$ For a contestant,...
CF 2222C - Median Partition
CF 2222C - Median Partition Rating: - Tags: dp, math Solve time: 2m 36s Verified: no Solution Setup The simulator maintains a global simulated time variable $CLOCK$ and executes each MIX instruction by dispatching to a routine that models its effect on registers, memory, and timing. The I/O instructions considered here are restricted to devices $16$ and $18$. Device $16$ represents the read-card unit, and device $18$ represents the printer...
CF 1949A - Grove
CF 1949A - Grove Rating: 3300 Tags: brute force, dfs and similar, dp, geometry, probabilities Solve time: 2m 41s Verified: yes Solution Problem Understanding Every tree is planted at an integer lattice point. Around that point we place a disk of radius r , representing the root system. Two conditions must hold. The entire disk must stay inside the square lawn. Since the lawn is the square [0,n] × [0,n]...
CF 1949C - Annual Ants' Gathering
CF 1949C - Annual Ants' Gathering Rating: 1900 Tags: dfs and similar, dp, greedy, trees Solve time: 4m 48s Verified: yes Solution Problem Understanding Each vertex of the tree initially contains exactly one ant. A move chooses an edge $(u,v)$ and orders all ants currently gathered at $u$ to move to $v$. The ants obey only when the destination already contains at least as many ants as the source. If...
CF 48G - Galaxy Union
CF 48G - Galaxy Union Rating: 2700 Tags: dp, trees, two pointers Solve time: 2m 23s Verified: yes Solution Problem Understanding We are given an undirected weighted graph with exactly n vertices and n edges. Since a connected graph with n vertices and n edges contains exactly one cycle, the graph is a unicyclic graph, a tree with one extra edge. For every planet u , we must compute the...
CF 48E - Ivan the Fool VS Gorynych the Dragon
CF 48E - Ivan the Fool VS Gorynych the Dragon Rating: 2100 Tags: dp, games, graphs Solve time: 2m 21s Verified: yes Solution Problem Understanding The game state is completely described by two numbers: how many heads and how many tails the dragon currently has. From a state (h, t) Ivan may choose one of two move types. If he cuts i heads, where 1 ≤ i ≤ n and...
CF 38E - Let's Go Rolling!
CF 38E - Let's Go Rolling! Rating: 1800 Tags: dp, sortings Solve time: 1m 24s Verified: yes Solution Problem Understanding We are given n marbles on a one-dimensional axis, each with a position x[i] and a pin cost c[i] . You can stick a pin in some marbles, paying the associated cost, and unpinned marbles will roll left until they hit the nearest pinned marble. If a marble has no...
CF 38F - Smart Boy
CF 38F - Smart Boy Rating: 2100 Tags: dp, games, strings Solve time: 2m 49s Verified: no Solution Problem Understanding We start with an empty string. The first player picks any single letter that appears somewhere inside at least one dictionary word. After that, players alternately extend the current string by adding exactly one character either to the front or to the back. The restriction is the core of the...
CF 46E - Comb
CF 46E - Comb Rating: 1900 Tags: data structures, dp Solve time: 1m 52s Verified: yes Solution Problem Understanding Each row of the table contains integers, and from every row we must take a positive-length prefix. If we choose c[i] cells from row i , then the selected cells in that row are exactly the first c[i] entries. The total reward is the sum of all selected numbers. The restriction...
CF 38H - The Great Marathon
CF 38H - The Great Marathon Rating: 2400 Tags: dp Solve time: 2m 31s Verified: no Solution Problem Understanding We have a connected weighted graph of cities. Runner i starts from city i and finishes in some other city. The finish city is chosen independently for every runner, and several runners may share the same destination. Each runner travels along a shortest path, so their finishing time is exactly the...