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
Any news on the Java support?
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.
imho, such information worth being stated in the blog above or/and in yandex.contest clars
Good point, I will add it above.
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.
Thanks a lot!
Auto comment: topic has been updated by Lewin (previous revision, new revision, compare).
Why Kotlin is not supported?
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...).
OK, I have managed to get in via another account.
X is missing
Added. Next time will check it twice.
>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.
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.
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.
Yeah, I didn't get it either.
You may want to add "visiting clist.by" to your daily routine.
Elimination stage ranking has beed updated.
how to solve C?
i tried to do it with pattern matching instruments of java, but got TL
What it is the test №7 in the task С?
I had WA7 and had bug with this test:
Nop.
bbccbcaccb
1
1 6 bb*
Yes
bbccbcaccb
1
1 6 bb*c
How to solve C?
EDIT : My approach was same as the editorial. Can anyone explain why I am getting Wrong answer for this code?
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.
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.
How to solve F?, I couldn't find any solution better than n2
The editorial has already published
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?
Участник располагается выше в итоговой таблице отборочного этапа, если имеет:больше зачетных очков;меньше минимальное занятое место за четыре раунда отборочного этапа при равенстве зачетных очков.а кто выше в случае равенства перечисленных показателей?
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.
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.
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.
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.
Thanks for the problemset. I liked it, especially problem B
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.