Lewin's blog

Round 2 of Yandex.Algorithm 2017
By Lewin, history, 8 years ago, In English

Hello everybody!

On May 27, 23:00 Moscow time, Round 2 of Yandex.Algorithm competition will take place. I wrote the majority of the problems in this contest, with some additional help from Zlobober.

I would like to thank Zlobober for all his help with coordinating this round, MikeMirzayanov for polygon, and of course, everyone who took the time to test this round.

Please note, the problems will be randomly arranged, so make sure you read everything during the round :)

If you are using Java, please submit using Java 7 x32.

See you in the competition soon!

UPD 1: Editorial here: http://codeforces.me/blog/entry/52223

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

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

Any news on the Java support?

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

    For this round specifically, I have reference solutions in Java for all problems. On Yandex, you may have to submit in Java 7 x32, since it seems my solutions time out in the other versions (Java 7 and Java 8 more specifically).

    I'm not sure about general support for other versions, it seems like a hard bug to track down.

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

      imho, such information worth being stated in the blog above or/and in yandex.contest clars

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

        Good point, I will add it above.

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

    We have the state of java compilers as it was several months ago. Java7_x32 runs in client mode (option -client) and runs in time +/- 20% of polygon runs (at least for the problems of this round).

    We will also send an announcement with the fastest java version in the contest system at the beginning of the round.

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

Auto comment: topic has been updated by Lewin (previous revision, new revision, compare).

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

Why Kotlin is not supported?

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

It says: "You cannot participate in the contest because the registration is closed" -- I am not sure whether this is simply because the contest has not started yet and everything is right, or whether I am using some wrong account (although it appears I am using a correct account...).

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

    OK, I have managed to get in via another account.

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

X is missing

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

>mfw in the middle of the contest
>mfw I submitted harder problems on blind and saw myself in 3rd place

UPD: And both failed. After a lot of local testing even. Awesome.

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

Lol, you definitely should send out reminders. I learned about this competition when it was already 10 mins into contest by randomly strolling on codeforces. I immediately told it to my friends, none of them knew that also.

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

    Hi! I'm terribly sorry you didn't receive the email. After round 1 reminder that went out too late I made sure to schedule the mailing exactly 24 hours before the round and even got my email fine. Thanks for raising the issue, I'll work with the mailing system to fix it.

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

    You may want to add "visiting clist.by" to your daily routine.

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

Elimination stage ranking has beed updated.

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

how to solve C?
i tried to do it with pattern matching instruments of java, but got TL

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

What it is the test №7 in the task С?

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

    I had WA7 and had bug with this test:

    bbccbcaccb
1
1 6 bb*
    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve C?

EDIT : My approach was same as the editorial. Can anyone explain why I am getting Wrong answer for this code?

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

    The start piece should match the entire prefix of the [l, r] substring, not just the first character if the pattern doesn't start with * (the same goes for the suffix and the last piece).

    Depending on the implementation details, the case when there're no * in the pattern might also be special.

    The general idea of your solution is correct.

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

B is nice!

For problem C I feel ashamed — somehow I thought it was a bitset task, but the intended solution is much simpler and better.

I've seen the "game part" of F in SRM 408 med. Though the other part looks hard enough.

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

    How to solve F?, I couldn't find any solution better than n2

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

      The editorial has already published

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

My approach for problem C: for all substrings of size less than or equal 10, map the substring to a vector of its starting positions then for each query binary search for the next string, I think it's O(n * 10 + q * log2.n). Is there any better solution?

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

Task E is probably obtained from task F from NAIPC 2017 (I have strong feeling about that). I don't object against such way of creating tasks; that's suitable for ordinary contests, like CF rounds or TC (of course, if solutions uses fresh ideas, different from the source).
BUT Yandex.Algorithm is an annual championship, for such competitions you need to use your best, most interesting tasks. I think so because some people solved NAIPC, some of them came up with this idea during the competition. So, today people who have seen this task had advantage.

UPD: apart from this, I find other tasks nice, especially B and F.

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

    I believe that the intended solution for the problem you mentioned was noticing that 10^18 is a small value and than carefully exploit that fact. Also, the problems are indeed different: there the number of elements of each color wasn't fixed, and the problem statement was to generate an object by a number, not vice versa, and that was why you could exploit the low constraints.

    The solution of this problem requires the calculation of an exact number of sequences without adjacent elements of same color. I don't know how to apply directly the DP from this problem to that problem, can you describe it?

    We knew about the problem you mentioned beforehand, but we decided that it didn't have any significant effect on our contest.

    Apart from it, kudos to Lewin.

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

      I understand solution for the task from NAIPC is different and in fact much easier.
      But still setups for both problems are very similar, and questions asked "find n-th lexicographical" and "find number in lexicographical order" are closely related.

      I believe many strong teams who solved NAIPC came up with this dynamic programming (for example, our team), that's pretty natural. I don't like situation "oh, I know how to solve this problem, I came up with this idea couple of month ago" in top-tier competitions.

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

        They may look similar, but they are about different combinatorial objects. In one of them you fix the correspondence between the colors and quantities, and in another you don't. Can you please elaborate how can the solution of this problem applied there or vice versa? I'm not even sure that the problem from NAIPC is solvable in polynomial time in general case.

        If these problems solutions are not related to each other then I completely disagree that it is wrong to give this problem in our contest. After all when you solve problem X and come up with a cool idea, that is not related to problem X itself but may be applied in problem Y, it is not an Y's author fault, it is your advantage and you are free to use it.

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

Thanks for the problemset. I liked it, especially problem B

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

Why does my this code gets WA test 39. I have done a simple simulation as suggested in the editorial. I am unable to detect the error. Please help.

→ Reply