Skybytskyi.Nikita's blog

By Skybytskyi.Nikita, 6 weeks ago, In English

solutions on github, video on YouTube. Short text solutions:

A. Puzzle From the Future

Greedy: first optimize the length (no consecutive equal numbers), then the individual digits starting from the most significant ones. $$$O(t \cdot n)$$$ overall.

B. Different Divisors

The least prime divisor $$$p$$$ should be at least $$$d + 1$$$. Then the second prime divisor should be at least $$$p + 1$$$. Selecting the least prime number bigger than something is a binary search in the array of primes. The array of primes can be generated with a sieve. $$$O(\max d \log \log \max d + t)$$$ overall.

C. Array Destruction

Each operation should involve max because it can't be removed later. If we know the initial $$$x$$$ then the simulation of this process takes $$$O(n \log n)$$$ with std::multiset or $$$O(n)$$$ with some smart solution from neal. Because the initial value of $$$x$$$ also includes $$$\max_i a_i$$$, it remains to try all $$$n$$$ values of the form $$$a_j + \max_i a_i$$$. $$$O(n^2 \log n)$$$ overall. No $$$t$$$ because $$$n \mapsto n^2 \log n$$$ is convex, and we can apply Jensen.

D. Cleaning

Write $$$a_1 = x_1$$$, $$$a_i = x_i + x_{i - 1}$$$ for $$$i = 2, \dots, n$$$. We want $$$x_i \ge 0$$$ and $$$x_n = 0$$$. If we swap $$$a_i$$$ and $$$a_{i+1}$$$ then $$$x_i$$$ changes by $$$\Delta$$$, and $$$x_j$$$ changes by $$$\pm 2 \Delta$$$ where $$$\Delta = a_i - a_{i+1}$$$, and the sign depends on the parity of the position. We therefore can process the array in reverse, maintaining the suffix min of odd positions and even positions and checking several conditions. Note that we also need all negative $$$x_i$$$ to be on the suffix, because prefix does not change when swapping $$$a_i$$$ and $$$a_{i+1}$$$.

E. What Is It?

This is a somewhat tricky construction problem. I could not figure out the exact construction during the contest but had some close ideas, and fixed my solutions shortly after. The general idea is to maximize the number of long swaps (you'll get one swap of length $$$n - 1$$$, two swaps of length $$$n - 2$$$, two swaps of length $$$n - 3$$$, etc). It is also very convenient to construct the permutation in reverse.

  • Vote: I like it
  • +18
  • Vote: I do not like it