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
Hint 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)$$$.
1712C - Sort Zero
Hint 1The operation only decreases numbers.
Hint 2An array is sorted if there is no index $$$i$$$ such that $$$a_i \gt a_{i + 1}$$$.
Hint 3Suppose there is an index $$$i$$$ such that $$$a_i \gt 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
Hint 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 a clever greedy.
Bonus: solve for every $$$k$$$ from $$$1$$$ to $$$n$$$.
[problem:1712E]
1712F - Triameter
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 answers to the problem references a bit later! Try to guess them if you haven't already.
