School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Solutions for School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules) (contest 48). 6/8 problems verified against sample I/O. Difficulty range: 900-2800.
School Personal Contest #3 (Winter Computer School 2010/11) - Codeforces Beta Round 45 (ACM-ICPC Rules)
Type: Beta | Problems: 8 | Verified: 6/8 | Rating range: 900-2800 | Time: 15m 12s
| Problem | Name | Rating | Tags | Solve Time | Verified |
|---|---|---|---|---|---|
| A | Rock-paper-scissors | 900 | implementation, schedules | 1m 31s | ✓ |
| B | Land Lot | 1200 | brute-force, implementation | 1m 47s | ✓ |
| C | The Race | 1800 | math | 1m 54s | ✓ |
| D | Permutations | 1500 | greedy | 2m 3s | ✗ |
| E | Ivan the Fool VS Gorynych the Dragon | 2100 | dp, games, graphs | 2m 21s | ✓ |
| F | Snow sellers | 2800 | greedy, sortings | 1m 27s | ✓ |
| G | Galaxy Union | 2700 | dp, trees, two-pointers | 2m 23s | ✓ |
| H | Black and White | 2800 | constructive-algorithms | 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.