Both

hm, don't know. What the rest thinks? Anyway you can try it later with virtual participation.

Yes, thanks

For problem D, I remember having done a problem very similar to this problem using Stirling numbers of the second kind in some Div2 contest (by considering the generating function).

EDIT: apparently it was an Educational Round (the relevant comment is here: https://codeforces.net/blog/entry/72268#comment-565745)

The number of segments is equal to the number of $$$i$$$ such that $$$a[i] \neq a[i + 1]$$$ plus 1. Then use linearity of expectation to count it. Between two numbers in the array there will be $$$2^k-1$$$ new numbers. And if at least one of $$$a[i]$$$ and $$$a[i + 1]$$$ is random, the probability of them being different is $$$\frac{x - 1}{x}$$$, the numbers of elements in the resulting array is $$$n + (2^k-1)*(n-1)$$$, so the answer is $$$\frac{x - 1}{x}(n + (2^k-1)*(n-1) - 1) + 1$$$. And none of $$$a[i]$$$ and $$$a[i + 1]$$$ is random only in case of $$$k=0$$$, but then you just count segments.

If you don't run the algorithm at all, then it's easy to find the number of distinct elements.

If you run it $$$k > 0$$$ times, consider the expected value of the number of segments when you add a number between two equal elements and two unequal elements. If you add it between two equal elements, the number of segments gets incremented by $$$2$$$ with probability $$$1 - 1/x$$$ and by $$$0$$$ with probability $$$1/x$$$. If you add it between two unequal elements, the number of segments gets incremented by $$$1$$$ with probability $$$2/x$$$, and by $$$2$$$ with probability $$$1 - 2/x$$$ (here we increment by 1 and 2 instead of 0 and 1, since we need to count transitions in the original array as well). So the contribution to the expected value is $$$2 - 2/x$$$ in either case, and the initial value is $$$1$$$.

So when you do this operation on an array of length $$$t$$$, the expected value becomes $$$1 + (t - 1)(2 - 2/x)$$$, and the length becomes $$$2t - 1$$$, i.e., if the final length is $$$w$$$, then the expected value is $$$1 + (w - 1)(1 - 1/x)$$$.

The final array has $$$2^k (n - 1) + 1$$$ elements, so the expected number of segments is $$$2^k (n - 1) (x - 1) / x + 1$$$.

The editorial link was in the Russian version of the blog.

Consider what happens with different values of $$$m$$$.

If $$$m = 2$$$, $$$a_i^i \equiv i \pmod 2$$$, so the answer is the sum of remainders mod 2 in any case.

If $$$m = 3$$$, $$$a_i^3 \equiv a_i \pmod 3$$$ for all $$$i$$$, so depending on whether the final position is odd or even, we get $$$a_i \pmod 3$$$ or $$$a_i^2 \pmod 3$$$ as its contribution to the sum. Note that $$$0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 1$$$, and $$$0^1 \equiv 0, 1^1 \equiv 1, 2^1 \equiv 2$$$ modulo $$$3$$$. So a greedy algorithm that assigns as many numbers that are $$$2 \pmod 3$$$ to the odd positions works.

If $$$m = 4$$$, then a similar congruence holds (but with a catch). The only other thing is when there are elements $$$a_i \equiv 2 \pmod 4$$$. We claim that if such an element exists, it suffices to put it in the first position. If we put something else in the beginning, then the difference can only remain the same (in case we swap it with a $$$3$$$ which was at an odd position) or decrease. So once we do this, the contribution of $$$0, 2$$$ to any place is $$$0$$$, that of $$$1$$$ is $$$1$$$, and that of $$$3$$$ is $$$1$$$ if it is at an even position and $$$3$$$ if it is at an odd position. Then a similar greedy approach as in the previous part works.

Yes. Sorry I wanted to say the order a1, a(n/2), a2 is not correct

I found a test case where your solution might fail. What's your answer for 4 1 2 2 3?

It seems to be impossible in non-private gym, only for those who solved the problem. What problm you are interested in? I can share my code though I am not sure that it is nice.

You meant problem D? I don't know how I just asked if someone knows;)

0^0=1 multiplied by 1/2

Problem C. Find the order
Sort the array. Then if order a[n/2] , an , a[n/2]−1 , an−1 , ..., a1 , a[n/2]−1 is correct then answer exists else it does not exist. Proof: if n is even then we should not have any element which occurence in array is more than half in other case we will have two adjacent equal elements. Iа we don’t then this order is correct. If n is odd then we can have only minimum with occurences more than half by 1(this minimum should stand on odd positions otherwise we will have two equal elements equal to each other or if it is not minimum then it will arround minimum). Notice that order a[n/2] , a1 , a[n/2+1] ... is not always correct, see 112.