Hi everyone! I would like to share a contest from problems I suggested in some programming school. These problems are by my own and some by Mosyagin. Is starts on this Wednesday at 18:00 Moscow time (see your timezone https://www.timeanddate.com/worldclock/fixedtime.html?day=24&month=2&year=2021&hour=18&min=0&sec=0&p1=166). You will be given 8-9 problems. I think they are educational a bit(but may be not all). I would be glad if you will participate and give me some feedback. Don't be too strict anyway it's one of my first such experience though I always wanted to make a contest. You can find contest in gym with name Kaliningrad Krosh Contest 1. It's duration 3 hours, statements will be on Russian and English.

Tutorial of 8 of 10 problems(except E and J): https://drive.google.com/file/d/1i_H_OFlPyx4uAtzD4r6PxRxI2bEXs76V/view?usp=sharing

Auto comment: topic has been translated by AleksanderBalobanov (original revision, translated revision, compare)Are the contest for a team or for individual participants?

Both

is it possible to change contest time? asking this because after one hour of the start of this contest codechef div3 also starts.

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

Will you upload the editorial after the contest?

Yes, It's ready except one of problems.

Thanks:)

Except two because I added one more problem

In problem C,isn't this statement in the problem self-contradictory:

You should determine is it possible to reorder it's elements in such a way that condition a1a3a5...a1a3a5... is true. In other words, first element should be strictly greater than the second, the second element should be strictly less than the third etc.__ First element a1 is actually less than a2 in the first line whereas in the second line it says first element (i.e. a1) should be strictly greater than the second. Or am I getting it wrong?UPD: Problem statement has been corrected now.Yes, thanks

Interesting problems! Is there an editorial upcoming?

Yeah, except two problems.

Tutorial is slightly brief so ask quesions! Was the problem D googlable?)

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.com/blog/entry/72268#comment-565745)

How to solve E?

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$$$.

How to solve C and D? Especially, D??

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

Alrighty! Thanks a lot! :)

Auto comment: topic has been updated by AleksanderBalobanov (previous revision, new revision, compare).Can someone please explain how to solve J?

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.

Good analysis. Thanks a lot!

The editorial for C says 'Notice that order a[n/2], a1, a[n/2+1] ... is not always correct, see 112.' What is 112?

UPD: I think it is the test 3 1 1 2 ?

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

My ordering for C was A[0], A[k], A[1], A[k + 1], A[2], ..., A where k is (n+1)/2 in 0-based indexing, Can you tell me why this is incorrect? This fails on pretest 10.

Example : Ordering for an array of length 5 would be A[1], A[4], A[2], A[5], A[3], here in 1-based indexing.

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

Are you getting correct answer for

4

1 2 2 3 ?

Using your approach you should get -1, but answer exists and is equal to 2 3 1 2

Thanks, you are correct

He meant 4 is the number of elements.

By the way, I don't know why it is that submissions to some of the problems are visible while others are not.

Following this logic you mentioned: Ordering for an array of length 5 would be A[1], A[4], A[2], A[5], A[3], here in 1-based indexing.

another answer can be : 1 4 2 3 2

Thanks, then I made incorrect example. n = 4, a = [9, 6, 8, 8] is the 10-th testcase

Can you please make the codes visible?

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.

Problem I

https://pastebin.com/wDS3bRUM