Yandex's blog

By Yandex, history, 3 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 Algorithm tasks are available in English and Russian.

Prizes:

  • 1st place: 300,000 rubles

  • 2nd place: 250,000 rubles

  • 3rd place: 200,000 rubles

  • 4th place: 150,000 rubles

  • 5th place: 100,000 rubles

There will be T-shirts for top-30 in each categories.

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

I would like to thank the Algorithm team and personally the teamlead of category Chmel_Tolstiy

UPD: Qualification round is running now. It's two hours virtual contest and contestant should start the participation (you need a registration) till 23:59 3rd October (Moscow time, UTC+3).

UPD2: Qualification round is over. Thank you all for participating! Upsolving: https://contest.yandex.ru/contest/29878/enter/

UPD3: Qualification Round Editorial: https://codeforces.me/blog/entry/95880

UPD4: Algorithm 2021 is over! Congrats to winners ksun48, Radewoosh and Um_nik

Special thanks to tourist for great performance and first place out of competition.

Everyone can register to look at problems or to upsolve: https://contest.yandex.ru/contest/30228/enter/

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

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

Qualification round is running now. It's two hours virtual contest and contestant should start the participation till 23:59 3rd October (Moscow time, UTC+3).

Please read all problems we think that each quite interesting and some of them has subtasks.

Good luck and get some OK's.

======

Квалификационный раунд начался. В формате двухчасового виртуального соревнования участнику нужно стартовать свою сессию до 23:59 3 октября (время московское, UTC+3).

Мы рекомендуем почитать все задачи, т.к. считаем их достаточно интересными и в некоторые добавили подзадачи для разнообразия.

Удачи и побольше ОК.

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

One who is planning to participate in Qualification round should start in next about 36 hours. Good luck and have fun.

======

Желающие поучаствовать в квалификационном раунде должны стартовать в ближайшие 36 часов (на самом деле около того). Удачи и приятно проведите время, решая задачки!

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

why are there so few T-shirts?)

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

Is it possible to upsolve the problems of qualification round ?

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

Where can I find how to solve E

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

    Define $$$cnt_i$$$ — size of suffix consisting of only bits $$$1$$$

    One condition in good matrix is $$$cnt_i \ge cnt_ {i-1}$$$ and other bits in row $$$i$$$ consist of bits $$$0$$$, for $$$2 \le i \le n$$$

    Write DP $$$dp_{i,j,k}$$$ — minimum number of swaps if we make suffix $$$i$$$ of rows and suffix $$$j$$$ of columns in row $$$i$$$ consist of $$$1$$$ using $$$k$$$ bits from some positions.

    So transiions:

    • $$$dp[i][j][k]-(!a[i][j]) \Rightarrow dp[i][j + 1][k - 1]$$$

    • $$$dp[i][j][k]+(m - j + 1) - sf[i-1][j] \Rightarrow dp[i - 1][j][k + (m - j + 1)]$$$, where $$$sf_{i, j}$$$ is number of bits $$$1$$$ in row $$$i$$$ on suffix $$$j$$$

    Answer is $$$\min(dp_{i, j, sum})$$$ for all positions $$$(i; j)$$$ and sum bits of matrix $$$sum$$$

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

Final round is on the same day as Kickstart round G, hoping that the timings don't clash.

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

Hope we get an editorial for the problems this year :D

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

Please, open upsolving for backend qualification

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

