[Обновлено]: удаление k-ых элементов из массива длины n пока в нем не меньше k элементов

Правка ru11, от dmkz, 2018-06-28 17:38:26

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

Исходный код
Теги структуры данных

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru11 Русский dmkz 2018-06-28 17:38:26 19
ru10 Русский dmkz 2018-06-28 17:35:44 1595
ru9 Русский dmkz 2018-06-27 16:52:33 89
ru8 Русский dmkz 2018-06-27 16:31:38 8
ru7 Русский dmkz 2018-06-27 16:30:02 351
ru6 Русский dmkz 2018-06-27 16:10:42 20
ru5 Русский dmkz 2018-06-27 16:10:15 195
ru4 Русский dmkz 2018-06-27 14:50:23 126
ru3 Русский dmkz 2018-06-27 02:41:27 393
ru2 Русский dmkz 2018-06-27 02:25:54 1390 Мелкая правка: 'вствуйте! [736. Уда' -> 'вствуйте! Задача [736. Уда'
ru1 Русский dmkz 2018-06-27 00:10:12 1425 Первая редакция (опубликовано)