Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)
4 problems from Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated) (contest 1387), difficulty 2100-2900. 1/4 solutions verified against sample I/O.
Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated)
ICPC/IOI | 4 problems | 1/4 verified | Difficulty 2100-2900 | 17m 38s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Graph | 2100 | *special, binary-search, dfs-and-similar | 905 | 6m 59s | |
| B1 | Village (Minimum) | 2100 | *special, dp, greedy | 1,890 | 1m 47s | ✓ |
| B2 | Village (Maximum) | 2500 | *special, dfs-and-similar, trees | 1,276 | 7m 9s | |
| C | Viruses | 2900 | *special, dp, shortest-paths | 204 | 1m 43s |
CF 1387C - Viruses
We are given a system where each “gene” is an integer label, and every gene greater than 1 can expand into a sequence of genes according to a fixed mutation rule.
CF 1387B2 - Village (Maximum)
The village is a tree where each house is a node and each road is an edge of length one. Initially, every house has exactly one villager. We must reassign villagers so that every person moves to a different house, forming a permutation of nodes with no fixed points.
CF 1387A - Graph
We are given an undirected graph where every edge enforces a linear constraint between its endpoints. Each vertex must be assigned a real value, and every edge says exactly what the sum of its two endpoint values must be. Black edges force a sum of 1, red edges force a sum of 2.
CF 1387B1 - Village (Minimum)
We are given a village consisting of N houses connected by N-1 roads in a tree structure, so every house is reachable from any other via exactly one simple path. Each house initially has one villager. The villagers want to move so that no one remains in their original house.