2 августа 2016 в 14:00 (время московское) открывается первый этап SnarkNews Summer Series 2016. Как и несколько предыдущих серий, SNSS-2016 пройдёт на системе Яндекс.Контест. Опубликовано расписание серии.
По просьбам участников отдельно публикую ссылку для регистрации и входа в первый раунд. В комментариях к этому сообщению по окончании раунда в соответствии с расписанием можно будет обсудить задачи первого раунда.
А почему контест 80 минут, а не 100?
На SnarkNews Series контест всегда идёт 1:20. Это на Яндекс.Алгоритме время было увеличено до 1:40.
Странно... не помню, чтобы раньше было 80 минут.
Как решать B and E?
E: зафиксируем клетку, в которой мы окажемся после одного повторения маршрута. Эта клетка дает нам (dx,dy), на которые мы смещаемся за одно повторение программы. Отсюда мы можем сказать, что какая-то клетка (a,b) хорошая тогда и только тогда, когда клетки (a+k*dx,b+k*dy) тоже хорошие. Отметим все хорошие клетки, которые слева-сверху от (dx,dy), найдем по ним лексмин валидный маршрут из (0,0) в (dx,dy). Выберем лучший ответ по всем (dx,dy).
E. Зафиксируем, сколько ходов влево (
p) и сколько ходов вниз (q) в оптимальном ответе. Теперь заведём табличкуp + 1наq + 1, в которой мы хотим получить картинку периода. В этой табличке клетка(row, col)свободна, если на настоящей доске свободны все клетки(row, col),(row + p, col + q),(row + 2 p, col + 2 q)и так далее до самого края доски.Осталось в такой табличке найти лексикографически минимальный путь из
(0, 0)в(p, q). Это делается динамикой или жадностью.Edit: beaten by 1 minute :)
B не сдавал, но вроде должна решаться примерно так:
Построим суфавтомат по строке a1#a2#...#an. Дальше будем бинпоиском за O(|bi|·log(n)) искать места в суффмассиве, куда можно вставить строки bi и bi{ ('{' – символ идущий сразу за z). Будем считать, что мы сделали прибавление единицы на этом отрезке, потом все эти обновления можно обработать за один проход по массиву. Для каждого суффикса мы можем узнать к какой именно строке из исследуемого языка он относится.
Ну в B же в условии написано "Напишите Ахо-Корасик и посчитайте дп по нему."
Дело в том, что раньше я никогда не слышал про Ахо-Корасика и довольно часто слышал про существование структуры бор, но понятия не имел как она пишется (да-да, подготовка к АСМ на высшем уровне). На последнем раунде (внимание: спойлер!) в разборе одной из задач упоминается бор. Я пошел почитать про эту структуру данных на emaxx, чтобы решить эту задачу так (на самом раунде я написал нечто похожее на бор с использованием структуры map). Прочитав, я сразу понял, что бор + Ахо-Корасик (далее просто бор) могут решить задачу Б (к этому моменту я специально не стал читать решения Б и Е описанные здесь). Поняв это, сегодня, я решил задачу из последнего раунда бором, а после пошел писать Б, но меня терзали смутные сомнения. Краем глаза листая эту страницу я увидел упоминание суффиксного автомата (правда не известно к какой из задач: Б или Е), и подумал что бором не получится решить по какой-нибудь причине (сначала я думал на ТЛ). Когда написал, понял что для одной вершины я храню 57 интов, а так как вершин должно быть 26*len = 2.6кк = 600 МБ, я стал подозревать, почему бор — плохая идея. Но, на моё удивление, всё заработало затратив лишь 18 МБ (10 МБ после объединения массивов go и next).
P.S. Сейчас пойду читать условие Е (да-да, я заранее спросил как решается задача, условие которой даже не прочитал).
B: Построим Ахо-Корасик. В каждом состоянии посчитаем, сколько терминальных встречается на пути из него до корня по суффиксным ссылкам. Прогоним каждое из слов-запросов через него, на каждом шаге прибавляя значение из текущего состояния. Всё. Не понимаю, почему я здесь вижу уже третьего человека, которому здесь мерещатся суфф. структуры (ещё и две сразу, lol).
Спасибо за красивую задачу E!
(ну и стандартый whine про Xmx в Java, отличающийся от Memory Limit'а)
Почему точности вывода 8 знаков после запятой не хватало в A? Поменял на 15 и зашло. Решение с правильным n-угольником, вершины в точках r*cos(2*pi*k/n), r*sin(2*pi*k/n)
Кажется, сайт немного не обновлен. В разделе история последнее соревнование SNSS-2015 (SNWS-2016 пропущено). В разделе Tournaments — SNSS-2014 (три соревнования пропущено). Просто я в первый раз пишу SnarkNews Series, и иногда мне хочется посмотреть, как же кто выступал в прошлых годах. Из-за того, что это не очень удобно, становится немного грустно.
Тут надо обладать чувством прекрасного. В адресе сайта можно во всех местах поменять год и/или snss на snws. При этом при использовании интерфейса все может поехать.
Мм... Ну да, это выход из ситуации. Но куда что может поехать? Это ведь пара кнопочек. В чем может быть проблема? Кстати, только что заметил, что на птз тоже последняя пара сборов в интерфейс не вставлена.
Fixed (и на сайте SNSS, и на сайте karelia.snarknews.info).
О, замечательно! Спасибо!
В смысле можно открыть 2014 год, а кнопки (причем не все) все равно будут вести в 2016. Где-то такое было, сейчас не вспомню уже.
Кажется сайт немного поломан. Нельзя отправлять решения по задачам, которые сдал вслепую. В смысле, не только во время контеста нельзя, а вообще нельзя, прямо сейчас, например, я не могу отправить решение — поле для отправки заблокировано так же, как во время контеста блокируется после отправки решения вслепую.
Да, прошу прощения, сейчас должно работать
Как решать D, E, F во втором раунде? (Хотя по D я кажется почти придумал решение).
P.S. Да-да, я опять не читал условий и спрашиваю... Но поверьте, ваш ответ, во-первых, может пригодиться кому-нибудь другому, а, во-вторых, когда я пойду дорешивать задачи и даже если решу сам — ознакомлюсь с вашим решением (хотя скорее всего совсем что-нибудь сложное только с вашей помощью получится решить).
Статистика:
В топ30 SNSS1 — 2 человека с 4-я задачами, 9 человек решили всё.
В топ30 SNSS2 — 23 человека с 3-я задачами, 1 человек решил всё, 1 человек решил 5 задач.
В топ30 SNSS3 — 7 человек с 2-я задачами, 0 человек решили всё, 3 человека решили 5 задач.
А неадекватное повышение сложности — это тоже фишка SNS? Неадекватное, потому что и без того физически тяжело решить 6 задач за 80 минут, так еще каждый раз задачи сложнее становятся. Или главная цель — предоставить выбор что решать, а то что решить всё — невозможно, это уже второстепенное.
Ну вот требование "чтобы победитель сумел решить всё" действительно не обязательно.
В целом обычно первый раунд подбирается проще остальных (и тоталов там бывает изрядно), далее уже более-менее равномерно. Хотя иногда (скорее даже "довольно часто") получается, что фактически решают несколько не так, как предполагалось при составлении раунда.
В Петрозаводске нормальная ситуация, если победитель сдал половину. В чём проблема вообще?
Почему все обратили внимание именно на кол-во тоталов. Первоначальной претензией было количество участников в топ30 с наименьшим количеством задач и то что это наименьшее количество задач уменьшается. А количество тоталов я решил включить в статистику дополнительно.
А два раза давать самой простой задачей — геометрию, тоже нормальная ситуация?
Да.
более чем
Нормальная, особенно в третьем раунде
Про пятый раунд треда нет, поэтому спрошу тут. Как решать A с пятого раунда?
Сделаем топологическую сортировку лампочек, дальше идем с первой до последней и честно переключаем если не включена (таким образом включить можно все лампочки и понятно, что это будет единственный способ). Это будет решение за квадрат, чтобы влезло нужно заменить переключения на битсеты.