#brute-force
CF 2222G - Statistics on Tree
CF 2222G - Statistics on Tree Rating: - Tags: binary search, brute force, dfs and similar, divide and conquer, graphs, trees Solve time: 6m 33s Verified: no Solution Problem Understanding We are given a tree. For a pair of vertices $(u,v)$, we remove every edge belonging to the unique simple path between them. After those edges are deleted, the tree breaks into several connected components. The value of the pair...
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 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 1949B - Charming Meals
CF 1949B - Charming Meals Rating: 1500 Tags: binary search, brute force, greedy, sortings Solve time: 1m 44s Verified: yes Solution Problem Understanding We have two arrays of size n . The array a contains the spiciness values of the appetizers, and the array b contains the spiciness values of the main dishes. Every appetizer must be paired with exactly one main dish, and every main dish must be used...
CF 1949E - Damage per Second
CF 1949E - Damage per Second Rating: 2900 Tags: brute force, math Solve time: 1m 7s Verified: no Solution Problem Understanding We are asked to distribute a fixed number of skill points between two attributes: damage per hit and hits per second, in order to minimize the total time to kill a sequence of monsters. Each monster has a health value $h_i$, and the time to kill it is determined...
CF 241F - Race
CF 241F - Race Rating: 2300 Tags: brute force, implementation Solve time: 2m 26s Verified: yes Solution Problem Understanding The city is represented by a grid. Every cell is either a building, a street tile with a traversal cost from 1 to 9 , or a junction labeled by a lowercase letter. Movement rules are unusual. You can move only between adjacent cells that share an edge, but: moving from...
CF 38C - Blinds
CF 38C - Blinds Rating: 1400 Tags: brute force Solve time: 1m 7s Verified: yes Solution Problem Understanding We have a set of horizontal blind stripes of varying lengths, and our goal is to construct a rectangular blind for a window using these stripes. Each stripe can be cut into smaller pieces, but pieces cannot be shorter than a given minimum length, l . The final blind is built by...
CF 46A - Ball Game
CF 46A - Ball Game Rating: 800 Tags: brute force, implementation Solve time: 1m 23s Verified: yes Solution Problem Understanding The children stand in a circle numbered from 1 to n . Child 1 starts with the ball. The first throw moves the ball forward by 1 position, the second throw moves it forward by 2 positions, the third throw by 3 positions, and so on. After exactly n -...
CF 38B - Chess
CF 38B - Chess Rating: 1200 Tags: brute force, implementation, math Solve time: 2m Verified: no Solution Problem Understanding We are given the positions of two chess pieces on a standard 8 × 8 board, one rook and one knight. Their starting positions are guaranteed to be safe, meaning the rook does not attack the knight and the knight does not attack the rook. We must place one more knight...
CF 48B - Land Lot
CF 48B - Land Lot Rating: 1200 Tags: brute force, implementation Solve time: 1m 47s Verified: yes Solution Problem Understanding The garden is represented as an n × m grid. Each cell contains either 0 or 1 . A 1 means there is a tree in that square, while 0 means the square is empty. We want to place a rectangular house plot somewhere inside the grid. The rectangle must...