Chmel_Tolstiy's blog

Yandex.Algorithm 2016 Qualification round
By Chmel_Tolstiy, 9 years ago, translation, In English

Yesterday ACM ICPC World Finals finished. We congratulate all winners, medalists and special prize winners!

We want to remind you that tomorrow, May 21, at 00:00 (UTC+3) the qualification round of Yandex.Algorithm will start. For participation in qualifications you should register and start a virtual contest at any time prior to May 23 (UTC+3).

As usual 6 problems of varying difficulty will be provided at Yandex.Algorithm rounds. In order to qualify for the elimination stage rounds and compete for a trip to the finals in Minsk and other prizes you should solve at least one problem.

Also Yandex.Algorithm offers students to participate in the internship track. For more information see the rules of the championship.

Good luck! See you at Yandex.Algorithm!

P.S. The qualification round has started. Problems prepared by Romka, Ixanezis and Chmel_Tolstiy.

EDIT. Analysis has been posted.

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

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

The people who qualified earlier in the warm-up round, can they participate in this round too? Will this performance affect their qualification?

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

    "Only those contestants who have correctly solved at least one problem in the test or qualification rounds will be eligible to proceed to the elimination round."

    Please refer here for the rules. :)

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

    All can compete in the qualification round. Good luck and have fun!

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

When will The editorials be posted or when will they reveal test cases?

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

Are Indians eligible for internship opportunities and participation in the contest ?

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

Can someone explain what is the difference of the blind and open submission?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +10 Vote: I do not like it

    With blind submission, you can't re-submit your solution if it passes the tests from the statement (it is tested on the full test suite only after the contest). In the scoreboard such submissions are marked as ?.

    This can decrease your time by 100 × X / Y seconds, where X is the number of contestants that didn't solve this problem and Y is the total number of contestants.

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

"For participation in the Internship Track, the nomination participant shall tick the appropriate checkbox in the registration form."

Why don't I see any checkbox? There is just a textbox next to "I want to participate in the Internship Track".

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

    Type something like "Yes", "Sure", "I would be happy to" =)

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

I forgot my password and the answer of my security question! Is it possible to restore my password?

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

How to solve F?

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

    In case radar isn't at integer distance from some point — we can move it further from this point without losing score on this particular point. Therefore there exists a solution in which radar is at integer distance from some point.

    Now in the same way by moving a radar over some circle we can show that there exist solution in which radar is at integer distance from two points (unless we have N=1 in the input).

    Therefore we have a set of interesting locations to check: take a circle of integer radius R1 with center at point p1, a circle of integer radius R2 with center at point p2, intersect them :) Our set is clearly finite — you don't need to check some R which is too big, because in such case your location will be too far from all points. In case your location is at distance more than 4 from each point, your best possible score is 20/25, and that's clearly not an answer (you can get at least 1 by placing radar at some point from input), therefore your location should be relatively close to at least one point from input.

    And +27 by mmaxio make me think that one can make some random/locopt solution get AC as well :)

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

      That's what I wrote... and got WA. Geometry problems.

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

        Hint: you have a bug

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

          Yeah, that's what I figured. Geometry problems: practically impossible to not make several bugs (I fixed one during the contest).

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

          Lol. This is how editorials for geometry problems should look like.

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

Is the editorial posted somewhere?

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

What's the solution for problem C?

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

    For each round one team gets 2 points, the other gets 1. However, this value is not important, and the only way the N teams can have distinct scores are if one team wins (N-1) games, another wins (N-2), ..., wins only one, wins no games. Therefore, the only possible outcomes that produce distinct scores can be represented as permutations of the N teams.

    Generate a permutation. Then for each permutation you calculate the probability of the corresponding outcome.

    For example, if you generate 3 1 2 for N=3, p = p_{3>1} * p_{3>2} * p_{1>2}

    You add all N! possible outcomes that give distinct scores, which is the total probability of the teams having distinct scores. This provides a O(N^2 * N!) solution which is sufficient, but I think optimizations such as memoizations can reduce the complexity to O(N * N!) or less.

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

      Awesome, thanks for a very clear explanation!

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it
      but I think optimizations such as memoizations can reduce the complexity

      If you'll want to improve your solution for higher constraints, you may use bitmask DP to get 2^N instead of N! — when considering next guy in standings, you don't care about relative order of people above him, only about subset which they form.

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

What's D's solution?

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

    Lets call all the numbers formed by alternating bytes(e.x.1,10,101...) — patterns. Enumerate the patters in some way( there are only 61 of them).

    Now it looks like a simple dp: dp[prefix][pattern][flag]

    Where flag means if the whole prefix of our imaginary number is equal to the prefix of N.

    The complexity of dp is O(log*cntOfPatterns*2).

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

