Thanks for participating in the round, we hope you liked the problems!
Solve count predictions (official div. 2) 1712A - Wonderful Permutation
HintThe smallest possible sum is $$$1 + 2 + \ldots + k$$$.
Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$ for $$$n \le 10^5$$$.
1712B - Woeful Permutation
HintsHint 1In an optimal answer, for all $$$1 \le i \le n$$$, $$$\operatorname{lcm}(i, p_i) = i \cdot p_i$$$.
Hint 2$$$\operatorname{lcm}(x, x + 1) = x \cdot (x + 1)$$$.
Hint 3$$$\operatorname{lcm}(x, x + 1) + \operatorname{lcm}(x + 1, x) = x^2 + (x - 1)^2 - 1$$$.
Bonus: try to prove the solution without the editorial!
1712C - Sort Zero
HintsHint 1The operation only decreases numbers.
Hint 2An array is sorted if there is no index $$$i$$$ such that $$$a_i > a_{i + 1}$$$.
Hint 3Suppose there is an index $$$i$$$ such that $$$a_i > a_{i + 1}$$$. What operations do you need to perform to make $$$a_i \le a_{i + 1}$$$?
Bonus: solve for when $$$a_i$$$ can also be negative.
1712D - Empty Graph
HintsHint 1$$$\operatorname{d}(u; v) \le 2 \cdot \min(a_1 \ldots a_n)$$$
Hint 2diameter $$$\le 2 \cdot \min(a_1 \ldots a_n)$$$
Hint 3diameter $$$\le \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$$$
Hint 4Binary search on the answer or do a clever greedy.
Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$.
1712E2 - LCM Sum (hard version)
HintsHint 1Count the number of "bad" triplets such that $$$\operatorname{lcm}(i, j, k) < i + j + k$$$.
Hint 2$$$\operatorname{lcm}(i, j, k) \le 2 \cdot k$$$ in a bad triplet.
Hint 3A triplet is bad iff $$$\operatorname{lcm}(i, j, k) = k$$$ or ($$$\operatorname{lcm}(i, j, k) = 2 \cdot k$$$ and $$$i + j > k$$$).
Hint 4$$$\operatorname{lcm}(i, j, k) = x$$$ implies $$$i$$$, $$$j$$$, and $$$k$$$ are all divisors of $$$x$$$.
Hint 5For every $$$k$$$, iterate over all pairs of divisors of $$$2 \cdot k$$$.
Hint 6Think of the "bad" triplets as of segments $$$[i; k]$$$ with some weight.
Bonus: solve the problem in $$$\mathcal{O}((n + t) \log n)$$$ or better.
1712F - Triameter
HintsHint 1Let $$$f_v$$$ be the distance to the closest vertex $$$\in L$$$ to $$$v$$$. You can calculate it for every vertex in $$$O(n)$$$.
Hint 2The distance in the new graph $$$\operatorname{d'}(u, v)$$$ is equal to $$$\min(\operatorname{d}(u, v), f_u + f_v + x)$$$
Hint 3Suppose there is a vertex $$$v$$$ with $$$f_v > 0$$$. Then there is always a vertex $$$u$$$ in the subtree of $$$v$$$ such that $$$f_u < f_v$$$ and $$$depth_u$$$ > $$$depth_v$$$.
Hint 4Think small-to-large merging.
Hint 5Maintain the largest value of $$$depth_v$$$ over all $$$v$$$ with $$$f_v = i$$$ for all needed $$$i$$$.
Hint 6In this problem, small-to-large merging works in $$$O(n)$$$.
Hint 7The diameter is $$$\le n$$$. So you can increase it by $$$1$$$ at most $$$n$$$ times.
Bonus: solve for $$$n, q \le 10^6$$$.
Don't forget to rate the problems!
Problem FeedbackA - Good problem
- Mid problem
- Bad problem
B - Good problem
- Mid problem
- Bad problem
C - Good problem
- Mid problem
- Bad problem
D - Good problem
- Mid problem
- Bad problem
E1 - Good problem
- Mid problem
- Bad problem
E2 - Good problem
- Mid problem
- Bad problem
F - Good problem
- Mid problem
- Bad problem
PS: Solution codes probably will be added later.
PPS: I will post the explanations to the references a bit later, try to guess them if you haven't already!