Zlobober's blog

Yandex.Algorithm 2018 Round 3
By Zlobober, 7 years ago, translation, In English

Hi everybody! Tomorrow at 12:00 UTC there will be the third round of Yandex.Algorithm 2018. You can enter contest from the Algorithm main page.

This round is written by me with a great help of GlebsHP and everybody who was testing the round. While solving the problems, you will be helping some of my colleagues here at Yandex to deal with some practical (or not) situations. Good luck to everybody!

Enter the contest

UPD: Round is over! Congratulations to Merkurev, jcvb and Um_nik who got first three places in the standings.

The elimination stage is over and we can now find out who are the contestants that are going to compete in the Algorithm Finals in Saint Petersburg: elimination scoreboard.

There is also a round editorial (ENG only) available.

Good luck and see you later!


Important information for Opencup participants
  • Vote: I like it
  • +57
  • Vote: I do not like it

Comments Comments (40)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +53 Vote: I do not like it

Here are the past Yandex Algorithm Round 3s:

2013

2014

2015

2016

2017

Good luck to everyone participating!

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

    I don’t know why it’s downvoted, but this is really helpful, thanks!

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

There is no link yet at https://contest.yandex.com/algorithm2018/ to the contest itself

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

The link shows me Round 2 of ML track, not Round 3. Note that I'm not 100% sure that I use the correct Yandex account, since it's been a while.

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

    It should be available at the algorithm page now, but for your convenience I also added it to the body of the post. Good luck!

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

How to solve E

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

    The following passed in upsolving (after the end of the contest :( ). The main observation: we can solve the problem from highest to lowest bits greedily. I.e., first find how many numbers among x and y contain bit 219, let it be X19, Y19. Say A19 = min(X19, Y19). Now, let's define X18 as "max number of x's with bit 218 we can choose, assuming we also choose A19 numbers with bit 219 in addition". And so on; the answer is .

    How to compute Xi, Yi? Naive approach would be max-flow, just build a graph with numbers on one side and bits on the other. It is even incremental (we go over bits and add new edges to the sink). Unfortunately, this gets TLE even with optimizations (at least, in Java).

    Now, an improvement: we can compress the graph significantly for most of the iterations: when computing Xi, we're interested only in the last 20 - i bits, so if 20 - i is small, we replace n with 220 - i in graph construction. This already fits in TL, even in Java.

    I'd be interested in a faster solution, though.

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

      We can apply Hall's Theorem to check if a certain Ai is valid.

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

        By the way, how to prove that we should choose Ai greedily?

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

          Suppose you have a solution that isn't as greedy as possible i.e. A_i is suboptimal. Then there is some edge you can add with weight 2^i. To add it, you may have to discard one or two other edges from your match (those sharing a vertex with your new edge), but they have weight at most 2^(i-1), so you haven't reduced the total weight.

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

            Suppose that x1, x2, y1, y2 = 2, 1, 3, 2.

            In the optimal solution, we should make pairs (x1, y2) and (x2, y1), and in this case A1 = 1, A0 = 1.

            Consider a suboptimal solution: pairs are (x1, y1) and (x2, y2), and A1 = 1, A0 = 0. But we need to discard an edge of weight 2 to improve this.

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

              You're right, my argument doesn't work.

              Here's a new one, although a lot less intuitive: consider the solution based on Hall's Theorem. If you decrease Ai by 1, what is the effect on the rest of the solution? Ai + 1 will increase by at most 1, Ai + 2 can increase by at most 1 etc; and the increases sum to less than what you've lost.

              I think it needs a bit more work to make it formally correct, but that's the outline.

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

        That's exactly what I did, and it passes in upsolving (you also need to use a Mobius transform to make it O(2^N*N) rather than O(3^N)). Unfortunately I only realised this solution 90 seconds before the end of the contest and didn't have time to code it.

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

      I used Hall theorem in the second part of my solution in order to compute maximal possible Xi and Yi. So we only need to know number of vertexes, which have at least one common bit with some mask, and we can compute it offline in O(2^20 * 20), as I did.

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

      I use flow graph and get AC in upsolving.

      This is my AC code

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

    First of all, we want to maximize number of 219 edges, then number of 218 edges and so on. To do this we will use Hall's marriage theorem. Suppose we have already fixed the number of edges 2p for all p > k and now want to find the number of edges 2k. According to Hall's marriage theorem we should satisfy some inequalities of the form: , where Amask is the number of such x in one of the input arrays that x&mask ≠ 0. Since ansi = 0 for i < k (for now) we can check these inequalities only for mask which has lowest 1-bit on position k. To calculate Amask we can use or-convolution. From these inequalities we can deduce the biggest possible ansk.

    Complexity —

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

    You may also check the official editorial, you may find the link in the post.

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

What is corner case in C??

Also what is the cut off rank to be in top 256 across all elimination rounds

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

How to solve D? Was it Binary Search?

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

    Yes, we just make binary search and then for every vertex compute Li, Ri — the left and the right border of possible value, according the Lj, Rj in the descentants, receiving with DFS. Checker — if some Li > Ri, answer is false.

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

Now that the top 256 in Algorithm track is decided, When will you send t-shirts? :D

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

It seems like the test data for F is weak. I just submitted a solution that completely ignores that the bottom row and top row are adjacent, and it passed.

→ Reply
»
7 years ago, # |
  Vote: I like it -58 Vote: I do not like it

Is It Rated?

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

When will test data for E in gym be fixed?

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

    It fixed now and all the solutions is rejudged.

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

Problem D, as I think, can be solved by extraction connected regions consist of '*' with numbers on borders. This regions are trees and for every such tree target value is max(|num1-num2| / distance(num1,num2)) for every pair numbers. But I does not know how to solve this task fast. Can anyone help?

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

Is it possible to look at other people's submission, e.g. in CF Gym ?

There is some part in editorial that I don't understand. Would be very helpful if I could take a look at accepted code.

Thanks in advance.

→ Reply