Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)
3 problems from Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics) (contest 1322), difficulty 1300-3500. 1/3 solutions verified against sample I/O.
Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)
Div. 1 | 3 problems | 1/3 verified | Difficulty 1300-3500 | 12m 47s
| # | Problem | Rating | Tags | Accepted | Time | ✓ |
|---|---|---|---|---|---|---|
| A | Unusual Competitions | 1300 | greedy | 12,886 | 4m 47s | |
| C | Instant Noodles | 2300 | graphs, hashing, math | 2,703 | 2m 42s | |
| F | Assigning Fares | 3500 | dp, trees | 162 | 5m 18s | ✓ |
CF 1322F - Assigning Fares
We are given a tree with $n$ stations and $n-1$ tunnels, so between any two stations there is exactly one simple path. On this tree, we are also given $m$ special routes.
CF 1322A - Unusual Competitions
We are given a string consisting only of parentheses, and we are allowed to modify it using an operation that picks any contiguous segment and permutes its characters arbitrarily. The cost of such an operation equals the length of the chosen segment.
CF 1322C - Instant Noodles
Yes, the inequality $nu(n) le 2^{l(n) - lambda(n)}$ holds for all positive integers $n$. Consider an addition chain of minimal length $l(n)$ and let $lambda(n)$ be the length of a shortest chain consisting only of doubling steps.