Форум DL

Мой профиль

IOI 2016

day-1
То, что я начал поздно ничего не дало - в последние минуты контекста ничего придумать я не мог.
За пол часа сдал А.
Думал над B, но закономерностей не нашёл. Написал DP на 31 балл.
Затем пошёл писать C. Придумал O(n^3) на 38 баллов и написал. Пыталчя его оптимизировать, искать по чём можно было бы дихнуть, но нет - тоже больше не удалось взять быллов.
Проблемы: не придумал B на 64 балла (слышал, что там что-то с Эйлеровым циклом, но похоже скорее на Гамильтонов, плюс 2 * 10^5 вершин и до квадрата рёбер), не придумал оптимизацию хотя-бы до O(n^2) на C.

day-2
Быстро придумал A, но долго писал - такая уж там противная задача. Прочитал B, даже не сразу придумал квадратичное решение (подразумевается кол-во запросов - это интерактивная задача). За час до конца придумал решение, которое делает n*log(n)+n+log(n)^2 запросов. Стал писать, надеясь на то, что уложусь в n*log(n) за счёт отсекания лишних запросов. Это действительно экономило 53 запроса, но n+log(n)^2 утратило 138 или более, из-за этого не влезало (получил только 70 баллов, которые знал как взять проще, почти сразу после того, как придумал n^2), но, вроде-бы уже 5 часов прошло на тот момент. Правильное решение я пока не знаю, но там что-то с разделяй-и-властвуй, которое я придумать не смог, было на него похоже.

Мой профиль

Открытка 2026

Начну с того, что условия обоих дней довольно длинные и на их прочтение уходит много времени и нежелания в начале.

Day 1
Сдал B за 30 мин. D показалась длинной и сложной, поэтому сосредоточился на A и C. Долго думал над A, на C ничего хорошего придумать не получилось. Когда на 2-ом часу понял, что A - тоже гроб, пошёл читать D. Придумал dp за n^2, но до 3-его часа отлаживал. Затем стал думать над оптимизацией. Это было не сложно, т. к. Кирилл рассказывал этот алгоритм прошлым днём. Однако, из-за того, что я его никогда не писал, а также писал с багами, сдал D только в 4:59.
Если бы хватило времени, мог бы взять 30 и 31 балл соответственно на A и C (возможно больше), но хорошо, что я сдал D.

Day 2
Теперь самой лёгкой задачей была C, решил я её только через час. Затем в каком-то порядке брал частички по A, B и D. В B запихал кубический жадник на n <= 1000, но полное решение придумать не смог (решалась она довольно просто, но такого приёма, как представить брожение по полоске туда-сюда как цикл, я раньше не видел). В D была ещё одна dp, но оптимизацию на неё я придумать не смог. Это довольно понятно, ведь нужно было идти с конца массива, а не с начала. В конце взял 30 баллов на A, но придумал ещё одну подгруппу на 15 баллов, которую не успел написать.

В общем:
Мне не хватило времени. А ещё я ожидал, что задачи будут более стандартными, как в том году. Конечно, я умею решать и такие, но к ним нужен немножко другой подход, а я пол олимпы просто искал закономерности в дп и пытался оптимизировать квадратичные решения.