How to solve problem D Matrix?

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

    Observation: if we fold the matrix along the horizontal axis, all numbers in the same column became equal. For example for the matrix:

    1  2  3  4
    5  6  7  8
    9  10 11 12
    13 14 15 16
    

    After folding

    14 16 18 20
    14 16 18 20
    

    And if we fold along the horizontal axis again (just assuming, this is forbidden in the problem statement for this example), every numbers will be doubled.

    And the same observation hold for the vertical axis. Also if there is a moment that we have already done 2 type of folds, all numbers will be the same.

    The second observation is that we must fold along the bigger side. Suppose that side is $$$m$$$. Then we will have: $$$n \le m$$$, so $$$n \le \sqrt{n \times m} \le \sqrt {2^{30}} = 2^{15}$$$, which is small enough. That means after the first time folding, we actually can just maintain the set of the numbers in every columns. That is, we calculate them, put them into a set. While $$$m > n$$$, we double these numbers again and again, put them into the set. And finally we can fold along the other axis and all number will become one. Now is just looping until $$$n = m = 1$$$ and double this number again and again.

    This algorithm works in $$$O(\min(n, m) \log n \log m)$$$

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

      Thanks, I see what i did wrong.

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

      Sigh, I just realized I misread the limitation as $$$n, m <= 2^{30}$$$ and spent an hour for an $$$O(\log n)$$$ solution...

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

    Problem have $$$O(log(n)+log(m))$$$ solution.

    We have some numbers after each fold. We need add count of this numbers to the answer and subtract count of numbers that have already been added since the previous fold. It can be proved that it is necessary to subtract only numbers $$$\le n\cdot m$$$ (numbers that intersect with the original sequence). It can be done in $$$O(1)$$$ with simple math formulas.

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

How to solve problem F?

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

    Let's formalise reversing a path as changing each edge $$$p \rightarrow v$$$ to $$$q \rightarrow v$$$ and vice versa iff $$$v$$$ isn't on the path. Now it's simple casework with some efficient tree stuff.

    • If one of the vertices $$$p,q$$$ coincides with $$$1,N$$$:
      • If the other two also coincide, the path doesn't change. W.l.o.g. now $$$p=1$$$.
      • If $$$q$$$ is on the path at distance $$$d$$$ from $$$1$$$, the length decreases by $$$d$$$ because the $$$q \rightarrow$$$ part of the path is changed to $$$1 \rightarrow$$$.
      • If $$$q$$$ isn't on the path, the length can only change if the edge $$$1 \rightarrow$$$ isn't between $$$1$$$ and $$$q$$$ — the whole path is extended and its length increases by the distance between $$$1$$$ and chosen $$$q$$$.
    • Otherwise, exactly one of the vertices $$$p,q$$$ (w.l.o.g. $$$p$$$) must be inside the path between $$$1,N$$$. If both are inside the path, its length doesn't change; if neither's inside, then all edges of the path don't change.
    • Let's say that we moved from $$$p$$$ towards $$$1$$$, again w.l.o.g., for $$$d_1$$$ edges, left the path before reaching $$$1$$$ and moved further for $$$d_2$$$ edges. Then the length of the path increases by $$$d_2-d_1$$$. (Only if $$$d_2 \gt 0$$$ and $$$d_1 \gt 0$$$, the length doesn't change otherwise.)
    • If we instead reached $$$1$$$ and moved further for $$$d_2$$$ edges, the same rule applies except $$$d_1$$$ is uniquely defined as the distance of $$$1$$$ and $$$p$$$.

    We can bruteforce all cases for one of $$$p,q$$$ coinciding with $$$1,N$$$. Now let's pick the vertex $$$v$$$ (possibly $$$1$$$ or $$$N$$$) where we left the path after moving from $$$p$$$ to $$$q$$$; we know $$$d_1$$$ and just need the sum of distances to all vertices in its (non-path) subtrees, with some multiplier since we have equivalent cases depending on which vertex is on the path and to which one we're moving. $$$O(N)$$$.

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

How to solve problem B?

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

    For mine, each tile can be rotated so for each tile I see the lexicographically minimum representation of it (there might be a better way). Like

    WW

    BB

    can be

    BW

    BW

    if it's rotated, but both tiles can be

    BB

    WW

    which is the lexicographically minimum of them (going clockwise starting at upper left) so I use that to represent the first 2 tiles. I mapped the first 2 tiles to the third tile, and the third tile is mapped to the number of tiles that can be rotated to it.

    Then, for each tile in the picture, I get how many tiles left I have that can be rotated to this tile, and if I run out of tiles that can be put there it's "No".

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

Isn't the next round schedule fixed yet?

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

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

Will the final be in the same virtual format ? E.g. we will have x hour window to do the contest any time between some fixed start and end date. Since https://clist.by shows that the final round will be 27 hours.

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