Anyone know if it'll be possible to see the test cases? I'm really curious what test case 12 on problem D is so that I could try and figure out what's wrong with my solution.

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

    Im sure you have LongLong overflow (:

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

      Yeah probably... just thought I triple checked for that. I'll check a fourth time

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

I had qualified for the elimination round of the contest (even received a mail regarding this), but now when I go to the website (contest.yandex.ru), it says "Unfortunately, you have not progressed to elimination stage of Yandex.Algorithm-2016". Can you please look into it.

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

    Did you log in to your account? For some reason, it shows this message to people who aren't logged in.

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

      I was logged in when it displayed this message. Regardless, I logged out and logged in back again and it now shows the correct message. Thanks!

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

Are we supposed to wait on https://contest.yandex.ru/? 'Cause I don't see any timeout there, or some message at 16:00 here will be tasks...

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

Guys, you are worst contest organizers among contests I have participated! (I didn't participate in Challenge24 :P)

First of all that contest lasts 100 minutes and expected time of judgjing my submission is ~20 mins, that is 20% of whole contest! How many participants did you expect? 10?

But that is not as important as wrong tests in C :|... I spent 30% of that contest waiting for my submission to C to evaluate and 50% of contest staring at my code searching for a bug to learn few minutes before the end that both of my (substantially different) submission were correct -_-.........

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

    Tests in C were wrong? I don't see anything related in jury messages.

    Such a slow judging was forcing you to submit in blind.

    Problems were nice though.

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

      Yes, they were. Message relating to that is "Test 10 was fixed". I had two substantially different submissions, one submitted at 0:12, one at 0:33 and both got WA on 10th test. Few minutes before the end both results changed to OK ._. According to ikatanic's comment which was here, but disappeared "The numbers are given in non-ascending order." was not fulfilled.

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

        Actually I'm not sure that was the violation. Maybe both of my submissions turned OK after they fixed the test.

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

    Why did they use different test cases for different participants anyway? It's hard to think that test cases might be invalid when there are more than 100 participants who got their C accepted..

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

      Probably they used a bit different algorithm which didn't need input to be sorted.

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

    I am one of the worst contest organizers. I'm so sorry that we made several mistakes during preparation and during contest. Black day of polygon hurt us too, but most mistakes were made without it.

    • we ignored proposal to decrease number of tests in A and B
    • we added test in C without checking validator (sorry polygon)
    • we made personal notification about rejudge C (possible not to all, not checked by me now)
    • we fixed several issues in problem statements during contest

    I hoped that my work at Yandex.Algorithm 2016 will make it better than last years. Seems I'm wrong. I just want to say "Sorry, and hope to see you in the next round".

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

      Regarding the judging queue. If you want to use your platform then I think you should extremely carefully choose easy problems (let's say A and B). It should be possible to have a very small number of tests. As a participant I would prefer even a stupid (non-interesting) easy problem but thanks to it being able to see my submission being judged faster than after 1/5 of the contest.

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

        "a very small number" means something much smaller than 192 (the number of tests in B today)

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

      Thanks for apologies :). If one is good enough he should qualify even when starting in just two rounds :P. Tasks were nice. I may sound harsh when mad, but I don't get discouraged easily, so I will surely participate in upcoming rounds, hope there won't be such problems :). I am sure you are able of organizing good rounds, but just need to pay more attention to every detail.

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

        Sure, we will pay more and more attention to details (I hope to every one).

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

How to solve problem F? I know how to compute dynamic complexity, but I wasn't able to find a string whose dynamic complexity is high enough. My best result for n = 10000 is 64613, out of needed 92104.

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

Seems like the most useful profit from blind submissions is not time bonus but not getting confused with false WAs because of wrong tests xd.

And regarding to slow judging queue. Should I remind you what happened during last year's middle-night round? Will you ever get a reliable platform?

That round definitely should be "unrated", however I guess organizers don't have guts for that, I understand that organizing another round is a big effort and for those who have submitted C blindly or used an algorithm not relying on input being sorted round was fair. However it can't be denied that for me contest was completely lost and that is 100% organizer's fault.

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

Can you translate all questions (clarifications) you answer in public? During the contest it isn't convenient to see some question and answer in Russian (for people who don't know Russian).

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

    +1 to that. After some time I stopped paying much attention to them, because there were too many of them and some were in Russian :P. Btw, should I refresh page to see up to date notifications? I checked notifications after Errichto told me tests to C are wrong and I didn't see anything regarding to that there. After some clicking it appeared there, but I don't recall what was exact order of my actions (refreshing, clicking etc.).

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

    Yes, we will translate all clarifications from this round (in short time), and in next rounds all admins will answer both languages.

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

Will the editorial be posted for round1?

→ Reply