GlebsHP's blog

By GlebsHP, history, 7 years ago, translation, In English

In case you want to take part in Yandex.Algorithm 2018 but somehow haven't registered yet, you might want to follow this link.

Qualification round has started at 00:00 Moscow time, February 17th. Round is a virtual competition 100 minutes long. You can start it at any moment of time till 23:59 on Sunday, February 18th (Moscow time).

We recall that in order to be able to participate in elimination stage one needs to accept at least one problem at qualification round. However, everyone who managed to accept at least one problem during warm-up has already qualified to the next stage.

Judges ask all the participant to withdraw from any problem discussion and do not publish any solutions till 01:40, February 19th.

Good luck, we hope that you will enjoy the problems!

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

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by GlebsHP (original revision, translated revision, compare)

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

I really enjoyed the problems even if I couldn't solve a lot, very interested in the editorial :). Good job!

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

Please change English title to English. Because it is written in Russian I firstly ignored this.

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

    Done, thanks

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

      is it just me or it seems that the title is still not changed.

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

        Haha, Gleb changed it to English title but in Russian language version, not in English :D

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

Is there a way to end contest earlier if everything is already blind/AC?

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

Why do I have to wait something like 4 minutes for my submission to be included in standings? Is it like that in further rounds as well?

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

    We are working on this issue. Hope that during Qualification this is not critical.

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

      It was happening during entire Petrozavodsk camp, so I think that it's problem with whole yandex system.

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

    Why are u always complaining btw

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

6 hours remaining before end of qualification round. Hurry up! :)

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

I don't get it, is there any advantage to submitting blind??

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

    Submitting blind reduces penalty time (which is irrelevant in qualification round)

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

