Блог пользователя Zlobober

Автор Zlobober, 4 месяца назад, По-русски,

Всем привет! Завтра, 8 апреля в 15:00 MSK пройдет третий отборочный раунд Яндекс.Алгоритм 2018. Перейти в контест можно с сайта Алгоритма.

Раунд подготовлен мной с большой помощью от GlebsHP, а также всех, кто поучаствовал в прорешивании. В задачах вам предстоит помочь некоторым из моих коллег по Яндексу справиться с разными жизненными (и не очень) ситуациями. Всем удачи!

Вход в контест

UPD: Раунд завершился! Наши поздравления Merkurev, j_______________________ и Um_nik, показавшим наилучший результат в раунде.

Отборочный этап завершился и теперь известны имена участников, проходящих в финал соревнования в Санкт-Петербурге: таблица результатов.

Также доступен разбор раунда (ENG only).

Всем спасибо за участие и до новых встреч!


Важная информация для участвующих в Открытом Кубке
 
 
 
 
  • Проголосовать: нравится  
  • +57
  • Проголосовать: не нравится  

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +53 Проголосовать: не нравится

Here are the past Yandex Algorithm Round 3s:

2013

2014

2015

2016

2017

Good luck to everyone participating!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

По правилам, если один участник заработает футболку за два разных трека, то ему дают одну. А куда уйдёт другая?

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +46 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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!

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve E

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 месяца назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              3 месяца назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              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.

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I use flow graph and get AC in upsolving.

      This is my AC code

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 —

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

What is corner case in C??

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D? Was it Binary Search?

»
3 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится -58 Проголосовать: не нравится

Is It Rated?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will test data for E in gym be fixed?

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
3 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I used binary search for Problem D but I failed on test case 17. Is there any corner cases that I missed? Here's the link to my code Your text to link here...