Форум 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 часов прошло на тот момент. Правильное решение я пока не знаю, но там что-то с разделяй-и-властвуй, которое я придумать не смог, было на него похоже.