Is there a public live scoreboard of the final round available somewhere?

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

I admit I'm not too good at interactives but what is the point for the 90% winrate for problem B if tests are deterministic? Is it just a joke or does it actually matter for you to rng and hope the grader's heuristic is bad?

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

    I guess that's just a troll... There is a simple win strategy.

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

      What is the winning strategy? I solved the problem but I used a heuristic (go first iff N is odd, and always pick the number that has common factors with the most other numbers), but I see no reason that should be optimal.

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

        If $$$n$$$ is odd, then go first, pick number $$$n$$$ in the beginning, and in the following round, if the jury picks one of $$${2i-1,2i}$$$ for some $$$i$$$, player just picks another one. Similar strategy can be applied for the case where $$$n$$$ is even.

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

Is it only me or was the problem statement hard to understand?

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

I don't want to excuse for my performance, but let me leave some complaints to make the contest better.

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

    Thank you for feedback. Sorry, for these issues.

    • will double check it in next time
    • frustrated to make the same mistake twice
    • first time report of such an issue (will double check it)
    • found an error fast and tried to fix it fast, forgot in hurry to send a message

    By the way hope it was quite good contest.

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

B makes me uneasy. You need to have a 90% winrate against what? Some jury solution that's not even guaranteed to be the best?

If the game has no known winning strategy that can be calculated fast enough, then this is just a tossup — you need to make several attempts because your strategy's winrate will depend on the jury's winrate.

If the game has a known winning strategy that can be calculated fast enough, then this formulation is just dumb and confusing. If it's supposed to be a joke, it's just annoying and not very amusing. Though, the problem statement doesn't guarantee that n is chosen uniformly at random, so you can make a test where all games have the same $$$n$$$ for every $$$n$$$, so I guess I was supposed to understand that it is a "troll"?

And then I find out that the first greedy strategy I write is actually correct.

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

    What's "best"? If the grader plays the winning side, of course it can beat you, and if the grader plays the losing side, all moves are losing unless you mess up.

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

      I mean optimal. From the problem statement alone it's not clear that the grader always makes correct choices (it is even called a heuristic and the statement about 90% makes it sound like it might not be).

      A priori, you can't deduce from the statement alone that whether a state is winning or losing is decidable in polynomial time. So it could be possible that you are expected to exploit weaknesses in the jury's algorithm.

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

        But then they wouldn't be able to set the problem if they couldn't decide who was winning in case contestant had a better solution.

        Anyway, from contestant's point of view it doesn't matter too much, just try to solve the problem.

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

I think all the problems except B were really cool, kudos to authors!

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

How will we be contacted according the prizes? My main email in yandex system is [email protected], but I'm not using it at all, I guess that other non-Russian participants too.

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

    In case of some issue with email contact we'll get in touch right here.

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

The problems felt too easy for the finals. I only like problem D because I couldn't solve it.

