School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
8 problems from School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules) (contest 48), difficulty 900-2800. 6/8 solutions verified against sample I/O.
School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Beta | 8 problems | 6/8 verified | Difficulty 900-2800 | 15m 12s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Rock-paper-scissors | 900 | implementation, schedules | 7,290 | 1m 31s | ✓ |
| B | Land Lot | 1200 | brute-force, implementation | 3,042 | 1m 47s | ✓ |
| C | The Race | 1800 | math | 856 | 1m 54s | ✓ |
| D | Permutations | 1500 | greedy | 2,995 | 2m 3s | |
| E | Ivan the Fool VS Gorynych the Dragon | 2100 | dp, games, graphs | 705 | 2m 21s | ✓ |
| F | Snow sellers | 2800 | greedy, sortings | 189 | 1m 27s | ✓ |
| G | Galaxy Union | 2700 | dp, trees, two-pointers | 324 | 2m 23s | ✓ |
| H | Black and White | 2800 | constructive-algorithms | 184 | 1m 46s |
CF 48B - Land Lot
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.
CF 48C - The Race
We are asked to predict the next petrol station where Vanya will stop, given the stations he has already visited.
CF 48D - Permutations
We are given a shuffled array that originally came from concatenating several permutations. Each permutation may have a different size. After concatenation, all numbers were mixed together, so the original grouping disappeared.
CF 48E - Ivan the Fool VS Gorynych the Dragon
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.
CF 48F - Snow sellers
We are asked to plan snow purchases over n days from m companies, ensuring we buy exactly W cubic meters each day. Each company produces a fixed daily amount w[i], but the cost of all snow from that company decreases linearly: c[i] on day 1, c[i] - a[i] on day 2, and so on.
CF 48G - Galaxy Union
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.
CF 48H - Black and White
We are asked to tile an rectangular floor with three types of 2x2 square tiles: black, white, and mixed tiles that have a black and a white section in a diagonal pattern.