How to do D?

Oof, and here I was thinking that Sqrt-Decomposition could work :3

This task has simple implementation.

Assume, we are looking at some element $$$x$$$ in the permutation. There are elements that are smaller that it — we will mark them as $$$-$$$, and elements, that are greater — we will mark it as $$$+$$$. So we have this picture: $$$[-+--+x++--+-]$$$.

Now, when the answer is greater than $$$3$$$? Well, if we have $$$[-x+]$$$ or $$$[+x-]$$$ or $$$[-+x]$$$ or $$$[+-x]$$$ or $$$[x-+]$$$ or $$$[x+-]$$$. When the answer is greater than $$$5$$$? If we have $$$[-+x-+]$$$ or $$$[+-x+-]$$$ or $$$[+-+-x]$$$ etc.

So, now we see, that we need to find the smallest segment, that has $$$--$$$ or $$$++$$$ at one of its ends. We can stand at $$$x$$$ and just move to some direction and calculate number of $$$-$$$ and $$$+$$$. Once these numbers are not equal, we found a candidate for answer for this direction. Notice, that answer can be in one of two forms: $$$[...x]$$$ and $$$[...x.]$$$, where $$$.$$$ is one element. But the second form can't be for first and last elements, so we need to "if" it.

Why can we just iterate, without any optimization? Well, I don't know. I first tried to create a bad test, and thought, that worst answer is $$$O(n \cdot \log{n})$$$. Then I whote a stress, which, if I understood correctly, showed even $$$O(n)$$$.

What was your approach to E? I backtracked $$$n=6$$$, found out that we cannot construct $$$2^6-1$$$, then gave up lol.

I can confirm that spam submitting with random condition on N without proving works

can you please explain me the solution to E. I can not understand the editorial.

Actually,neither of the topics is required. However,I do agree that A is harder than C，for i spend 80 minutes on A and only 30 minutes on C.

I never use digit dp in normal form because you can always fix the first smaller digit and then write dp without any restriction.

anyways this problem is much more easier check this code

The answer consists of 3 parts:

1. $$$P_1$$$ and $$$P_n$$$ $$$\implies$$$ just two such points, the sum bounded by $$$2n$$$.
2. $$$P_i$$$ being local max or min on segment $$$[P_{i - 1}, P_{i + 1}]$$$ $$$\implies$$$ answer for such points is $$$3$$$, so the sum is bounded by $$$3n$$$.
3. The remaining points $$$\implies$$$ the only non-trivial case.

Consider subsequence of all points falling under case (3). Let $$$P_a$$$ and $$$P_b$$$ be two such consecutive points. Then, it can be proved that answer for both of the points does not exceed $$$b - a + 3$$$. Consider e.g. case $$$P_a < P_b$$$. Since $$$P_b$$$ does not fall under case (2), we have either $$$P_{b-1} > P_b$$$, or $$$P_{b+1} > P_b$$$. Consider e.g. case $$$P_{b+1} > P_b$$$, then $$$P_a < P_b < P_{b+1}$$$. This implies that $$$P_a$$$ cannot be the median of both segments $$$[P_a, \dots, P_{b-1}]$$$ and $$$[P_a, \dots, P_{b+1}]$$$ simultaneously. So, one of these segments would give the answer for $$$P_a$$$. (If the segments have even length, you might add element $$$P_{a-1}$$$ to them to obtain segments of odd length).

So, the answer for all such $$$P_a$$$ does not exceed the doubled distance between the leftmost and the rightmost of them, plus a constant overhead for each pair of consecutive such points. In total this is bounded by $$$5n$$$.

Write a function which given a number K, let's you know how many numbers <= K exist which are Neq numbers. You can use digit dp for it.

Next, use binary search on this function to find the smallest number which gives K as the answer.

can confirm that stress test fixes this

what was your approach?

Congratulations! You've entered Hall of Fame!