Сегодня прошел ежегодный открытый чемпионат Харькова. Очень хотелось бы узнать, какое решение проходило в задача G? Мои сокомандники клянутся, что написали божественную декартку, но она не проходила по времени. У кого-то вышло пихнуть ее?
Сегодня прошел ежегодный открытый чемпионат Харькова. Очень хотелось бы узнать, какое решение проходило в задача G? Мои сокомандники клянутся, что написали божественную декартку, но она не проходила по времени. У кого-то вышло пихнуть ее?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 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 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
HTTP/1.1 404 File Not Found
Оно только для избранных, наверное =(
Это линка для залогиненных участников) Должно работать, если вот так.
Как Н делать? Говорят — боян бояном, была в этом году в первый день украинского отбора на IOI, да и на CF есть, задача N. Такое можно делать Ахо-Корасик? Или с какой стороны к ней подходить вообще?
Да, еще эта задача была на Удмуртском опенкапе где-то месяц назад :) Там Ахо-Корасик по запросам. Дальше рассказывать? :)
H можно делать Ахо-Корасиком. Для начала создадим автомат из строк-запросов. После этого посмотрим на бор, который описан во входных данных. Будем его обходить дфсом и вместе с этим двигать текущую вершину в автомате. Единственное отличие от задачи поиска подстрок в тексте состоит в том, что для бора нам нужно будет иногда откатываться назад и помнить какая раньше была текущая вершина. Но, если текущая вершина автомата — параметр дфса, то рекурсивный дфс сам запомнит что и как было :)
Помимо этого, есть альтернативное решение с хешами. Заметим, что у строк-запросов может быть не более O(sqrt(N)) различных длин. Для каждой такой длины посчитаем все хеши по бору из входных данных. Отсортируем полученные хеши и двоичным поиском найдем количество вхождений хеша для строки-запроса. Итоговая сложность O(N*sqrt(N)*log(N)). Такое не заходило, получало ТЛ 6. Возможно, если переписать все на хеш-таблицу, то и зашло бы.
UPD: В тренировке по ссылке выше, решение за O(N*sqrt(N)*log(N)) проходит за 872 мс.
На отборе на IOI трюк с корнями тоже не зашел Т_Т
Спасибо. Не дошли еще руки до пропущенного из-за Харькова этапа Opencup)
Я тоже думал о решении с хешами — но говорят, что оно и не должно заходить.
У них есть какая-то дорешка? У меня не получается ее найти.
Задача H отсюда совпадает с G с чемпионата Харькова. Решать можно декартовым деревом. Понятно, что в каждый момент времени занятые числа разбиваются на отрезки подряд идущих. Для каждого такого отрезка можно хранить декартово дерево. Помимо этого, для того, чтобы определять какому декартову дереву принадлежит заданная позиция можно использовать систему непересекающихся множеств. После этого надо аккуратно написать добавление нового элемента в новую позицию.
Не решили эту задачу, но вроде так будет легче: поддерживаем декартово дерево, в котором изначально 2 * n нулей. Когда поступает запрос добавить число x на позицию pos, находим первый ноль справа от pos, удаляем его, и вставляем на место pos наше число x. Тогда в конце в декартке будет храниться ответ. Определять первый ноль справа можно поддерживая сумму спуском по дереву.
Да, видимо так будет проще. Сложность такая же, но спуск по дереву писать значительно проще, чем рассматривать случаи :)
У нас ровно такое упорно получало ТЛ23.
У кого-то вышло пихнуть ее?
У Михаила Добкина вышло.
Дорешка