Yandex's blog

Yandex.Algorithm makes a comeback!
By Yandex, history, 4 years ago, translation, In English

Hi all,

We are pleased to announce that Yandex is once again including Yandex.Algorithm as part of the programming championship. The Algorithm track is a great opportunity to solve interesting problems, compete with participants from around the globe, and win cash prizes. This year's championship will be held completely online.

Schedule:

  • The trial stage starts on September 21 at 12:00 and ends on October 18 at 23:59

  • The qualifying round starts on October 19 at 12:00 and ends on October 25 at 23:59. It will be organized as a virtual contest. Participants will get six tasks, with 120 minutes total to solve them

  • The final round will be held on November 7. The time will be announced later. The final round will include participants who earned at least five points in the qualifying round.

The Algorithm tasks are available in English and Russian.

Prizes:

  • 1st place: 300,000 rubles

  • 2nd place: 150,000 rubles

  • 3rd place: 100,000 rubles

Registration is open until the end of the qualifying round. To learn more and register, go to the site: https://yandex.com/cup/algorithm/

UPD:

Algorithm 2020 final is over! Thank you all for participating!

More information is available at the Chmel_Tolstiy comment

See you at the next competitions!

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

Comments Comments (62)
| Write comment?
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

what about t-shirts?

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

    There won't be t-shirts this year. I know your sadness

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If I start qualification round virtual contest now, will I write it for 2 hours or till 26 october for 7 days?

→ Reply
»
4 years ago, # |
  Vote: I like it +48 Vote: I do not like it

Bump, 1 day of qualifying round is left.

I found in rules that 5 points are enough to qualify but will I see the number of points assigned to each problem? The rules just say that there might be groups of tests, each worth 1-5 points.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Yes, the number of points is stated in the problem statement.

    → Reply
»
4 years ago, # |
  Vote: I like it +36 Vote: I do not like it

