Endagorion's blog

By Endagorion, history, 8 years ago, translation, In English

Cheers everyone.

Today, on June 13 at 10:00 MSK the third and final qualification round of Yandex.Algorithm 2016 tournament will take place. I am the author of all tasks in this round. I wish to thank Ivan Gassa Kazmenko, Oleg snarknews Khristenko, and espically Aleksey Chmel_Tolstiy Tolstikov and Maxim Zlobober Akhmedov for their immense contribution to problems preparation. I also thank Yandex employees who were involved in testing this round.

Best of luck!

UPD: the round is complete! Congratulations to Um_nik, who was the only one to solve all problems!

You can find the elimination standings here. Congratulations to 25 best participants!

Editorial here

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

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

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

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

How to solve Problem B — BMO and Garland?

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

    Iterate for left turned on lamp. add 2^(min(k - 1, len of suffix)) to answer

    UPD: and also add 1 for case when there's no lamps at all

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

      I've got WA 11 using this approach, and all the contest spent testing :(

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

        2^(k-1)%m != ((2^k)%m)/2. It my WA 11. Very stupid bug :(

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

    Formula: (n - k + 2) * 2k - 1. But actually I have no idea how to prove it, just found it by bruteforcing.

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

      fix '1' in the left suffix : full segments : (n-k+1) * 2^(k-1) not full segments: sum from 0 to (k — 2) 2 ^i and just zeroes — it's 1 more, not full segments and just zeroes gave 2^(k-1).

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

        Wow, that's pretty clear. Thank you so much.

        UPD: Thank you all the guys below for explanation.

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

      Well, I first thought it would be like (n - k) * 2k, that is, (n - k) positions to fix a window of size k and 2k possibilities for each window. However, this has over-counting.

      But, we can fix ones at the end of each window padded with zeroes on left and right of the window, and then place anything in between. Dunno how to put that in a formula though.

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

      fix any segment and set leftmost and rightmost lamp. If set has length l, then count of possible variants is 2l - 2. For fixed l count of segments is n - l + 1. And then answer is sum for l = 2 to k of 2l - 2 * (n - l + 1). And need to add n + 1 (for l = 0 and 1). Simplifiing formula gives us your formula.

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

      Say you fix the first K long segment at the beginning. Now you have 2^k possible ways. Every time you move your segment one along, you should not count all the combinations where the lamp that just left your segment was turned off, as they are also valid in the new segment, but already counted. That is 2^(k-1), so for the new segment that is one to the left we add (2^k)-(2^(k-1)) = 2^(k-1) to our answer. We do this n-k times, as this is how many times we can move the segment. So answer is, as you said, 2^k + (n-k)*2^(k-1) = (n-k+2)*2^(k-1)

      EDIT: I guess I was the last of a million people to all post within 1 minute ;)

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

      First add all possible for the first k lamps.

      res = 2^k

      Now say the right most turned on lamp is i > k. Iterate over all n >= i > k.

      You will notice for each such i, answer is 2^(k-1), since you have fixed i-th lamp.

      Hence formula is: 2^k + (n-k)2^(k-1)

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

    Iterate l over range [0..k]. Consider all possilble segments of length l with leftmost and rightmost bits set to 1. For every position, there are 2max{0, l - 2} possible segments, making (n - l + 1)·2max{0, l - 2} possibilities for each possible l (except when l is 0 when there is only one possibility: a string consisting of all zeros).

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

    Most intuitive for me was the following:

    Imagine all numbers from 1 to n. For n equals 5 it is going to be:

    00000

    00001

    00010

    00011

    ....

    11111

    If k =3, then there are exactly 2^k numbers with three digits, we count them in. There are 2^k numbers with exactly four digits, but we are intersted only in those which end '0', like:

    01010

    01100

    01110

    So there are 2^k / 2 = 2^(k-1)

    Then we look at numbers with exactly five digits, there are 2^(k+1) of them. But we are interested only in those which end by 00, there are 2^(k+1) / 2^2 = 2^(k-1) of them.

    And so on. So the final calculation will be 2^k + 2^(k-1) + 2 ^ (k-1) + 2 ^ (k-1) + ... + 2 ^ (k-1) repeated (n-k) times.

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

