Буквально вчера завершился очередной ACM ICPC World Finals. Мы передаем наши поздравления всем победителям, медалистам и обладателям специальных призов!
Сегодня мы хотим напомнить, что завтра, 21 мая, в 00:00 (UTC+3) начнется квалификационный раунд Яндекс.Алгоритма. Для участия в квалификации вам следует зарегистрироваться и начать виртуальное соревнование в любой момент до 23 мая 00:00 (UTC+3).
Как и во всех раундах Яндекс.Алгоритма, будет предложено 6 задач различной сложности. Для того, чтобы квалифицироваться в отборочные раунды и сразиться за поездку на финал в Минск, денежные призы и футболки, необходимо решить хотя бы одну задачу.
В этом году специально для студентов Яндекс.Алгоритм предлагает поучаствовать в стажерском треке. Более подробную информацию о нем можно найти в правилах чемпионата.
Успехов! До встречи на Яндекс.Алгоритме!
P.S. Квалификационный раунд уже начался! Задачи подготовили Romka, Ixanezis и Chmel_Tolstiy.
EDIT. Опубликован разбор задач квалификационного раунда.
А если я уже прошел с тренировочного раунда, то можно ли будет участвовать вне конкурса?
Да, участвовать можно. Мы будем очень рады!
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!
Стажёрский трек — хороший привет VK Cup с их специфической политикой по участию. Спасибо что так!
Смысл сдавать задачу "втемную" в меньшем штрафном времени?
Если я правильно понял вопрос. Для квалификации в отборочные раунды нет смысла сдавать втемную и бороться за место как можно выше, но можно потренироваться перед основными раундами, где это может помочь попасть в финал или выиграть футболку.
Таким образом, в квалификации кажется логичным (лично мне) хоть одну задачу сдать в открытую, а на остальных уже решать, что делать.
А куда адрес для футболки писать? В форме регистрации только город есть :)
Для тех, кто выиграет футболку, будет разослано письмо с соответствующей анкетой.
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 / Y seconds, 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).
Как решить первую задачу? Я не совсем понял условию
Если b > p, выводишь - 1, иначе max(p, a + b).
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 bigger n?
It works.
Может у кого-нибудь 4 задача падала на 7 тесте(из первого раунда)?
В чем там проблема?
у меня падала на тесте 2 2 2. (правильный ответ — 8)
у меня его проходит и тоже ва7
А как её решать? Я смог собрать формулу, но она требовала считать комбинации порядка миллион из миллиона. Быстро не получилось, думаю было бы TLE в любом случае.
Задача вполне решалась с помощью формулы, в которой нужно считать Ank и Cnk из миллионов. Достаточно просто предпосчитать все факториалы и числа, обратные к факториалам. По крайней мере если все считать за линию, вполне укладывается в треть секунды.
Почему-то я с этим раньше не сталкивался, а сам сразу не сообразил.
Это и ещё забытая строчка:
if (place == 31) place = 1000;
в третьей задаче — и футболка стала пропадать с горизонта. Буду стараться в следующем раунде.
Там все за
O(n * log(n))считается. Один цикл доn, в теле которого считаются биномиальные коэффициенты заlog(n).В цикле перебираем количество пар, которые будем использовать как разделители групп. Перебор
ipот1доp. Посчитаем количество мальчиковtmи девочекtw, которые нужно теперь распределить по группам, просто вычтяipизwиm.Сперва предположим что слева будет спать девочка, тогда количество групп девочек будет
gw = (ip + 1) / 2, а групп мальчиков —gm = ip / 2.Теперь нужно посчитать сколько существует вариантов расположить ребят, чтобы использоватьipразделителей, а слева лежит девочка.Здесь:
С(n, k)— функция числа сочетаний изnпоkf(n)— факториал числаnC(tm + gm - 1, gm - 1)— количество способов разбитьtmмальчиков наgmгрупп.C(tw + gw - 1, gw - 1)— количество способов разбитьtwдевочек наgwгрупп.C(ip, p)— количество способов выбратьipпар-разделителей групп изpвозможных пар.f(tm),f(p),f(tw)— всевозможные варианты распределить объекты определенного типа на соответствующие места, количество места = количеству объектов.Считаем все еще раз, предположив теперь, что слева спит мальчик (просто поменяются
gwиgm).Предварительно нужно учесть два частных случая:
f(m)илиf(w).На каждую группу есть ограничения, например на кранюю это что количество в ней больше 0, а на внутреннюю это то что количество там больше 1.
Это учитывается?
На группы нет ограничений. В группах допускается нулевое количество элементов. Причем например если группа девочек с нулевым количеством элементов находится слева, то это означает, что на первой слева кровати будет спать девочка (из пары-разделителя). На границах соседних групп всегда будет либо край, либо мальчик и девочка какой-то пары-разделителя, которые мы уже не учитываем.
Когда мы выбрали
ip, остальные девочки и малькики из пар никак не отличаются от одиночек. Про пар-разлеители можно забыть.Да, я понял уже. У меня немного другая логика программы.
Можете код свой скинуть?
на этом тесте все ок
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.
Добрый вечер!
Правильно ли я понимаю, что футболки получит топ-512 отсюда(https://contest.yandex.ru/algorithm2016/) ?
И если так, то как формируется этот топ?
Участники сортируются по набранным очкам (ГП-30). А дальше по количеству решенных задач, при равенстве по убыванию штрафа.
Очки, задачи и штраф суммируются за все 3 отборочных этапа.
Таким образом будут определены финалисты, обладатели футболок и победитель стажерского трека.
Will the editorial be posted for round1?
We will post it tonight or tomorrow.