### AleksanderBalobanov's blog

By AleksanderBalobanov, history, 3 days ago, translation,

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

• +81

 » 3 days ago, # |   0 Auto comment: topic has been translated by AleksanderBalobanov (original revision, translated revision, compare)
 » 37 hours ago, # |   +10 Are the contest for a team or for individual participants?
•  » » 36 hours ago, # ^ |   +11 Both
 » 37 hours ago, # |   -21 is it possible to change contest time? asking this because after one hour of the start of this contest codechef div3 also starts.
•  » » 36 hours ago, # ^ |   +2 hm, don't know. What the rest thinks? Anyway you can try it later with virtual participation.
•  » » » 35 hours ago, # ^ |   0 Will you upload the editorial after the contest?
•  » » » » 35 hours ago, # ^ |   +21 Yes, It's ready except one of problems.
•  » » » » » 35 hours ago, # ^ |   0 Thanks:)
•  » » » » » 31 hour(s) ago, # ^ |   0 Except two because I added one more problem
 » 34 hours ago, # | ← Rev. 2 →   0 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.
•  » » 32 hours ago, # ^ |   0 Yes, thanks
•  » » » 31 hour(s) ago, # ^ | ← Rev. 2 →   +8 Interesting problems! Is there an editorial upcoming?
•  » » » » 31 hour(s) ago, # ^ |   0 Yeah, except two problems.
 » 31 hour(s) ago, # |   0 Tutorial is slightly brief so ask quesions! Was the problem D googlable?)
•  » » 31 hour(s) ago, # ^ | ← Rev. 3 →   0 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)
 » 30 hours ago, # |   0 How to solve E?
•  » » 30 hours ago, # ^ | ← Rev. 2 →   +24 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.
•  » » 30 hours ago, # ^ |   +1 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$.
 » 29 hours ago, # |   0 How to solve C and D? Especially, D??
•  » » 29 hours ago, # ^ |   0 The editorial link was in the Russian version of the blog.
•  » » » 29 hours ago, # ^ |   0 Alrighty! Thanks a lot! :)
 » 29 hours ago, # |   0 Auto comment: topic has been updated by AleksanderBalobanov (previous revision, new revision, compare).
 » 29 hours ago, # |   0 Can someone please explain how to solve J?
•  » » 22 hours ago, # ^ |   +1 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.
•  » » » 17 hours ago, # ^ |   0 Good analysis. Thanks a lot!
 » 21 hour(s) ago, # | ← Rev. 2 →   0 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 ?
•  » » 20 hours ago, # ^ | ← Rev. 2 →   +1 Yes. Sorry I wanted to say the order a1, a(n/2), a2 is not correct
 » 21 hour(s) ago, # |   +1 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.
•  » » 20 hours ago, # ^ |   +1 I found a test case where your solution might fail. What's your answer for 4 1 2 2 3?
•  » » » 20 hours ago, # ^ | ← Rev. 2 →   0 5 4 1 2 2 3 1 3 2 4 2
•  » » » » 20 hours ago, # ^ | ← Rev. 2 →   +4 Are you getting correct answer for 41 2 2 3 ?Using your approach you should get -1, but answer exists and is equal to 2 3 1 2
•  » » » » » 19 hours ago, # ^ |   0 Thanks, you are correct
•  » » » » 20 hours ago, # ^ |   0 He meant 4 is the number of elements.
•  » » » » » 17 hours ago, # ^ |   0 By the way, I don't know why it is that submissions to some of the problems are visible while others are not.
•  » » » » 17 hours ago, # ^ |   0 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
•  » » » » » 16 hours ago, # ^ |   0 Thanks, then I made incorrect example. n = 4, a = [9, 6, 8, 8] is the 10-th testcase
 » 20 hours ago, # |   +5 Can you please make the codes visible?
•  » » 16 hours ago, # ^ |   0 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.
•  » » » 15 hours ago, # ^ |   0 Problem I
•  » » » » 13 hours ago, # ^ |   0