01:40, February 19th Moscow time has passed. How to solve F?

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

    Suppose minimal such distance is d. Then we can place servers on the diameter in vertices that are at distance d from diameter ends. Now we can just binary search for d

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

      Is there a way to solve this if the number of servers > 2?

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

        I do not see easy way to generalize this solution

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

          Alternative approach.

          Fix d and root the tree. Take a look at node v with maximum depth. For covering it, there should be a server somewhere in subtree of d-th parent of v, say u. With greedy conclusions it's optimal to set one of the servers exactly in u.

          Then choose v as the deepest node from the set of nodes uncovered by the first server (it can be disconnected but it doesn't matter) and set the second server in the d-th parent of new v.

          Now check whether each node is covered.

          Seems to be generalizable for > 2 servers

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

        If you can solve this problem: https://main.edu.pl/en/archive/oi/16/gas, then you can enlarge the number of servers a little.(I guess...)

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

        My solution seems to work in with arbitrarily number of server.

        First binary search the farthest distance d. For a fixed d, I'm going to find the least possible number of servers to cover all vertices within d. Let dp[i] be the critical vertex in the subtree of vertex i, where critical vertex is the deepest one still uncovered, if all the vertice in the subtree of i are covered, the critical vertex is the highest one placed with server.

        Then, for each vertex i, collect critical points from its direct children. If the critical point is placed with server but farther than d, skip it. For those uncovered critical points, keep the deepest one. For those with server, keep the highest one. Considering following cases:

        • No critical points: If i is root, place a server. Anyway, dp[i] = i
        • Exists a critical point with server and no critical points uncovered or all uncovered points can be covered by the highest critical point with server: dp[i] =  the critical point with server.
        • Othewise: If i is root or distance between i and an uncovered critical point is exactly d, place a server at i and dp[i] = i. Otherwise, dp[i] =  the deepest uncovered critical point.

        Then, I can find the least possible number of servers to cover all vertices within d.

        It's somehow greddy and I didn't prove it.

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

    Find center of tree. Then cut the deepest or second deepest subtree, find diameter of each component is also pass.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    1. Find diameter, and centre of tree, if it's an edge disconnect that, if it's a node, disconnect either of the edges from it that are part of diameter.
    2. Find diameter of the 2 new trees obtained.
    3. The centres of these trees are your answers.

    Centre is defined as midpoint of any diameter. I don't have a formal proof for it, but it works. Intuitively, since we can prove centre is unique, it makes sense for it to be answer for a single server.

    Also can be easily generalised for an arbitrary K number of servers since at each step, you find diameters of each tree(of the forest) in total O(N) time, so solution is overall O(N·K).

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

      Wow,your solution is cool,but could you tell me about if you should choose 3 nodes,how to proof that your solution is still correct.And I don't know well how to divide the diameter.

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

        I think the 3 server nodes would be the original tree center, and the 2 centers of the partitioned trees. I don’t have a way to prove/test it, but it seems somewhat intuitive by the same arguments as for 1 or 2 servers.

        However, now that you mention it, I believe it is non-trivial to extend this for more than 3 nodes, possibly just doing a greedy(choosing node that minimizes current answer most) works, but I can see why it might not.

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

          Nope:

          7
          1 2
          1 3
          1 4
          2 5
          3 6
          4 7
          

          The only optimal solution for three servers is 2, 3, 4, but the center is 1.

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

How to solve E?

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

    Use 2 pointers to find, for each left index, the rightmost right index such that all words are covered

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

How to solve D?

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

    If we want the smallest possible sequence which we cannot form a triangle, it will be Fibonacci sequence. consider at most the first 100 numbers in a range, because Fibonacci numbers get larger.

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

      Wow that's an easy solution.

      I solved it with two pointers and sets to find dp[L] which gives you the leftmost right border so that this interval havs a valid triangle .. and then in the quereies I see if dp[L]<=R and I print the triple .. and it passed :D .. I don't think the writera meant my solution.

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

        How did you calculate dp[L] ?

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

          you keep moving with the right pointer until you have found a triangle ... but how know that you found one?

          You have two sets, one for the lengths of the current interval, and one for saving the 3 indices that form a triangle (there may be more than one triple).

          Then when you move one step to the right you add this length to the lengths set and you see it's neighbors one to the right, one to the left, two to the right and two to the left and try to form triangle with them. If some triple forms a triangle you add it to the second set with the minimum index first to sort them by index.

          So when the second set is not empty that means that you have found a triple so you can stop, and by that you have found the leftmost R that you can form a triangle with.

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

            I think we can improve a bit this approach. We can store only one triangle and there is always be R index. When move left border we must check only existence triangle with R (if one of the indexes was L). If no such triangle move R.

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

      I learned this idea from the editorial of 766B.

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

      But we should get first 100 sorted elements in range [L;R] (using segment tree for example), isn't it?

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

        you don't have to, for each query sort the first min(100, size) elements in temporary array. , it's fast enough to pass the time limit.

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

          I tried to make up antitest and understood what did you mean :D

          Nice idea.

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

i have 2 questions on yesterday's yandex. 1: can some one plz give me a proof for why this solution for c works. https://ide.geeksforgeeks.org/dkwmWVvF88

2: And i used segment tree for d in which i find the 3 maximum elements in a segment. And if those 3 cant form a triangle, print -1. But it doesnt work. failure on last test case. here is the code https://ide.geeksforgeeks.org/KsnMcNWu6K

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

    2: How did you decide that choosing the largest 3 elements will be sufficient?

    Counter-case 3,4,5,10

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

    For C, the answer is n^((n-1)^2) because after you fill the top-left (n-1)x(n-1) submatrix with anything, there is exactly one way to fill the remaining cells so that the matrix is valid.

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

      Can you proof that the rightest lower cell would be always correct ? UPD: oh, i understood why is it works )

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

        can you elaborate it

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

          1) Consider the top-left (n-1)x(n-1) submatrix 2) The sum of right column will be equal of sum of those elements plus the rightest lower cell 3) The sum of the bottom row will be equal the same => exactly one way to fill value to the last cell.

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

            how do you say that there exists one way. why cant you have 0 ways?. no number to fill it. cuz these 2 sequences are entirely different and how adding those integers will give the same number modulo n.

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

              We should proof, that sum of bottom row is equal to sum elements of right column.

              an, 1 + an, 2 + ... + an, n ≡ a1, n + ... + an, n (n), we can sub from both sums an, n

              Let's proof it.

              => they both contain top-left (n-1)x(n-1) submatrix => the sums are equals => there's exist a value for an, n

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

      Another way to explain: you can fill all cells except for main diagonal with any values. After that you can set the desired values to the main diagonal elements.

      UPD. This solution is wrong. But it led me to a correct formula due to the double mistake. Thanks God, I'm an idiot!

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

        main diagonal?

        for all cells except the both diagonals, doesn't it?

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

          I don't think either idea works, you can't fill center in these cases for N=3 [_,1,1] [1,_,1] [1,2,_] or [_,1,_] [1,_,1] [_,2,_]

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

Any ideas why my solution of problem D gets WA on first test (though it passes the samples)? https://pastebin.com/iiMfq5fJ Maybe I misunderstood something

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

    Successful hacking attempt of Stroustrup's solution.

    5 2
    1 1 10 1 1
    1 5
    2 4
    
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Thanks a lot, I see now, something went terribly wrong with my two pointers approach