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.

The people who qualified earlier in the warm-up round, can they participate in this round too? Will this performance affect their qualification?

"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. :)

All can compete in the qualification round. Good luck and have fun!

When will The editorials be posted or when will they reveal test cases?

The editorial will be posted on Monday.

Are Indians eligible for internship opportunities and participation in the contest ?

Sure.

Can someone explain what is the difference of the blind and open submission?

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/Yseconds, where X is the number of contestants that didn't solve this problem and Y is the total number of contestants."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".

Type something like "Yes", "Sure", "I would be happy to" =)

I forgot my password and the answer of my security question! Is it possible to restore my password?

How to solve F?

In case radar isn't at integer distance from some point — we can move it further from this point without losing score on this particular point. Therefore there exists a solution in which radar is at integer distance from some point.

Now in the same way by moving a radar over some circle we can show that there exist solution in which radar is at integer distance from two points (unless we have N=1 in the input).

Therefore we have a set of interesting locations to check: take a circle of integer radius R1 with center at point p1, a circle of integer radius R2 with center at point p2, intersect them :) Our set is clearly finite — you don't need to check some R which is too big, because in such case your location will be too far from all points. In case your location is at distance more than 4 from each point, your best possible score is 20/25, and that's clearly not an answer (you can get at least 1 by placing radar at some point from input), therefore your location should be relatively close to at least one point from input.

And +27 by mmaxio make me think that one can make some random/locopt solution get AC as well :)

That's what I wrote... and got WA. Geometry problems.

Hint: you have a bug

Yeah, that's what I figured. Geometry problems: practically impossible to not make several bugs (I fixed one during the contest).

Lol. This is how editorials for geometry problems should look like.

Is the editorial posted somewhere?

What's the solution for problem C?

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.

Awesome, thanks for a very clear explanation!

If 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.

Thanks!

What's D's solution?

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)`

.can you share the code ?

ofc

Thanks

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.

Im sure you have LongLong overflow (:

Yeah probably... just thought I triple checked for that. I'll check a fourth time

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.Did you log in to your account? For some reason, it shows this message to people who aren't logged in.

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!

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...

A link appeared: https://contest.yandex.ru/algorithm2016/contest/2529/enter/

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 -_-.........

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.

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.

Actually I'm not sure that was the violation. Maybe both of my submissions turned OK after they fixed the test.

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..

Probably they used a bit different algorithm which didn't need input to be sorted.

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.

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".

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.

"a very small number" means something much smaller than 192 (the number of tests in B today)

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.

Sure, we will pay more and more attention to details (I hope to every one).

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.Fibonacci string works for small

n. Does it work for biggern?It works.

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.

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).

+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.).

Yes, we will translate all clarifications from this round (in short time), and in next rounds all admins will answer both languages.

Will the editorial be posted for round1?

We will post it tonight or tomorrow.