5 августа 2016 в 22:00 (время московское) открылся первый этап SnarkNews Summer Series 2018. Как и несколько предыдущих серий, SNSS-2018 пройдёт на системе Яндекс.Контест. Опубликовано расписание серии.
По просьбам участников отдельно публикую ссылку для регистрации и входа в первый раунд. В комментариях к этому сообщению по окончании раунда в соответствии с расписанием можно будет обсудить задачи первого раунда. Напоминаю, что первый раунд заканчивается в 22:00 московского времени 14 августа.
Можно год поменять на 2018, а так задачи интересные!
Как решается задачи C и A ? Вроде простые задачи ,но решить не смог .
В С ответ — это верхняя целая часть квадратного корня из n А решается динамикой с мемоизацией с обработкой одного шага за корень
Ясно ,спасибо большое !
Для понимания задачи C и почему там такой ответ можно решить аналогичную задачу Div2C codeforces
Если не понятно, как в A вычислять значение для конкретного n за корень, то вот аналогичная задача E с образовательного раунда. В ней необходимо применить абсолютно тот же самый подход. В задаче же со снарка дополнительно понадобится быстрая хэш-таблица (или не понадобится, если схитрить и заметить кое-что интересное). Если писать на плюсах, то вот пост о быстрой хеш-таблице gp_hash_table.
Спасибо большое dmkz ! С удовольствием буду разбирать !
Должно ли в задаче D проходить решение за квадрат? То есть, получаем строки из поддеревьев в явном виде и сравниваем их. Мое проходит с временем 0.945 и памятью 37 МБ. Возможно, кто-нибудь сумеет подобрать контр-тест, который приводит к TLE или ML. Исходный код.
UPD: Возможно, это не квадрат, а O(n log(n)), так как чтобы произошло сравнение длинных строк, необходимо, чтобы у текущего узла было как минимум два поддерева одинаковой высоты максимальной высоты
Это O(n). После каждого сравнение двух строк одинаковой максимальной длины мы оставляем лучшую, а про вторую забываем. Забытой строке соответствует какой-то путь в дереве, и вершины с этого пути больше рассматриваться не будет. А так как всего у нас n вершин, то мы не можем забыть более чем n вершин, и все сравнения работают суммарно за O(n).
Вот только ваша реализация работает конечно же за квадрат из-за того, что строка явно возвращается:
Если строки явно не хранить (моё решение так и делает), это вообще работает за линейное время. Если мы в какой-то момент сравниваем две строки длины l, то одна из них больше никогда не поучаствует ни в каком сравнении. То есть сравнение длины l убирает l рёбер из рассмотрения. А рёбер всего линейное количество.
Большое спасибо, MrDindows, Gassa. Вообще я написал это решение только чтобы найти багу в решении с хешами, в итоге и линейное решение получил (осталось
std::stringпоменять наstd::list<char>), и багу с хешам исправил. Прикреплю заодно решение с хешами по модулю 261 - 1, может кому пригодится. Исходный код