1 января 2016 в 20:16 (время московское) открывается первый этап SnarkNews Winter Series 2016. Как и несколько предыдущих серий, SNWS-2016 пройдёт на системе Яндекс.Контест. Опубликовано расписание серии.
По просьбам участников отдельно публикую ссылку на вход в первый раунд. Здесь же по окончании раунда в соответствии с расписанием можно будет обсудить задачи первого раунда.
Update2. В связи с тем, что отдельные участники не обратили внимания на то, что первый раунд идёт "некруглое" количество суток, завершение раунда перенесено на 20:16 10 января 2016. Напоминаю, что обсуждение задач закрыто до завершения возможного времени написания последнего стартовавшего, то есть до 21:36 10 января 2016.
Автокомментарий: текст был обновлен пользователем snarknews (предыдущая версия, новая версия, сравнить).
Как решать D? Аккуратно написанный DFS по состояниям "текущее положение — последние 3 перехода" заходит, или надо что-то более разумное?
Еще, кстати, интересно узнать стратегию интерактора :)
У меня зашел неаккуратный dfs по таким же состояниям, т.е. в нем я даже "тупо" пытался идти туда, откуда пришел. В дорешивание выяснил, что мое решение делает не более 30к действий.
Код
У интерактора никакой стратегии изменения лабиринта нет. Под динамическими тестами понималось перемещение финиша (в некоторых тестах, например в семпле, финиш фиксирован). В каком месте условия указывать что в тесте статическое, а что динамическое я пока не придумал.
Я пытался делать так. Переберём первые три хода. Теперь все рёбра раскрашены в цвета 1,2,3,4 и путь должен выглядеть как 123412341234... И можно делать поиск в глубину по состоянию (клетка, последний цвет). При таком подходе, кажется, маску хранить не нужно, достаточно только одного цвета.
Не зашло, на втором тесте не доходит до ответа. Баг или это и должно работать?
Вот второй тест: http://pastebin.com/FRUXsqn7 Ответ: DDRDLL Я сначала тоже хотел писать такое решение, но мне показалось, что при переборе первых трех ходов будет слишком много одинаковых ходов, так как цвета в первых трех цветов могут быть одинаковыми. Но решение должно работать, скорее всего в решении баг.
У меня именно оно зашло: http://pastebin.com/Xw30ecMX
"Выброшенные крупье и посетителем числа сортируются по убыванию. Затем сравниваются два наибольших значения. Если у крупье выпало большее значение, посетитель должен снять одну из своих фишек. Иначе одну из своих фишек снимает крупье. После этого, если оба игрока бросали более одной кости, по аналогичной схеме сравниваются два значения, следующих за наибольшими, и, соответственно, одна фишка у того или иного игрока снимается."
Can anyone translate this part? It was hard to understand.
Something like this:
Hope it helps.
Thank you.
Google Translate says: Then, if both players throwing a single bone, in a similar way compares two values, following the largest, and, accordingly, one piece at one or another player withdraws.
Somehow "more than" part is missing.
"более одной" значить "more than".
Google Translate не является идеальным при соревнованиях, он переводит очень плохо — и иногда смешно.
F как-то решается за чистую линию? Очень похоже на баян, который я пропустил.
Ну у меня зашло решения за O(N * |A| * |A|), где |A| — размер алфавита.
Какое решение? Можно поподробнее?
У меня за N * |A| решение. Каждый ход смотрим, обязаны ли мы ставить ту букву, которой осталось больше всех. Обязаны, если в наличии осталось нечетное количество букв (2*k+1), а той, которой больше всех, сейчас k+1 штука. Иначе ставим лексикографически минимальную. Ну и не надо ставить одну и ту же букву подряд.
Понятно, спасибо.
Вот я придумал такое же решение, но с деревом отрезков для максимума, то есть за O(N * log|A|), но интересно можно ли за O(N)
Видимо, можно за O(N + |A|2).
Мы выставляем обычно 2 минимальные буквы (из тех, что есть), но если есть буква, которой половина (+-1), то нужно начать выставлять её, чередуя со всем остальными (которые, очевидно, будут в порядке возрастания).
Значит в любой момент нас интересуют три буквы: 2 минимальных и та, которой больше всего. Нам надо узнать, какое из событий произойдёт раньше: одна из минимальных букв закончится или буква с максимальным кол-вом вхождений начнет "доминировать". Это можно сделать за O(1). До следующего такого события мы можем выставлять буквы за O(1). Событие "какая-то буква стала доминирующей" может быть только 1, событий "какая-то буква закончилась" не больше O(|A|).
Наверное, можно O(|A|2) еще соптимизить.
Можно за O(N + |A|): заведем массив векторов, в котором для каждого количества будем хранить номера символов для каждого символа при этом еще будем хранить пару, в каком векторе он находится и какая позиция у него в этом векторе
Теперь необходимо вычислять максимум (поддерживаем указатель на нужную непустую ячейку вектора)
И собственно ставить какой-то символ (ставим символ и благодаря вспомогательной информации обновляем наши вектора)
AC код
Как решалась задача E ?
Как решать E легко?
Мне ясная динамика (k, n, битмаск восможньих сумм 1..K) с
, но это очень медленно и мне было нужно оптимизировать много вещей.
Может быть, локально вычислить все количества коллекцией с L ≤ K? Их только 8000 и если они известны, то количества с L > K уже легко считать...
Эта динамика достаточно быстрая :)
Код.