Thanks for participating in the round, we hope you liked the problems!
| Handle | A | B | C | D | E1 | E2 | F |
|---|---|---|---|---|---|---|---|
| Vladithur | 16K | 8K | 3K | 900 | 500 | 50 | 4 |
| GlowCheese | 14K | 9K | 5K | 500 | ? | ? | ? |
| thanhchauns2 | 14K | 8K | 2K | 1K | 500 | ? | ? |
| QuangBuiCPP | 14K | 7K | 2K | 1K | 500 | 24 | 5 |
| welleyth | 16K | 10K | 4K | 1.5K | 600 | 130 | 2 |
The smallest possible sum is $$$1 + 2 + \ldots + k$$$.
Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$ for $$$n \le 10^5$$$.
In an optimal answer, for all $$$1 \le i \le n$$$, $$$\operatorname{lcm}(i, p_i) = i \cdot p_i$$$.
$$$\operatorname{lcm}(x, x + 1) = x \cdot (x + 1)$$$.
The operation only decreases numbers.
An array is sorted if there is no index $$$i$$$ such that $$$a_i > a_{i + 1}$$$.
Suppose 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.
$$$\operatorname{d}(u; v) \le 2 \cdot \min(a_1 \ldots a_n)$$$
diameter $$$\le 2 \cdot \min(a_1 \ldots a_n)$$$
diameter $$$\le \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$$$
Binary search on the answer or do a clever greedy.
Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$.
1712E2 - LCM Sum (hard version)
Count the number of "bad" triplets such that $$$\operatorname{lcm}(i, j, k) < i + j + k$$$.
$$$\operatorname{lcm}(i, j, k) \le 2 \cdot k$$$ in a bad triplet.
A triplet is bad iff $$$\operatorname{lcm}(i, j, k) = k$$$ or ($$$\operatorname{lcm}(i, j, k) = 2 \cdot k$$$ and $$$i + j > k$$$).
$$$\operatorname{lcm}(i, j, k) = x$$$ implies $$$i$$$, $$$j$$$, and $$$k$$$ are all divisors of $$$x$$$.
For every $$$k$$$, iterate over all pairs of divisors of $$$2 \cdot k$$$.
Think of the "bad" triplets as of segments $$$[i; k]$$$ with some weight.
Solve in offline.
Let $$$f_v$$$ be the distance to the closest vertex $$$\in L$$$ to $$$v$$$. You can calculate it for every vertex in $$$O(n)$$$.
The distance in the new graph $$$\operatorname{d'}(u, v)$$$ is equal to $$$\min(\operatorname{d}(u, v), f_u + f_v + x)$$$
Suppose 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$$$.
Think small-to-large merging.
Maintain the largest value of $$$depth_v$$$ over all $$$v$$$ with $$$f_v = i$$$ for all needed $$$i$$$.
In this problem, small-to-large merging works in $$$O(n)$$$.
The diameter is $$$\le n$$$. So you increase it by $$$1$$$ at most $$$n$$$ times.
Bonus: solve for $$$n, q \le 10^6$$$.
Don't forget to rate the problems!
PS: Solution codes probably will be added later
PPS: I will post the answers to the problem references a bit later! Try to guess them if you haven't already.
