### Chmel_Tolstiy's blog

By Chmel_Tolstiy, 7 years ago, translation,

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.

• +138

 » 7 years ago, # |   +10 The people who qualified earlier in the warm-up round, can they participate in this round too? Will this performance affect their qualification?
•  » » 7 years ago, # ^ |   +3 "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. :)
•  » » 7 years ago, # ^ |   +23 All can compete in the qualification round. Good luck and have fun!
 » 7 years ago, # |   +3 When will The editorials be posted or when will they reveal test cases?
•  » » 7 years ago, # ^ |   +13 The editorial will be posted on Monday.
 » 7 years ago, # |   +3 Are Indians eligible for internship opportunities and participation in the contest ?
•  » » 7 years ago, # ^ |   +3 Sure.
 » 7 years ago, # | ← Rev. 2 →   0 Can someone explain what is the difference of the blind and open submission?
•  » » 7 years ago, # ^ | ← Rev. 5 →   +10 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.
 » 7 years ago, # |   +8 "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".
•  » » 7 years ago, # ^ |   0 Type something like "Yes", "Sure", "I would be happy to" =)
 » 7 years ago, # |   +13 I forgot my password and the answer of my security question! Is it possible to restore my password?
 » 7 years ago, # |   +5 How to solve F?
•  » » » 7 years ago, # ^ |   0 That's what I wrote... and got WA. Geometry problems.
•  » » » » 7 years ago, # ^ |   +21 Hint: you have a bug
•  » » » » » 7 years ago, # ^ |   +6 Yeah, that's what I figured. Geometry problems: practically impossible to not make several bugs (I fixed one during the contest).
•  » » » » » 7 years ago, # ^ |   +29 Lol. This is how editorials for geometry problems should look like.
 » 7 years ago, # |   +19 Is the editorial posted somewhere?
 » 7 years ago, # |   0 What's the solution for problem C?
•  » » 7 years ago, # ^ |   +4 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.
•  » » » 7 years ago, # ^ |   0 Awesome, thanks for a very clear explanation!
•  » » » 7 years ago, # ^ |   +19 but I think optimizations such as memoizations can reduce the complexityIf 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.
•  » » » » 7 years ago, # ^ |   0 Thanks!
 » 7 years ago, # | ← Rev. 2 →   0 What's D's solution?
•  » » 7 years ago, # ^ |   +3 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).
•  » » » 7 years ago, # ^ |   0 can you share the code ?
•  » » » » 7 years ago, # ^ |   0
•  » » » 7 years ago, # ^ |   0 Thanks
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   0 Im sure you have LongLong overflow (:
•  » » » 7 years ago, # ^ |   0 Yeah probably... just thought I triple checked for that. I'll check a fourth time
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   +5 Did you log in to your account? For some reason, it shows this message to people who aren't logged in.
•  » » » 7 years ago, # ^ |   0 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!
 » 7 years ago, # |   +25 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...
•  » » 7 years ago, # ^ |   +5 A link appeared: https://contest.yandex.ru/algorithm2016/contest/2529/enter/
 » 7 years ago, # |   +82 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 -_-.........
•  » » 7 years ago, # ^ |   +3 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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +11 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.
•  » » » » 7 years ago, # ^ |   0 Actually I'm not sure that was the violation. Maybe both of my submissions turned OK after they fixed the test.
•  » » 7 years ago, # ^ |   0 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..
•  » » » 7 years ago, # ^ |   +16 Probably they used a bit different algorithm which didn't need input to be sorted.
•  » » 7 years ago, # ^ | ← Rev. 3 →   +77 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".
•  » » » 7 years ago, # ^ |   +10 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.
•  » » » » 7 years ago, # ^ |   0 "a very small number" means something much smaller than 192 (the number of tests in B today)
•  » » » 7 years ago, # ^ |   +7 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.
•  » » » » 7 years ago, # ^ |   +11 Sure, we will pay more and more attention to details (I hope to every one).
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   +20 Fibonacci string works for small n. Does it work for bigger n?
•  » » » 7 years ago, # ^ |   +25 It works.
 » 7 years ago, # |   +42 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.
 » 7 years ago, # |   +20 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).
•  » » 7 years ago, # ^ |   0 +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.).
•  » » 7 years ago, # ^ |   +10 Yes, we will translate all clarifications from this round (in short time), and in next rounds all admins will answer both languages.
 » 7 years ago, # |   +13 Will the editorial be posted for round1?
•  » » 7 years ago, # ^ |   0 We will post it tonight or tomorrow.