dmkz's blog

By dmkz, history, 6 years ago, In Russian

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

Исходный код
  • Vote: I like it
  • +9
  • Vote: I do not like it