Всем привет!
Уже сегодня, в субботу, 12 марта в 14:00 по московскому времени состоится пятая личная интернет-олимпиада для школьников. На этот раз помощь потребовалась жителям Зверополиса, мультфильм с которыми совсем недавно вышел на телеэкраны!
Продолжительность олимпиады — 5 часов. Не забудьте зарегистрироваться на цикл личных интернет-олимпиад в этом сезоне перед началом олимпиады, если вы не сделали этого раньше.
Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client (русская версия).
Олимпиаду для вас подготовили Илья Збань (izban), Дмитрий Филиппов (DimaPhil), Илья Пересадин (pva701), Дарья Яковлева (Devushka) и Григорий Шовкопляс (GShark).
По всем вопросам, возникающим во время олимпиады, просьба писать на [email protected].
Удачи!
Будет ли олимпиада добавлена в тренировки?
В С решение за N * колво_блоков * logN (что равно N * N * logN) заходит на 100. Кстати, как ее решать не за O(N sqrt N)? Еще интересно решение D на полный балл :)
Можно за O(N) если не ошибаюсь. code. Как D на 75?
FFT. #code
В С я решал за O(N). Перебирал кол-во шагов, которое сделает каждый ленивец и для каждого блока считал минимальное и максимальное число ленивцев(с фиксированным числом сделанных шагов), которых туда можно запихать. Суммирую эти значения и с помощью них обновляю ответ. Решение работает за O(макс_колво_шагов*колво_блоков), но можно заметить, что макс_колво_шагов <= N/колво_блоков. Таким образом, получается O(N)
Действительно... Я думал асимптотика N * кол_во_блоков, а кол-во различных блоков может быть sqrt(N), соответсвенно в сумме O(N sqrt N).
У меня тоже получилось N*колво_блоков=N^2, но можно было за N*log(N). Ищем блок, куда лучше всего запихать i-го ленивца, в зависимости от имеющихся уже ленивцев. Два придуманных алгоритма поиска валились на одном тесте. Тесты были разные и я запихал — в первом тесте был четный N, во втором нечетный...
Будет ли опубликован разбор задач?
А как А на сотню решать?
Посчитать gcd на суффексе и префексе, и перебрать удаляемый элемент