lperovskaya's blog

Second elimination round Yandex.Algorithm-2015 will start soon.
By lperovskaya, 9 years ago, translation, In English

For your convenience, we make a new thread for discuss second round of the Algorithm. Will be held on may 30 05:00 (UTC +3).

While waiting for the round you can practice

Don't miss out!

Previous Discussion.

UPD Round 3 will start on schedule at 13:00 on June 6, 2015 and will last 100 minutes.

The time and date of Round 2.2 will be specified later, stay tuned.

  • Vote: I like it
  • -81
  • Vote: I do not like it

Comments Comments (100)
| Write comment?
»
9 years ago, # |
  Vote: I like it +62 Vote: I do not like it

I understand that you wanted to make Yandex available for people all around the world, but since score from eliminations is summed and vast majority of people competing are from Europe and Asia (mainly Russia) then it's just sadism to schedule round on 4 AM :P (5AM for Russia). I guess that moving it 4 hours forward or 4 hours backward will make it much more available to many people and it won't make a significant difference for people which live in timezones where this hour is comfortable.

Nowadays, following TopCoder usually brings nothing good ( ͡° ͜ʖ ͡°)

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

    Sadism is part of Russian culture :)

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

      Indeed. Especially when you have "Internal Server Error" instead of the contest...

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

    5AM for Russia

    5AM in Moscow it's noon in Vladivostok.

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

      Or 3AM in Dublin. Just no :) Sorry for top participants who will have to participate in this absurd.

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

        Well, some top participants don't have to anymore :)

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

      OK, you got me there :). Though I know that China despite its size is in one timezone :P.

      By the way, are there many top competitive programmers in Russia outside bigger cities in west like Saint Petersburg, Moscow or Saratov?

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

        Novosibirsk (UTC+06:00, CF) is the third most populous city in Russia.

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

Internal Server Error

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

Internal Server Error

Is it really so difficult to handle 2,000 people online?

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

codechef working smooth .. yandex site down .. parallel universe!

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

    and UVa is down from yesterday !!! why ???

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

      I don't know why but, it's a pretty regular thing for UVa.

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

Ok, guys. Let's go back to sleep.

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

Internal Server Error ) 5 am is very nice time for jury :)

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

How to solve "Internal server error" problem (Spoilers):

Reduce it to external server error and then it is dynamic programming on servers

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

