Thanks for participating in the round, we hope you liked the problems!

**Solve count predictions (official div. 2)**

Handle | A | B | C | D | E1 | E2 | F |
---|---|---|---|---|---|---|---|

Vladithur | 16K | 8K | 3K | 900 | 500 | 50 | 4 |

_dlbm17 | 14K | 9K | 5K | 500 | ? | ? | ? |

thanhchauns2 | 14K | 8K | 2K | 1K | 500 | ? | ? |

QuangBuiCP | 14K | 7K | 2K | 1K | 500 | 24 | 5 |

welleyth | 16K | 10K | 4K | 1.5K | 600 | 130 | 2 |

Kon567889 | 14K | 10K | 5K | 2K | ? | ? | 5 |

**Hint**

The smallest possible sum is $$$1 + 2 + \ldots + k$$$.

**Tutorial**

Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$ for $$$n \le 10^5$$$.

**Hints**

**Hint 1**

In 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$$$.

**Tutorial**

Bonus: try to prove the solution without the editorial!

**Hints**

**Hint 1**

The operation only decreases numbers.

**Hint 2**

An array is sorted if there is no index $$$i$$$ such that $$$a_i > a_{i + 1}$$$.

**Hint 3**

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}$$$?

**Tutorial**

Bonus: solve for when $$$a_i$$$ can also be negative.

**Hints**

**Hint 1**

$$$\operatorname{d}(u; v) \le 2 \cdot \min(a_1 \ldots a_n)$$$

**Hint 2**

*diameter* $$$\le 2 \cdot \min(a_1 \ldots a_n)$$$

**Hint 3**

*diameter* $$$\le \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$$$

**Hint 4**

Binary search on the answer or do a clever greedy.

**Tutorial**

Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$.

1712E2 - LCM Sum (hard version)

**Hints**

**Hint 1**

Count 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 3**

A 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 5**

For every $$$k$$$, iterate over all pairs of divisors of $$$2 \cdot k$$$.

**Hint 6**

Think of the "bad" triplets as of segments $$$[i; k]$$$ with some weight.

**Hint 7**

Solve in offline.

**Tutorial**

Bonus: solve the problem in $$$\mathcal{O}((n + t) \log n)$$$ or better.

**Hints**

**Hint 1**

Let $$$f_v$$$ be the distance to the closest vertex $$$\in L$$$ to $$$v$$$. You can calculate it for every vertex in $$$O(n)$$$.

**Hint 2**

The distance in the new graph $$$\operatorname{d'}(u, v)$$$ is equal to $$$\min(\operatorname{d}(u, v), f_u + f_v + x)$$$

**Hint 3**

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$$$.

**Hint 4**

Think small-to-large merging.

**Hint 5**

Maintain the largest value of $$$depth_v$$$ over all $$$v$$$ with $$$f_v = i$$$ for all needed $$$i$$$.

**Hint 6**

In this problem, small-to-large merging works in $$$O(n)$$$.

**Hint 7**

The diameter is $$$\le n$$$. So you can increase it by $$$1$$$ at most $$$n$$$ times.

**Tutorial**

Bonus: solve for $$$n, q \le 10^6$$$.

**Don't forget to rate the problems!**

**Problem Feedback**

PS: Solution codes probably will be added later.

**UPD: explanations of the references:**

**Click here**

Hope you liked them!

**A**

The quote is just a modification of the original title of KonoSuba.

**B**

This is just something I invented, no reference here. Hope you liked the short poem!

**C**

The quote is the meme "people die when they are killed" in the Fate series, changed to fit the programming context. And the title is just "Fate Zero" changed to "Sort Zero".

**D**

"Do you have a wish?" is a recurring phrase in the LN series HakoMari, referring to the wish granting "boxes". The title is just "Empty Box" changed to "Empty Graph". Also, "O_o" is a reference to one of the main characters, "O".

**E**

The quote can probably be traced to many origins, but I personally modified the quote "We are legion, for we are many" from the series 86. There were also a lot of 6's and 8's in the sample, which might have helped you guess.

**F**

I didn't really think about this one, just modified a quote from Vivy a bit.