AleksanderBalobanov's blog

By AleksanderBalobanov, history, 3 days ago, translation, In English

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

 
 
 
 
  • Vote: I like it
  • +81
  • Vote: I do not like it

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by AleksanderBalobanov (original revision, translated revision, compare)

»
37 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

Are the contest for a team or for individual participants?

»
37 hours ago, # |
  Vote: I like it -21 Vote: I do not like it

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

»
34 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    31 hour(s) ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

  • »
    »
    30 hours ago, # ^ |
    Rev. 2   Vote: I like it +24 Vote: I do not like it

    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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
29 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AleksanderBalobanov (previous revision, new revision, compare).

»
29 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain how to solve J?

  • »
    »
    22 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
21 hour(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

»
21 hour(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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, # |
  Vote: I like it +5 Vote: I do not like it

Can you please make the codes visible?