Narrator: Alas, crazy_sea was wrong.

Probably you can not write checker in O(N) for the third?

2: Maybe it's because of the checker complexity.

I believe the checker for C is not easy when $$$N$$$ is large. (In fact, it's not obvious even for $$$O(N^2)$$$ time.)

My solution of C is $$$O(n^2)$$$.

Assume, the mex of the final set is $$$x$$$. In this case, all numbers less than $$$x$$$ are in set. The ones, that are not, have to be added. Assume, we added $$$y$$$ of such numbers.

Now, we have to add $$$k - y$$$ more numbers. These are numbers from $$$0$$$ to $$$x - 1$$$. We are counting number of sets, so we have to "find number of non-decreasing arrays of length $$$k - y$$$ with elements from $$$0$$$ to $$$x - 1$$$". Now, not easy combinatorial step: we have to put $$$x - 1$$$ stages into $$$k - y + 1$$$ positions. This is number of "combinations with repetitions": $$$C_R(k - y + 1, x - 1)$$$. Rewrite as usual combinations: $$$C_R(a, b) = C(a + b - 1, a)$$$.

For an $$$x$$$, define $$$q_x$$$ as the number such that $$$p_{q_x}=x$$$.

The minimum similarity has to be at least 1, as one can choose path $$$(x,q_x)$$$ to make it 1. So consider constructing a permutation that makes the answer 1.

Let's consider a leaf $$$x$$$. If this node makes a contribution of 1 to the final answer, than the final path must contain path $$$(x,q_x)$$$. As $$$x$$$ is a leaf, $$$x$$$ will be the first element in the LCS. Then we only need to ensure that there is no other same element after $$$q_x$$$. One simple way to do this is to make $$$q_x$$$ the leaf. Then we get the idea to shuffle the indexes of the leaves. It's not hard to prove that if we do this, any LCS with a leaf will have length of at most 1.

Then return to the original problem. Note that since leaves will not make any further contribution, we can simply delete them and do the same thing on the resulting tree again and again, until there's only 0/1 nodes left. Then we can do some trivial assignments and the whole process is finished. It can be proved that in this case, the answer is at most 1, which is obviously the best answer we can get.

can you provide failing test case

:) Видео недоступно Оно содержит материалы партнера SME. Он заблокировал ролик в вашей стране из-за нарушения авторских прав.

Did u find a test case on problem F where your code dosen t work, because i had WA on the same tests an was wondering where the mistake could be.

Hi, is there a name for dp code in D? Is it some kind of trick for powers of 2?

click