Can juri just paste problem statements here?

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

    May be they will decide to change date of round, there is no reason to spoiler problems.

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

    Yeah, and have us PM them our solutions.

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

    You probably shouldn't (unfair advantage to ppl who don't visit CF frequently), but you probably can (as in: it probably won't be removed immediately). Mathematical answer! :D

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

    Bad solution.

    1. Most but not all of the participants read CF.
    2. Looks like nobody has read the statements, that's ok.
    3. TCM/Time looks even more strange if we can't submit.
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Many have read problem statements..

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

      Several people managed to submit their solutions and got OK for them.

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

I think we have to sleep :(

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

I recommend open an incognito window/cleaning cookies for those getting ISE.

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

It seems that some people have already seen some problems statements...

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

    Yes, I already coded my solution for A, but can't submit. :(

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

      Me too. :(

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

      "The only thing that limits her is that she is unable to cover a height difference of more than m in a single step". Coundn't understand that part, because max(H_i) <= m, so we can go from i to j for any arbitrary i, j?

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

        I suggest not to discuss now.

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

    Yes, I've seen A

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

Come on!

It has been 20 minutes. Will you postpone it or what?

Are you waiting for gaining more hate of contestants who wake up in the middle of the night?

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

Am I need to register for this contest? I have participate in Round 1?

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

Its 4:24 AM in the morning here, i slept only 2 hours and woke to participate this contest and now its Internal Server Error, give us some update lperovskaya :P

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

    You should go back to sleep, you'll only have an unfair disadvantage, since some people have seen the problem statements.

    At least you're not in a bus with laptop battery charged barely enough for the contest in the original time frame (okay, even less than that).

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

I thought previously that Bayan did really bad...but here you go...

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

Codechef is more stable than Yandex, what a time to be alive!

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

I wonder if somebody is working on that or they just sleep at this late night/early morning time :)

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

Yet another F5-style contest :(

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

I think this contest should be postponed.

I just get off from the bed to participate in this contest while my girlfriend is waiting for me and doubting of my motive in the midnight. Now, I don't understand should I wait for the contest or go back to my girlfriend.

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

    I would prefer a girlfriend to this contest.

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

what is the problem???

I have exam an hour later and can't submit anything!!

PS: now I can not see problems either!

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

I wonder why they don't use Codeforces as the contest platform when Yandex 2012 went well on Codeforces. Now it's like a joke.

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

    I believe its "Not Invented Here" problem.

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

    I guess Codeforces doesn't yet support whatever minor unimportant modifications they want (like the blind/open thing). Make Codeforces more versatile and you avoid these problems.

    They should have canceled the contest after 20 minutes of this, tops. Very unprofessional. Not canceling it at all is even more disastrous (whoever f5s the hardest qualifies for onsite).

    Maybe they tried to cancel it but got internal server error.

    EDIT: After 1 hour, they finally got sane. Good night.

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

They said in QR such a problem won't happen in future rounds... hmmm

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

All problems: https://dl.dropboxusercontent.com/u/48283862/AYandex.pdf https://dl.dropboxusercontent.com/u/48283862/BYandex.pdf https://dl.dropboxusercontent.com/u/48283862/CYandex.pdf https://dl.dropboxusercontent.com/u/48283862/DYandex.pdf https://dl.dropboxusercontent.com/u/48283862/EYandex.pdf https://dl.dropboxusercontent.com/u/48283862/FYandex.pdf

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

    what's the use of seeing the questions when the status of submission is waiting for like forever!

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

Technical issues

Due to technical issues with Yandex.Contest platform results of this round will not be taken into account in elimination stage results. We will inform you about new scheduled time for second round additionally. Sorry for the inconvenience

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

Due to technical issues with Yandex.Contest platform results of this round will not be taken into account in elimination stage results. We will inform you about new scheduled time for second round additionally. Sorry for the inconvenience

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

    Wow! How lucky am I! I have to be in class during the contest, and can't participate. Now I have chance to join it again :D Hope the additional round won't be held on this time again :(

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

      Idea of different times for contests was so that everybody could take at least one with convenient timing. So replacement round should be at the same time.

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

        But we already wake up at 5AM. It's so scary :(

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

          And I am just going to sleep — 23:00 here, tomorrow morning is GCJ Round 2. So nice timing for me ;) I will have to wake up early for one of the rounds too.

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

    Please do not schedule it at 4 AM..... x_0

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

      Lets be fair it's 4 AM not in all timezones and I think 3 rounds are trying to cover all timezones. =)

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

    And the next round 2 is going to be scheduled on the same time?(

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

I want to have some words of support for contest staff here. Bad things happens on all platforms. Some people here asked "Why not Codeforces?", but aren't they very same people who would gladly complain about Codeforces server being down only if Codeforces would be available. TopCoder rounds got cancelled once in a while, etc. I think people would be much more forgiving if it would not happen in this particular round that scheduled at early morning/night for Europe

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

How to solve D?!

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

    If d = 2^p2 * 5^p5 then answer is max(p2, p5) Else impossible

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

    Take a worst case like a number = VeryBigPrimeNumber * 10^k + b, where b = h * d, where h = const. VeryBigPrimeNumber >>>> d, so you need that d = 5^p1 * 2^p2, beacuse 10^k have only two prime divisors(2 and 5) and you need that 10^k mod d == 0. So, if(d != 5^p1 * 2^p2) then ans := -1, else ans := max(p1, p2)! You can found p1 and p2 in O(logN). (My Internet is SlowPoke :) )

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

    Let's assume that the answer for some d is k. It means that we can decompose any integer n into a sum n = a × 10k + b and all we need to check divisibility of n by d is to look at b, i. e. a doesn't affect divisibility by d. Thus, 10k is divisible by d. If d = 2i * 5j the answer is max(i, j). Otherwise there is no such k, the answer is "impossible".

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

How to solve E? I used such dp — f[len_prefix][wasC1][wasC2][wasC3][ost][flag] I fixed the three biggest numbers and then calculate dp. But it gets TLE. Who can help me? Code Link Here

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

    I had even one more field in dp [did we have only zeroes before] but wasC1..C3 were compressed to one bitmask 0..7 and I got AC in 2.8s.

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

      i had a dp with state[len][0..7][mod][flag][zero][C1][C2][C3]. It worked nearly in 198ms.

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

Before the round starts, this blog was +53. Now it's +16, and still decreasing. What a sad story :(( I think all contests should be encouraged, as all managers have tried their best.

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

I'm interested how to solve C without coding brute force for small numbers and looking for a pattern?

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

    Read Wikipedia.

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

      Cannot see anything about giveaway nim there (:

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

        When played as a misère game, Nim strategy is different only when the normal play move would leave no heap of size two or larger. In that case, the correct move is to leave an odd number of heaps of size one (in normal play, the correct move would be to leave an even number of such heaps).

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

        It is called misère in there

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

How to solve A ? I am getting a WA on test 5. Submission.

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

    You need to compute the answer modulo 109 + 7.

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

      Wouldn't it get TLE anyway? It's O(n2). What's a better solution?

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

        two pointers maybe? (Lol i was typing "two painters" by mistake)

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

    May not be the best solution, but you can solve using seg-tree with lazy propagation. For a height 'X' the number of ways is sum of number of ways of reaching height 'X-i' where 1<=i<=MaxJump . You can view this in a slightly different way that ways[X] will be added to ways[X+i] for i in the same range. Consider this as a range update (you can find the range indices using binary search) . Finally find the value of the last leaf of segtree, which is the answer.

    If there is a solution better than O(n*logn), please do post your solution.

    Code : http://ideone.com/gnBviP

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

      two pointers :| http://paste.ubuntu.com/11446865/

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

        I didn't understand solition, please explain in simple words. I know about two pointer

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

          we know that dp[i] gets updated from dp[j] and dp[j+1] and ... dp[i-1] let's name this j az up[i] we know that if i < k -> up[i] <= up[k] so up[i-1] <= up[i] so we just need to move forward from up[i-1] to find the place that has less than m distance from i and that's that

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

      Another linear solution:

      Suppose dp[i] stores the number of ways to reach the ith step, and sum[i] stores sum of dp[0] to dp[i]. Also, you can store the cumulative sum of all the stairs uptil ith position in, say y[i]. now, you just need to search for lower_bound(y[i]-m) in the array y, and dp[i]=sum[i-1]-dp[lower_bound-1].

      http://ideone.com/jnj6zv

      Note: instead of calling lower_bound each time, you can preprocess the lower_bound indices in O(n) and calculate the dp and sum arrays in O(n).

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

        Your solution is actually the same with Reyna's.

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

          i only realized that after posting my comment. I hadn't refreshed my page since a few minutes :)

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

any updates on the new time of rescheduled round??

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

OK, so I will try to elaborate a bit more why organizing event at this hour is wrong and how it could be improved.

Firstly, we will use quantity argument. Look at the standings table. Keep in mind that this was middle of the night for Europe/West Asia. Scheduling hour of contest as such does good only for people from America (Northern and Southern). I just counted and there were about 14 people competing from those countries (USA, Argentina, Canada, Brazil, Dominicana and Cuba counted :P). And best of them was on 41st place. Does this really has any sense scheduling contest on that hour, making favor for that incredibly small amount of people and forcing about 200-300 not to sleep before 6/7AM? Moreover many people won't compete, so this competition kinda changes from "who is better programmer?" to "who can stay woken up longer?" and make results not reliable. Btw people competing at that hour have much smaller abilities, normally I would treat being unable to solve D as serious mental disability, but I managed to fail this either way :P (it was 5 AM >_>).

Considering people from America — isn't hour as one first contest was held at comfortable for them? If I'm not mistaken it's 1PM, so it superfine. 8PM in Poland/9PM in Moscow seems to be very good hour for people all around the world. Maybe for East Easia it is not that comfortable, so we can shift it 3 hours earlier. It is 9 AM in San Francisco and 1AM in Tokyo, so I think it's really fine. Given this — choosing hours 3 PM, 6PM, 9PM in Moscow would be the best option, because in that form everyone in whole world has at least 2 chances to compete in fine hours and amount of competitors such that they cannot compete 3 times not in the middle of night is much smaller than it is now.

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

    winger lives in USA, and he is on the third place.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Not all of the competitor who live in America represent it on the competition, so this count is not really perfect.
    2. 9 AM can be a bit early for some people, especially for the ones that got used to wake up at 10-11 AM.
    → Reply