Всем привет!
В это воскресенье, 21 января, мы начинаем сезон личных интернет-олимпиад — в 16:00 по московскому времени состоится первая личная интернет-олимпиада для школьников, которая также будет являться первым отборочным туром ИОИП. Вам предстоит помочь подросткам, попавшим в игру Джуманджи, со всеми возникшими у них трудностями.
Продолжительность олимпиады — 5 часов. Не забудьте зарегистрироваться на цикл личных интернет-олимпиад в этом сезоне перед началом олимпиады, если вы не сделали этого раньше.
Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client.
Олимпиаду для вас подготовили подготовили Илья Збань (izban), Николай Будин (budalnik), Александра Дроздова (demon1999), Михаил Анопренко (manoprenko), Дмитрий Филиппов (DimaPhil) и Григорий Шовкопляс (GShark).
Также спасибо Ильдару Гайнуллину (300iq) за помощь в тестировании задач.
Удачи!
It smells like long adventrure
Извините, а это нормально что я зарегестрировался, но не могу зайти на PCMS@ Web Client?
Мало просто заполнить форму, еще необходимо дождаться подтверждения регистрации.
тут можно посмотреть статус...
Проблемы с доступом к PCMS? Просто добавь 2 и получи PCMS2...
Можно ли писать не школьникам вне конкурса?
У вас тоже не грузиться?
Да
Я зарегистрировался после начала контеста, и я не могу войти в PCMS. У всех так? UPD: Зашел
Подскажите, где найти условия задач? Возможно, у меня проблемы с отображением некоторых ссылок.
Пожалуйста
Спасибо!
Как решать д?
Воспользуемся динамическим программированием.
У нас ДП такая: dp[v, k, flag], где v -- вершина, k -- количество
гепардовягуаров, которых мы хотим поставить в поддереве с вершиной v, flag -- флаг, он обозначает следующее:гепардаягуараНачальные значения: dp[v, 0, 0] = dp[v, 1, 1] = 0.
В самом конце подсчета динамики для заданного v мы увличиваем все значения dp[v, k, 1] и dp[v, k, 2] на значение энергии в вершине v.
Как делать пересчеты? Мы добавляем функцию merge, которая добавляет сына к ответу. Она работает за O(k1·k2), где k1 -- размер дерева, которое у нас уже есть, а k2 -- размер поддерева сына. Таким образом мы добавляем к нашей вершине v сыновей по одному.
Можно доказать, что такая динамика работает за O(n2).
Как она пересчитывается, смотрите код для лучшего понимания.
Может быть тогда кто-нибудь поделится идеями решения на полный балл C и B? Хеши в третей задаче у меня зашли только на длины строк до 10^5.Что дальше? Из предположений только алгоритм Манакера, но может быть можно какое-нибудь ДП насчитать?
В третьей да, Манакер. Конкатенируешь строку два раза, далее нужно найти наибольший палиндром, не превосходящий длины строки. Это делается так: находим наибольшие палиндромы четной и нечетной длин, затем их уменьшаем, пока они не станут не больше длины строки. Потом ищем максимум из них.
Во второй надо все IP-адреса перевести в
uint64
-числа. Затем ответ магическим образом оказывается равен b - a - 1 - k, где k — количество IP-адресов i таких, что a ≤ i ≤ b. Осталось проверить случай, когда это невозможно (между a и b нет подряд идущих).Спасибо. В плане третьей всё понятно. Вопрос по второй: я так понимаю, что под uint64 подразумевается не unsigned long long. Если так, то можно чуть подробнее об этом / ссылку на какой-либо материал по данному типу?
uint64
это, по сути,unsigned long long
(64-х битный беззнаковый). Я написалuint64
, чтобы было без привязки конкретно к языку C++.А вообще, я не любитель
long long
и всегда используюint64_t
иuint64_t
вместоlong long
иunsigned long long
соответственно (если это возможно).Видимо, что-то всё-таки понял неверно. Во-первых, при вычитании у нас могут появиться маски, по типу 999, которые больше 255. Во-вторых, x <= 8, т.е. длина числа будет 8 * 3 = 24, что, в свою очередь, больше ограничений типа.
x ≤ 8, каждое число по 8 бит, значит, все поместится в 8 * 8 = 64-х битный тип.
Мы преобразуем IP-адреса в
uint64
-числа таким образом. Самую правую часть адреса мы помещаем в младшие 8 бит, следующую слева от нее -- в следующие в 8 бит и так далее. При таком преобразовании каждое число меньше 28x будет соответствовать валидному адресу и наоборот.Если попробовать убрать лишние взятия остатка от деления, то на 100 заходят хеши.
Можно подробнее по этому поводу? Старался делать как можно оптимальнее и лишний раз не брать по модулю. Или может быть дело в том, что я считаю всё в long long?
При сумме/разности по модулю можно использовать следующий трюк: вместо
a = (b + c) % MOD
писать как-то так:Утверждается, что, если
a < MOD
иb < MOD
, то такая конструкция отработает быстрее.С разностью нечто похожее.
Да, это понятно. Но не совсем понимаю, как этот метод применим к коду выше. Во всех случаях используется умножение, где в любом случае нужно брать остаток от деления. Мне кажется, что будет быстрее загнать сумму/разность под это же взятие остатка, т.к. один раз нам всё равно придётся это сделать. Разве не так?
Остатки от деления надо брать поменьше, так что любое избавление от них полезно. Можно еще дальше подумать и пооптимизировать.
В общем, полный простор для воображения :)
Можно еще попробовать хэши по модулю 264 и надеяться, что анти-хэш тест авторы не нагенерили (скорее всего, это так).
Нет, там в подгруппе на 45 баллов было 1-2 теста на uint64(
И можно избавиться от ненужных ифов, если сделать нумерацию не с нуля, а с единицы.
Добавьте контест в тренировки.
Уже: http://codeforces.me/gym/101703
Кто прошёл первый отборочный тур??