lperovskaya's blog

Second edition of Yandex.Algorithm 2015 Round 2
By lperovskaya, history, 9 years ago, translation, In English

Second edition of Round 2 will start at 08:00 on June 13, 2015 MSK.

Don't miss your chance to win a tshirt and advance to the final round.

The round is made by GlebsHP, he even promises to share the problem analysis right after the end of the round. What a nice reason to wake up early on this Saturday!

UPD: The round is right around the corner!

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

»
9 years ago, # |
  Vote: I like it -13 Vote: I do not like it

After this contest if someone solved 0 is in 512 will he/she take a t-shirt?!

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

People are talking that t-shirts only for indians,please tell us that we can get t-shirts from any place ^_^

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

    Only Indians are eligible to get AC in Yandex, so how would you want to win Tshirt with 0 problems solved?

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

      I always thought that Yandex sounds a bit indian :]

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

Firstly it said "The contest is over. Submissions are not allowed" and then it allowed to virtually participate. Was that supposed to be like that xd (I started)? Please don't do it to me for the second time ; d

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

Please, press the "start virtual contest" button.

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

    There is no such button anymore.

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

    No such button now :(

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

    There are no standings. (Although that may be because nobody has submitted anything.)

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

    i clicked on it, and it shows "The contest is over. Submissions are not allowed"

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

    Seriously? Surprize virtual contest?

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

For how long virtual contest will be open?

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

    we'll fix the starting time for everyone on 8:00 in a few minutes

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

      So everyone who started virtual contest earlier will have an advantage?

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

        Was it possible to start it before 8:00? Or do you mean they didn't set start time to 8:00 for people who started virtual contest?

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

Screw you guys, I'm going home

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

    Is this not a "start virtual contest" button that I ask everyone to press on the title page?

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

      This has no sense: I've pressed 'start vritual contest' button at 8:20 and saw "time left: 1:20" (as if I pressed 'start' at 8:00). This totally ruined contest for me.

      Don't get me wrong: problems were great and I'm in top-512 for sure — nothing more to wish as a participant.

      But as a human, it was really annoying to see that Round 2.2 went on par with Round 2. In both rounds, there was a non-straightforward way to see problems (random F5 pressing in Round 2, "start virtual participation" in Round 2.2), which put participants in different conditions. And in both rounds, administration neglect that fact and try to continue contest as if nothing happened.

      In round 2, the announcement about failure was after about 40 minutes, but it was obvious from the start that something went wrong.

      This time, there was a fast announcement that one should press "start virtual participation". But it was totally confusing: I came here for a normal round, not a virtual one. Why should I press that button? Is it safe? Will my participation count in overall rating? Will I save my time or it will start from 8:00? All those questions arouse in my head and I was not sure about pressing that button. And immediately my fears were proven: timer started from 8:00, consuming some part of my time. And after opening standings at the end of contest (my time was out), I saw people with 1:33 and 1:28 virtual participation time (meaning they were still competing). Ridiculous.

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

Yandex.GEOMETRY.com

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

    I have no idea about geometry.. i could do only 1 question :(

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

      I have ideas,but can't implement coz have not knowledge how to sort vectors by angle,how to find angle and others...

      Here I think,for each bitset of length n(which means use i-th vector or not)we should add all angles in 2 consecutive vectors and it should be 2p and then anwer will be "YES";

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

    accurate!

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

Am I stupid or D really needed knowledge that every Pythagorean triple can be described as (d(i2 - j2), 2dij, d(i2 + j2))?? It took me much time to solve this problem and I felt sad seeing so many accepted submission xd.

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

What was in 50th test of problem A?

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

I apologise for not being able to publish analysis immediately. Hope to finish it before today's GCJ.

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

I'm very interested to see tests 17, 21 and 31 for problem F. There's something strange about my verdicts.

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

    21 and 31 are too large to be posted.

    Test 17: baababbbbaa

    Answer for test 17: aabbabbbbaa

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

      What about 4 test in D?

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

      Thank you, found my mistake already. It's so stupid :(

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

I used the following logic to try A:

Firstly, if 2 vectors are not in opposite directions, then i assumed that the sector formed by the smaller angle between these 2 vectors is reachable.

Hence, using above inference, i sorted all the given vectors according to the angle they make with x-axis and checked between which 2 vectors does our destination lies. If the difference between the angles of these two vectors is less than PI, output YES , else output NO.

This gave WA on test 39. What might be the fault in this solution?

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

    You may have problems with precision. Because coordinates can be up to 109, the difference between two angles can be about 10 - 18, so you need to use exact arithmetic.

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

      is there any way i might do this with double? i don't have much experience in handling precision errors.. what is the suitable value of eps in such cases?

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

      I was calculating angle using atan2; code with eps=1e-12 gets AC.

      So either tests aren't good enough or difference between angles can't be so small.

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

        Tests like this should have very small difference in angle:

        0 0
1 0
2
1 999999999
-1 -1000000000

        For this test, the answer is YES. And for the next test, the answer is NO:

        0 0
1 0
2
-1 999999999
1 -1000000000
        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +29 Vote: I do not like it

          Better way check precision problems is to use vectors like (1000000000, 999999999) and (999999999, 999999998). Atan2 returns the same double for them

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

            Hah, funny. At first thought there shouldn't be difference, because your angle is approximately just 2 times smaller, but what is important here is that atan2 values for eatmore's points are very small, so they are kept with higher precision and that is big difference. Nice!

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

        There were about 10 tests with very small angle differences (about 10 - 18, as eatmore mentioned). No idea why your code has passed, I will investigate this case in the free time and post the result here.

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

Is there some place I can check my T-shirt address :) to make sure it's correct?

The registration form is inaccessible now.

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

Did registration form ask address?! I couldn't remember.

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

27th place after 3 rounds, what a sad story :((

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

I'm eager to know how to solve E. If only rectangles nx0 or 0xm would be allowed! Then I will be able to solve it using just one flow. But in order to exclude them I need to run nm flows and that clearly TLEs. However I got an idea how I can speed it up, but it seems too complicated...

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

    I used m*n dinic flow and it was fast enough. The execution time was always below 1 second.

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

    nm Kuhns should be fine.

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

    nm Kuhns without any optimisation attempts whatsoever runs in 1.037s. I was surprised too!

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

Could the organizers, please, provide a way to check which address we used when we registered for the contest? Thanks!

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

Any news about t-shirts?!

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

    Check your email or go to algorithm.contest.yandex.com for more information

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

Who are the t-shirt winners of Warm-Up round?!

→ Reply