Последнее обновление: решение за O(n) динамическим программированием
Здравствуйте! Задача 736. Удаление с acmp.ru. Суть задачи: на каждой итерации из массива длины n до 5·106 удаляются элементы с индексами k, 2k, 3k и т.д. Затем все неудаленные элементы сдвигаются и операция повторяется до тех пор, пока длина массива не станет меньше k. Нужно для каждого элемента во вводе сообщить, каким по счету он уйдет.
UPD: Решено за O(q * sqrt(n))
. Решение Wild_Hamster
UPD2: Так как задача находится в теме "структуры данных", то авторское решение использует некую хитрую структуру данных, которая укладывается и в предел по времени, и в предел по памяти. На это же и намекают лучшие попытки к задаче: там есть решения с 39 МБ и 59 МБ по памяти.
Попробовал сдать код деревом отрезков за O(n log(n))
. На acmp.ru — Memory Limit Exceeded (на ideone.com 0.780 с, 84 MB)
UPD3: Написал код деревом Фенвика за O(n log(n))
. На acmp.ru — Time Limit Exceeded на 19-м тесте. (на ideone.com 0.480 с, 40 MB).
UPD4: Решение динамическим программированием за O(n)
: можно решать задачу на префиксе количества итераций, совершенных алгоритмом. Для того, чтобы дать ответ, нам для каждого элемента нужно определить, на какой итерации алгоритма он будет удален, и какому элементу на предыдущей итерации он эквивалентен и использовать уже посчитанный ответ для этого элемента.