Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round)
3 problems from Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round) (contest 930), difficulty 1500-2900. 2/3 solutions verified against sample I/O.
Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round)
Div. 1 | 3 problems | 2/3 verified | Difficulty 1500-2900 | 4m 58s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Peculiar apple-tree | 1500 | dfs-and-similar, graphs, trees | 8,386 | 1m 10s | ✓ |
| C | Teodor is not a liar! | 1900 | data-structures, dp | 2,373 | 1m 52s | ✓ |
| E | Coins Exhibition | 2900 | data-structures, dp, math | 519 | 1m 56s |
CF 930E - Coins Exhibition
We are given a line of $k$ coins, each independently oriented either “obverse” (call it O) or “reverse” (call it R). A full configuration is simply a binary string of length $k$, but $k$ can be extremely large, so we cannot enumerate configurations.
CF 930C - Teodor is not a liar!
We are given a collection of integer segments on the line from 1 to m. Each segment contributes coverage to every integer point inside it, including endpoints. For every integer position x, we can compute how many segments cover it; call this value cnt(x).
CF 930A - Peculiar apple-tree
We are given a rooted tree with vertices numbered from 1 to n, where vertex 1 is the root. Every vertex i greater than 1 has exactly one parent p[i], and that parent always has a smaller index, which implicitly guarantees that the structure is a rooted tree without cycles and…