When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ABalobanov's blog

By ABalobanov, history, 3 years 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

Announcement of Krosh Kaliningrad Contest 1
  • Vote: I like it
  • +81
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Are the contest for a team or for individual participants?

»
3 years 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

»
3 years 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.

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

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

  • »
    »
    3 years 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)

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

How to solve E?

  • »
    »
    3 years 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.

  • »
    »
    3 years 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$$$.

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

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

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

Can someone please explain how to solve J?

  • »
    »
    3 years 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.

»
3 years 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 ?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
3 years 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.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can you please make the codes visible?

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

for Problem E, the tutorial said the formula can be calculated faster. who can tell me more about that skill? or show me the code, thanks.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry I meant problem D. I try to optimize it using segment tree but failed ╥﹏╥...

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe some of reds can tell is it possible to compute formula $$$f_k = \sum\limits_{i = 0}^k C_k^i f_i+1$$$ for all $$$1 \le k \le n$$$ faster than $$$O(n^2)$$$.

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

Screenshot-2022-09-02-162032

This above formula from problem D tutorial ,when we convert summation boundary from [0,inf] to [1,inf] we get 1/2 extra value , why this extra value is not (0^i/2^0)=0? Any help please.

  • »
    »
    19 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    0^0=1 multiplied by 1/2

    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you so much , I thought about that but as I know 0^0 is undefined which made me confused about the formula .

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i cannot use vpn in some reason so i cannot view tutorial on google.can you help me to send me the tutorial or solution to problem C?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.