any idea how to fix WA3 in C?

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

    I think the scenario in that case is that after losing to some vampire i, we will lose to a vampire j < i few times and build up the strength to beat i later.

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

    +1, what can be wrong?

    my code

    EDIT: Yeah, I assumed that the defeated prefix never decreases.

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

      On a different note, how do you post collapsing blocks in comments? I tried the two options available (block, inline) both does not collapse the code.

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

        Try spoiler. I used below (but without dots).

        <.spoiler summary="description">

        .~~~~~

        code is block, block is in spoiler

        ~~~~~

        <./spoiler>

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

    I thought the number of fights in one "run" never decreases when I had WA 3.

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

    Very tricky. It is possible that you return to the original position with fewer points and still the answer is not -1.

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

    3 4 0 5 0 8 0 0 9 0 7 answer: 8

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

    Spent 13 wrong submissions on this (which effectively disqualified me), but finally got it right.

    The point is that sometimes it pays of decrease the starting value of M, while my original algorithm terminated when such a situation occurs.

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

      And on the 13th day the forces of code went to their forum and said unto each other: "Why can't we solve a baby problem? What's wrong with us?" And they answered: "Behold, thine logic has given way to thine vanity."

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

    My solutions failed on such case: 3 2 0 7 0 8 0 0 10 0 100

    Answer should be 8.

    UPD: Its wrong sample, correct one in comments below

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

      How to fix this case? I had a greedy-ish algorithm to go to max point where we can and then increase value to such that it greater than what is needed there. For finding max point where we can reach I used suffix minimum BIT. I am not sure how to fix my idea to accommodate for this case as it would keep on running in prefixes. Can it not be fixed using my current idea?

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

      are you sure it's 8? I got AC now but my solution still thinks it's -1

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

        Correct answer is -1. When we lose the third battle the strength become 0, and we can not win first battle.

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

        Oh, sorry, my bad.

        Correct one should be: 3 2 0 7 0 8 0 0 10 0 8

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

When will the final standings (three rounds combined) be released?

UPD: It's out!

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

Yandex rounds have really good quality. C, D and E were nice problems, thanks Endagorion.

Though, D was much easier than C and E.

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

How to solve Problem D?

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

    Check what is in . Then, with binary search find on the right the first cell of different type. Then, the same on the left.

    In binary search you should check X + 1, X + 2, X + 4, X + 8, ... till you find the first different type. Then standard algorithm.

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

    Let's find minimal k such that cells 0 and 2k have different colors (iterate k). I state that cells 0 and 2k are in consecutive segments (ease to prove, try yourself). Using binary search find the leftmost cell in 2k-s segment. Now repeat that starting from that cell instead of starting from 0. We have found starts of two consecutive segments. It is queries (and complexity).

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

from Provision: final round — July 28-29, 2016

from Schedule: 28-29 Jun 2016

Could someone clarify? Also, will there be someone from Yandex willing to help with visas?

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

A common reason for blind submissions: Submit near the end of the contest and no time to debug if the code is wrong.

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

How to solve C?

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

Does anybody know where I should write my address on yandex? I am in first 500 competitors, but I can't find field for address and they can't send me a t-shirt :D. Thanks

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

    We'll get in touch everyone in TOP-512 this week.

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

      This is not a TOP-512. This is the list of 512 people who can afford themselves to take part at least in two rounds.

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

        Better than year ago :)

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

        Even red still need to participate in competitions to win.

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

Some important information for non-Russian-speaking people:

"The Organiser shall not reimburse the Finalists’ costs of transfer from the place of residence of the Finalist to the final round" "Finalists can participate in the final round at the final round venue or online."

Are you planning to attend the onsite finals?

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

 What about #513 who has the same penalty with #512 :) ? Can he receive T-shirt ?

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

Love the blind submissions. Encourage people to code more carefully and not to depend on the testing system to check their codes. And the reward for the brave people is very worthy — Much fewer penalties time!

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

Let's settle this once and for all. Amazing World of Gumball >> Adventure Time :))).

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

Have everyone received the notification mail about the T-shirt? My friends received it yesterday, but I haven't yet. So I am really worried that they lost my email...

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

    I haven't received it yet either.

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

    Please fill feedback form. You can find the link in the bottom left corner of the contest page.

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

      Please give me advice on T-shirt.

      I will be in Russia in August, so thinking to put Russian address in the form instead of Cayman Islands. Do you think it is realistic to receive T-Shirt to address in St. Petersburg by August 26th? Otherwise I'll stick with Cayman Islands address.

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

        August 26'th is perfectly realistic date for St.Petersburg. Fill in Yandex office address and my name, if you want a personal office tour with your shirt =)

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

    I've surprisingly found mine in a spam folder.

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

      Mine too, but I provided @mail.ru address, so I can understand why :)

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

        The same thing to me)

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

        Where did you provide your email? I can't remember if I did that.

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

          If you are not sure, please fill the feedback form on the contest page.

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

            Well, I'm #513 who has the same penalty with #512. As you said before, I am able to receive a T-shirt.

            However, I haven't receive any mails from Yandex, even when I filled the feedback form on the contest page. So could you consider my problem?

            Thank you so much!

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

              Of course you get the tshirt too! Sent you an email about now.

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

    T-shirts are coming. A courier delivered it to me today. What is strange, I had to fill in my passport number in his papers, he said it's required when the package is insured.