### Zlobober's blog

By Zlobober, 5 months ago, translation, ,

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, j_______________________ 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

•
• +57
•

 » 5 months ago, # | ← Rev. 2 →   +53 Here are the past Yandex Algorithm Round 3s:20132014201520162017Good luck to everyone participating!
•  » » 5 months ago, # ^ |   +5 I don’t know why it’s downvoted, but this is really helpful, thanks!
 » 5 months ago, # | ← Rev. 2 →   +46 There is no link yet at https://contest.yandex.com/algorithm2018/ to the contest itself
•  » » 5 months ago, # ^ |   +51 Yandex contest links are like CF point distribution. It will appear in the top panel next to the optimisation and ML round "soon" (or "shortly before the contest").
•  » » » 5 months ago, # ^ |   +5 And occasionally it is shown in the blogpost after the contest starts.
•  » » » 5 months ago, # ^ |   +2 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!
•  » » 5 months ago, # ^ |   +39
 » 5 months ago, # |   +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.
•  » » 5 months ago, # ^ |   +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!
 » 5 months ago, # |   +10 How to solve E
•  » » 5 months ago, # ^ |   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.
•  » » » 5 months ago, # ^ |   +10 We can apply Hall's Theorem to check if a certain Ai is valid.
•  » » » » 5 months ago, # ^ |   0 By the way, how to prove that we should choose Ai greedily?
•  » » » » » 5 months ago, # ^ |   +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.
•  » » » » » » 5 months ago, # ^ |   +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.
•  » » » » » » » 5 months ago, # ^ | ← 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.
•  » » » » 5 months ago, # ^ |   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.
•  » » » 5 months ago, # ^ |   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.
•  » » » 5 months ago, # ^ |   0 I use flow graph and get AC in upsolving.This is my AC code
•  » » 5 months ago, # ^ |   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 —
•  » » 5 months ago, # ^ |   +10 You may also check the official editorial, you may find the link in the post.
 » 5 months ago, # |   +10 What is corner case in C??Also what is the cut off rank to be in top 256 across all elimination rounds
•  » » 5 months ago, # ^ |   +5 my problem in C was integer overflow
•  » » 5 months ago, # ^ |   +20 My problem was using (x+y)%2 to categorize bishops into two arrays.
•  » » » 5 months ago, # ^ |   +5 what was wrong with that????
•  » » » » 5 months ago, # ^ |   +20 it may be -1 0 or 1
•  » » » » 5 months ago, # ^ |   +20 -1 % 2 = -1
•  » » 5 months ago, # ^ |   0 Regarding 2 : Refer this link. Until Round 2, the criteria was to get a best rank of less than 163, It will get modified to a tighter rank after round 3.
•  » » 5 months ago, # ^ |   +5 Cut off can be seen here: https://contest.yandex.com/algorithm2018/algo-results/?p=6
 » 5 months ago, # |   0 How to solve D? Was it Binary Search?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 months ago, # ^ |   0 How much time it is working on C++?
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 1,6 second with 200 iterations of binary search
 » 5 months ago, # |   +18 Now that the top 256 in Algorithm track is decided, When will you send t-shirts? :D
 » 5 months ago, # |   +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.
»
5 months ago, # |
-58

# Is It Rated?

 » 5 months ago, # |   0 When will test data for E in gym be fixed?
•  » » 5 months ago, # ^ |   +10 It fixed now and all the solutions is rejudged.
 » 5 months ago, # | ← 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?
 » 5 months ago, # |   +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.
 » 5 months ago, # |   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...