Завтра, 6 августа 2015 года в 13:00 МСК. состоится финальный раунд Яндекс.Алгоритма, в котором 28 лучших участников будут соревноваться за призовой фонд в размере 540 000 рублей.
Следить за ходом соревнования можно будет на сайте Яндекс.Алгоритма.
UPD И мы поздравляем tourist с убедительной победой! Второе место занимает Petr с третьим местом поздравляем eatmore!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Будет ли онлайн зеркало?
Если и не одновременно с финалом (мало ли, чтобы не упало ничего), то было бы круто сразу после него, пока финалисты не успели заспойлерить в обсуждении все, что можно.
Обязательно начнем сразу после окончания раунда!
заходите на страничку соревнования и вы сможете поучаствовать виртуально
Когда ждать разморозки?
Можно послать свои сабмиты в дорешку. У меня упала C из-за тупейшего бага, остальные прошли.
Нда, у меня E по ТЛ упала и F по WA.
Не очень понятно, как может упасть F. Я пробовал вносить в своё off-by-one баги — сразу первый сэмпл становился SHUFFLED.
Есть набор багов, которые можно допустить в решении с перебором seed-а, соответствующего числу. Например, неправильный wrap-around для uint32 или (как раз и случившееся) неправильное округление при целочисленном делении. Тесты 61-72 ловят как раз такие ошибки.
Ещё можно написать вероятностное решение с недостаточной вероятностью правильного ответа.
А, я кажется понял. Имеется в виду решение, которое перебирает сид, соответствующий первому числу, а потом генерирует всю последовательность.
Я до него не додумался, и вместо этого перебирал сид, соответствующий каждому числу, и проверял, получается ли правильное следующее число. Поэтому у меня тестировался сразу перебор сида на 25000 кейсах в первом примере, и все баги ловились.
Эти баги происходят, когда результат вблизи ( ± 1) от сида равен
0или99999999, так что вероятность 10 - 8. На случайном тесте, даже если это делать в каждой из 105 точек, получается всего лишь около 10 - 3 вероятность напороться.Хм, извини за тупняк, но всё ещё не понял, что особенного происходит рядом с 0 или 10**8-1. Можешь привести пример кода?
Если неправильное округление при целочисленном делении, то вероятность порядка 1/43, так как ошибка при любом сиде может случиться?
Из пойманных багов:
1: x1 = s·108 / 232, значит,
. Можно написать
s = (x_{1} << 32) / 100000000 + 1в целых числах и поймать баг, когда делится нацело (а это происходит, когда x1 = 0).2: Можно завести переменную
sтипаuint32, перебирать, пока s ≤ (x1 + 1)·232 / 108 - 1, и получить вечный цикл при x1 = 99999999.А как C решается?
Стартуем с дроби со знаменателем 2 и всякий раз будем брать знаменатель, равный наименьшему простому делителю числителя предыдущей дроби (если такой знаменатель уже был на i-м месте, то ответ — цепочка от i-го места до текущего). И не позднее, чем через P(N) простые числа закончатся, так что повторение неизбежно. Максимальная длина цепочки — P(N).
Будем рассматривать только дроби с простыми d, заменим каждый u на любой простой делитель. У нас получилась функция, в ней надо найти цикл
Еще минут 5
Как-то в три часа ночи правильно прочитать уведомление пе получилось. Увидел "можно выводить произвольное число, а не ровно N/10", подумал "ну в условии же так и написано: любое не больше N/10, ничего не поменялось". FAIL. Правда, не очень-то и помогло бы.
When did tourist not win onsite finals?
VK Cup 2012, IOI 2012.
By the way, I would not call this round 'onsite'.
Today.
FBHC 2013
All-Ukrainian Olympiads in Informatics 2015
Возможно я что-то не понимаю, но 31 июля мне пришло письмо такого содержания:
Hello Jacob Dlougach!
The final round of Yandex.Algorithm-2015 is sheduled for August 8, 13:00 MSK and will last for 100 minutes.
С тех пор больше писем не приходило, и я был в полной уверенности, что контест будет 8-го...
Мне такого письма вообще не приходило. Враги какие-то прислали
Хо-хо-хо. А в русской версии так:
Здравствуйте, yeputons!
Финальный раунд Яндекс.Алгоритма-2015 состоится 6 августа в 13:00 и продлится 100 минут.
Удачи! Команда сервиса Яндекс.Contest.
Это просто отсеивание нерусскоязычных участников, как на VKCup :D
Привет! Действительно, произошла опечатка с моей стороны. Мне очень жаль, что так произошло. Подложенная под дату и время ссылка на timeanddate даже указывает на правильное время (я действительно сделала эту опечатку непредумышленно)
Я конечно заинтересованное лицо, но если все так и было, то казалось бы однозначно контест нужно переигрывать?
В результате оффлайн-обсуждения было замечено, что в согласии финалиста была правильная дата, и его нельзя было не подписать, так что пожалуй возражение снимается.
Кажется, не подписать его как раз можно: в правилах и в согласии упоминание этого согласия есть только в разделе 10 правил про призы. Предоставить подписанное согласие надо в срок до 14 календарных дней после подведения результатов. С другой стороны, рассылали и просили его подписать до конца июля, конечно, но именно что "вежливо просили", а не "по правилам надо".
The finals problemset authors:
GlebsHP A,D
Endagorion B
snarknews C
misof E
Gassa F
For those who don't read Russian comments and didn't notice: there's virtual participation available now.
How to solve C if you can choose at most N/10 fractions?
I was wondering why this constraint was removed.
First version of the problem had no constraint related to powers of prime as denominators, instead it had N/10 and N was between 10^5 and 2*10^5 (and no readable sample, because of this limitation). For these N number of primes P(N) is not exceeding N ~ N/10.
With both of these constraints for small N, when P(N)<N/10 exists sets of fractions where such a selection is impossible.
Unluckly, some necroediting happened and constant was returned in the new version.
А разбор задач будет?
уже совсем скоро в блоге Яндекса на Хабре
В разборе по A какая-то нереальная жесть написана.
Отсортируем точки по иксу, а при равенстве по убыванию игрека, и сложим в обычное одномерное дерево отрезков по этому порядку, которое умеет находить левый максимум на отрезке. Дальше просто поддерживаем множество активных точек в хипе по приоритету, и при удалении точки достаём новые точки на границе с помощью дерева отрезков, всё в сумме за O(nlogn).
В разборе написано решение жюри. Твоё решение проще и быстрее, но о нём мы узнали только из твоего сабмита :)
can anyone tell the difference between check sign and plus sign (on standings) ?
Check means OK after blind submission
как там дела с футболками? 2 месяца назад было письмо с просьбой заполнить форму с адресом в течение месяца, и с тех пор тишина...
начнем рассылать футболки в середине августа, следите за новостями в почте
It seems that for third year in a row Petr failed one of his "blind" submissions preventing him to claim the first place: 2013, 2014, 2015.
For third year in a row it is problem C :)
How to solve problem A?
I find a tutorial in the site:https://habrahabr.ru/company/yandex/blog/264253/,however it's in Russia.The English version translated is not clear.