What happens if in a certain track less than 3 people get score required to advance to the finals? Will the 3rd place prize be divided among the ones who advance? Or do organizers have an option of lowering the cutoff?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are we allowed to discuss the problems from the qualification round here now?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did people solve A. Reconstructing the alphabet and D. A reliable counter?

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

    D: let's maintain two multisets, first, contianing first k elements and second containing others. Let s be sum of first. Then one iteration is to:

    • delete first element in first;
    • insert s into first if s < second;
    • insert s into second and move smallest element from second to first if s >= second;
    • update s.

    $$$O((r + n) \log n)$$$

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

      :( I didn't expect D to have such a trivial solution so I implemented annoying $$$O(N)$$$ solution.

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

        What is the $$$O(n)$$$ solution you are talking about?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          It basically involved storing the first K numbers and other numbers with 2 deques each. In a merge sort like fashion we can perform each update in $$$O(1)$$$ while still maintaining the relative order. I've attached my ugly code as it might make more more sense (the code itself is $$$O(n\log n)$$$ because I was too lazy to write a merge code and instead of just sorting.

          Code
          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow this was pretty trivial :/ thank you!

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    For A, I wrote $$$T_5$$$ down, ABACABADABACABAEABACABADABACABA, and tried to find some useful pattern. After some time I realized that all odd positions have 'A'. With this, I can test if all even or odd positions are the same and map it to 'A'.

    Then I tried to erase all 'A' from $$$T_5$$$ and I got BCBDBCBEBCBDBCB where the structure is exactly $$$T_4$$$ so we can just repeatedly do the same. After every step, I erase half of the string(either all odd positions or all even positions) so it is $$$O(n\log n)$$$. It looks like it can be done in $$$O(n)$$$, though.

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

      Neat! Thanks.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Since you erase half of the string in each step, it's $$$O(N)$$$.

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

    i used dynamic segment tree.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Do you mean that the leaves are the numbers and you store the number of times they appeared so far? And an intermediate node contains the sum of the numbers in that range?

      → Reply
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

How to solve F?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where can you see the problems after the round ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an editorial for this contest ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please announce time of final round.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    I received an email with the following:

    Onward to the finals, which start November 7 at 12:00 (UTC+3). The competition will last 3 hours.

    I assume you are talking about the Algorithm track.

    → Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think that https://clist.by/ has incorrect time and date. If I understand the email correctly, this is correct time: https://www.timeanddate.com/worldclock/fixedtime.html?msg=Yandex+Algo+Finals&iso=20201107T12&p1=166&ah=3

Please confirm that you'll be taking part in your personal account.

I just see X below algo finals there. Nothing is interactive, I can't click anything.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I still wasn't able to reach any organizer. I got enough points in quals and even got an e-mail "Congratulations! You are in the Yandex Cup 2020 final" and yet I see only this in my profile:

Please help ;__;

EDIT: thanks to Chmel_Tolstiy for help, I'm added to finals now.

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

    Lmao one less guy to beat. Git gud at computers.

    Jk, I had a button under "confirmation" and when I clicked it a second button appeared under "final". It leads to a Yandex.Contest page. Maybe you blocked a script or something.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    I'm checking this issue

    → Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I'm qualified, I click on the contest link from logged in area, https://contest.yandex.ru/yacup/contest/21825/enter and it says "Internal server error"

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve A Need more coffee?

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

    binary search over derivate

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    To expand on Errichto's idea: if you give one person $$$x_1$$$ coffee and another one $$$x_2$$$ coffee, and their derivatives at those points are not equal, that means that you could give someone a little more and someone a little less and improve your answer. Therefore, an ideal case is to give everyone an amount such that their derivatives are the same.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can also do it without binsearch and with sort by $$$B$$$ as the only log-operation (maybe it can be eliminated too, not sure).

    Let's take out the constant sum of $$$C$$$, ignore $$$B \le 0$$$ and sort all other functions $$$(B-Ax)x$$$. All functions with $$$x \neq 0$$$ must have equal derivatives $$$K$$$ and all functions with $$$x = 0$$$ must have derivatives $$$B \lt K$$$, since if that isn't satisfied, we can always find a pair of functions and move $$$\mathrm{d}x$$$ coffee from the one with the smaller derivative $$$d_1$$$ to the one with the larger derivative $$$d_2$$$, gaining value $$$(d_2-d_1)\mathrm{d}x$$$. All the constraints I mentioned ensure that this is a valid move. It's important that the derivative of each function nicely decreases from $$$B$$$ to $$$0$$$.

    Let's pick some function + all those with greater/equal $$$B$$$ in sorted order. Then for each function, $$$B-2Ax = K$$$ ($$$\le B$$$ of our function) and the amount of coffee is $$$\sum x = \sum (B-K)/2A = \sum B/2A - K \sum 1/2A \le S$$$, which gives a min-formula for the optimal $$$K$$$. Now the answer is the max of answer so far and $$$\sum (B-Ax)x = \sum (B+K)(B-K)/4A = \ldots$$$. All sums are only over selected functions and can be computed nicely.

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

35th place despite being nearly asleep for much of the contest (10AM on Saturday smh). Not bad.

Interesting problems. E was kinda misplaced, counting pairs with $$$a+c=2b$$$ is obvious convolution and the extra step with $$$a < c$$$ is also pretty well-known d&c; I don't see what partial solutions the second subtask offered.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I don't see what partial solutions the second subtask offered.

    You can use bitmasks to write fast $$$O(n^2)$$$ solution.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      $$$O(N^2)$$$ for $$$N=5\cdot10^5$$$? Would anyone even risk wasting time on that? It's on the edge even for the huge TL.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        People who don't know FFT would. This is how we found out about this alternative approach. I was surprised too that it passes within half of time limit.

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

        It takes a 1-2 minutes to write simple bitset solution for the first subtask. But I couldn't pass the second subtask using STL bitsets.

        I was curious so I wrote my own bitset, after some constant optimizations squeezed it to ~7 seconds (given that I'm pretty bad at optimizing code). I think if one has prewritten bitsets and no FFT they may try to attempt $$$O(n^2)$$$ solution without any huge risks.

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

          Can you please share your std::bitset solution?
          I've also implemented it in couple of minutes, but got TL. I'm sure I'm too stupid, but don't know where

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 3   Vote: I like it +5 Vote: I do not like it

            Mb you didn't use right pragmas? Not sure which instruction sets are actually helpful I just copypasted those magic words from somewhere.

            Spoiler
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you so much, your are right, I forgot about pragmas. Got 8.984s on 32nd test without modification of my code :) It's stange I didn't get that I can use bitsets of length N / 2, not N: but even with this constant optimization TL without pragmas... Shame on me

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

          I just plugged one of my SSDs into an external enclosure and pulled out some old FFT implementation. Also an option is putting all your solved problems in one place and doing grep -r . -e ' convolution\('. Gotta completely miss the idea that convolution can be used since fast implementations are everywhere.

          And as our purple friend below shows, it can really be risky if you don't have ingrained constant optimisations.

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    can you elaborate on what convolution is please? (i spent the entire 3hs to come up with some kind of tree ds for E and now i see "obvious"). I'd be super grateful

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Consider a simpler version of the problem, where you want to count the number of $$$abc$$$ or $$$cba$$$. Then, for $$$b$$$ at position $$$k$$$ you want to count the number of pairs of positions $$$(i,j)$$$ such that $$$i+j=2k$$$ and $$$s_i=a/c, s_j=c/a$$$.

      Consider polynomials $$$p$$$ and $$$q$$$, where $$$p_i=1$$$ iff $$$s_i=a$$$ and $$$q_i=1$$$ iff $$$s_i=c$$$. In $$$pq$$$ the coefficient at $$$2k$$$ is exactly what you are looking for. So, you can create $$$p,q$$$ and multiply them with FFT.

      In order to count only $$$abc$$$, you can use divide and conquer approach. Split the string in two halves, count the number of triples where $$$a$$$ is in the first and $$$c$$$ is in the second half with the described approach, and solve recursively for both halves.

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

        If I'm not mistaken, convolution with FFT can be done in $$$O(N\log{}N)$$$. Does that mean that the complexity of the divide and conquer + FFT solution will be $$$O(N\log^2{}N)$$$?

        → Reply
»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Thank you all for participating! We did the best to fix some issues and to prepare good problems.

https://contest.yandex.ru/contest/22052/ -- one can register to look at problems or to upsolve. Hope to add both rounds into gym shortly.

Congrats to winners ksun48, Um_nik and voidmax

Special thanks to tourist for great performance (there only three persons in Yandex Cup who has already been a winner twice). You are the champion in our hearts and minds ;)

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

    Will there be an editorial ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Sorry, we have not prepared it yet. We'll publish it in some time on cup's page. Now community can help you I think.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Thanks for the great contest!

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +20 Vote: I do not like it

    91 seconds of penalty time :(

    I liked the tasks though, thanks

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +51 Vote: I do not like it

    The problems were great but please don't change the rules during the contest. Some people could have waited with submitting the next problem till 2:00 for frozen standings. And maybe there should have been an announcement that tourist doesn't fight for prizes, because this might change strategy for people in the top. That being said, none of that affected me because I didn't do that well :D

    btw. here are highlights of my screencast (10 minutes with commentary): https://youtu.be/ifsVDBOg39E

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +60 Vote: I do not like it

So here's my proof of a key part of full D: the only cases where the optimal string contains "ab**e" are:

  • $$$e = 1$$$ is the end of the string
  • "ab" contains at most 2 non-zero digits

Step 1: $$$e = 1$$$, not the end of the string: Let's just concatenate and "ab1" is better than "ab". From now on, let's assume $$$e \ge 2$$$. Our alternatives to "ab**e" are "a**b**e", "a**be", "abe" and splitting "a" or "b".

Step 2: When is splitting into "a**b**e" better? Obviously not when $$$a$$$ or $$$b$$$ is at most $$$1$$$, so let's denote the number of digits of $$$b \ge 2$$$ by $$$k$$$ ($$$10^{k-1} \le b \lt 10^k$$$) and prove by contradiction that $$$k \ge 2$$$ isn't allowed.

  • The loosest possible constraint is $$$((a+1) \cdot 10^k)^e \gt (a\cdot 10^k + b)^e \gt a^{b^e} \ge a^{10^{(k-1)e}}$$$. If this doesn't hold, we want to split regardless of $$$b$$$.
  • We're looking for $$$(a+1)^e \cdot 10^e \gt a^{10^{(k-1)e}} / 10^{(k-1)e} = f(10^{(k-1)e})$$$.
  • The derivative of $$$f(x) = a^x / x$$$ is $$$f(x)(\ln a - 1/x) \gt 0$$$ for $$$a,x \ge 2$$$.
  • Since $$$a \ge 2$$$ is assumed, the only case we need to consider is $$$k = 2$$$. If we increase $$$k$$$ any more, then the right side of the inequality increases and the left stays constant, so if it didn't hold for $$$k = 2$$$, that won't change for any greater $$$k$$$.
  • We're looking for $$$(a+1)^e \cdot 100^e \gt a^{10^e}$$$ with $$$e \ge 2$$$. Since $$$a+1 \lt a^2$$$ and $$$100 \lt a^7$$$, it implies $$$a^{9e} \gt a^{10^e}$$$.
  • It's easy prove that $$$9e \lt 10^e$$$, so this is impossible. Splitting just makes the exponent of "a" too massive.

Step 3: Notice that even if "b" is at most $$$9$$$, there can't be a way to split "ab" where "b" would be larger. Since "a" starts with a non-zero digit, let's look at remaining cases for "ab":

  • if there are at least $$$4$$$ non-zero digits in "ab", we can always find "b" that starts with the second-to-last of them, where both "a" and "b" are at least $$$11$$$
  • if there are $$$3$$$ non-zero digits and the first isn't "1", the same applies with $$$a \ge 2$$$ and $$$b \ge 11$$$
  • same if there are $$$3$$$ non-zero digits and "ab" starts with "10"
  • if the 3rd non-zero digit isn't at the end, $$$k \ge 2$$$ is the only option
  • "1d0...0g", where "d" and "g" are digits, is the only remaining case with $$$3$$$ non-zero digits
  • with only one non-zero digit there's no way to split anyway, so "d0...0" is an option
  • with $$$2$$$ non-zero digits, if each has a '0' right after, we can still split with $$$k \ge 2$$$
  • "d0...0g" is still an option
  • "1d0...0" is the last option, since if the non-zero digits are at the start, the first has to be $$$2$$$

Step 4: It's obvious that there's nothing to do if "ab" is "d0...0", so let's ignore this and just assign each '0' to the previous non-'0'. Intuitively, pumping value into the exponent instead of the base is good, so let's see if we can eliminate "1d0...0g" as an option.

  • We had $$$\left((10+d)\cdot10^{k+1}+g\right)^e$$$. Let's expand "e" into "h**r" and move "g" there, so that it becomes "gh**r". Now we have $$$\left((10+d)\cdot10^k\right)^{e^\prime}$$$. Let's add another variable $$$u = (10+d)\cdot10^k$$$ so we could say in a cleaner way that we're disproving $$$(10u+g)^e \gt u^{e^\prime}$$$.
  • A useful estimate: $$$(10u+g)^e / u^e = (10+g/u)^e \lt 11^e$$$.
  • Now let's estimate $$$e^\prime-e$$$. The string "gh" is at least $$$(g+1)h$$$, so $$$e^\prime \ge (g+1)^r h^r = (g+1)^r e \ge (g+1)e$$$; $$$e^\prime-e \gt ge$$$.
  • Since $$$u \ge 11$$$, we get $$$(10u+g)^e / u^e \lt 11^e \le u^{ge} \le u^{e^\prime-e}$$$. QED.

Step 5 (extra): Even for $$$e = 1$$$, splitting "ab" into "a**b" can be good. When is $$$a^b \lt a \cdot 10^k + b$$$?

  • Let's just get a rough bound: with $$$a \ge 2$$$, $$$a \cdot 10^k + b \lt (a+1) \cdot 10^k \lt a^2 \cdot 10^k \lt a^2 \cdot a^{4k} = a^{4k+2}$$$.
  • Then $$$b \lt 4k+2$$$ must hold. However, with $$$k \ge 2$$$, $$$b \ge 10^{k-1}$$$ and $$$10^{k-1} \ge 4k+2$$$, so $$$a = 1$$$ or $$$k = 1, b \le 5$$$.
  • If "ab" has at least $$$4$$$ non-zero digits, we can always pick $$$a, b \ge 10$$$, so that's not a case we want.
  • If "ab" has $$$3$$$ non-zero digits, we can pick the last (we just showed it can't have '0'-s after it) as "b". Then $$$a \ge 11$$$.
  • With $$$a \ge 11$$$, we have a better bound $$$10a+b \lt 11a \le a^2$$$, so $$$a^b \lt 2a^2$$$ only if $$$b \lt 2$$$.
  • If "ab" has $$$3$$$ non-zero digits, we can also pick the middle one as the start of "b". Then $$$a=1$$$ must hold, so "ab" must be "1d0...01".
  • Again, "d0...0" is obviously one case.
  • If "ab" has $$$2$$$ non-zero digits but '0' at the end, "1d0...0" is the only option.
  • If "ab" is "d0...0b" with at least one '0', it must be "d0...01" or "102" ($$$a = 10$$$, where we bruteforce $$$b \le 2$$$).
  • If "a" and "b" are digits $$$\ge 4$$$, a bruteforce check shows that "a**b" is always better. All other 2-digit numbers "ab" are still possible.

We just found out that each substring between exponents must be a 1-digit or 2-digit number, "102", "d0...01", "1d0...0", "d0...0" or "1d0...01". In addition, "1d0...01" (step 4) and "102" (proof is pretty short, you can finish it yourself) are only possible at the end.

→ Reply