A — it's trivial what to do; scary implementation
B — fine easy problem
C — trivial with Berlekamp-Massey
D — nice
E — bad convoluted statement; solution is easy if you know that sum over O(smaller child depth) is small
F — ok but why did you allow collinear and coincident points?

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

    Eh, D is pretty much classical "store prefix hashes and prefix reverse hashes", I wouldn't call that very nice.

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

      Don't we need to store the set of mismatched positions in order to find a single candidate for what prefix to reverse? I didn't come up with that during the contest and I don't think it's that standard.

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

        Yeah, we do. I don't see that as a particularly big step though. Maybe I got lucky by coming up with that quickly.

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

          I still don't see how to find a single candidate prefix to reverse. I did see that you should store mismatched positions to give a lower bound on the length of the prefix, but that still leaves O(n) candidates.

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

            Min and max mismatched index define a single candidate prefix. That's because min and max must be matched with each other.

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

              Ah, that's quite nice. I totally missed that.

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

          That's definitely the key observation. In our Polish group only Radewoosh came up with that observation. Call me stupid, but it took me a few minutes to even understand why this is true, yet alone come up with it during the contests :P

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

      I have to say I dislike string problems that can only be solved by hashing: the solution isn't correct for all possible inputs, and you're just relying on the fact that judging is done with fixed examples that are unlikely to break your particular hash function.

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

        There's not much difference between hashing and randomized algorithms in general, so you're basically saying "I don't like all randomized algorithms"

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

          Pretty much. I don't get the same sense of satisfaction of having fully solved a problem.

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

    Ad C. Can you elaborate on that? IIRC Berlekamp-Massey guesses the linear reccurrence from given n points. I am convinced that for a given $$$A$$$ there will be a linear rec. But how to feed it with initial values?

    My solution was like this:

    Let

    $$$g(s) = \text{length of longest unique subsequence of } s$$$

    and

    $$$f(k) = |\{s : g(s) \leq k\}|$$$

    If you have

    $$$f(0),f(1),...,f(|A|)$$$

    you can easily calculate the answer. Let us fix k. To calculate $f(k)$:

    For $$$j=1,2,3,...,k$$$ we define

    $$$g(j, len) = |\{s : |s|=len, s \text{ ends with exactly }j \text{ unique characters, }s \text{ doesn't have a subword of }k+1\text{ unique chars }\}|$$$

    One can write matrix M s.t.

    $$$M \cdot (g[1,len],...,g[k,len]) = (g[1,len+1],...,g[k,len+1])$$$

    Now

    $$$f(k) = \sum_{i, len} g(i, len)$$$

    and this can be easily calculated with matrix exp, if you extend the matrix and the vector to maintain also the sum of everything.

    Also, this got WA, but I am pretty sure that I have a bug in implementation. So if anyone could provide a correct result for 500000000 50, or share a solution, so I can find an input to debug, I would appriciate that.

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

      I don't understand your question. Finding a matrix is only more advanced than solving the problem with dp for small values.

      For me, dp[i][j][k] was the number of strings of length $$$i$$$ with max $$$j$$$ unique characters in a row, and a suffix of $$$k$$$ unique characters. Compute it for $$$i \leq A^2$$$ in $$$O(A^4)$$$ or $$$O(A^5)$$$.

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

        Ok. Got it, so you calculated the first elements of the sequence using the DP (for me that is the non-trivial part). And then used BM to find the simplest lin. rec. the first A^2 elems are satisfying. Having the lin. rec. allows you to find Lth element of the sequence for big Ls easily.

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

    Can you please share your idea on problem A?

    I was able to solve it with (I think) $$$O(L^2 \cdot n \cdot log(k))$$$ where $$$L \leq 20$$$. Using a trie with a map<int,int> for transitions in each node. It worked in ~1.8 seconds in C++, which seems too close to TL.

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

      You can store consecutive elements as decimal numbers since these elements are digits in base k. This way you will get rid of one L factor.

      implementation in case needed

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

        Ah, thank you! I didn't realize that these base-k sequences will fit in "long long" in base-10.

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

          In "long long" in base-10? You don't use base-10 anywhere.

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

            You're right, it doesn't really make sense to use base-10 in this context. But then again, there are 10 types of people in this world, right? :)

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

How to solve task D in final round?

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

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

I missed the finals because there was no e-mail from Yandex Cup about me qualifying to the finals and/or reminder e-mail before the contest. Actually, the last e-mail I see from the organizers is dated August 7.

Of course, it's my fault that I don't visit clist.by on a daily basis :)

But still, it's quite normal to expect that that finalists have other things to remember other that the date of the finals, and make some effort on notifying us.

Dislike to Yandex Cup for that.

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

    Check your spam and filters, I have mails with remainders as intended:

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

      I double-checked. No letters. Also, I know that Egor did not receive these e-mails as well.

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

        Have you checked correct inbox? Or maybe redirects are broken?
        I noticed strange thing, that mails on screenshot above are sent to @mail.ru, though I of course take part with my @yandex.ru account
        Of course it's my random guesses and only Yandex can answer properly

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

      I only received 1 reminder yesterday, and interestingly it is different from the one on your screenshot: it has "уже завтра" in the title, and starts with a slightly different text. Seems like they have different mailing lists and send different emails to these lists.

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

Yandex when we can expect backend standings revealed?