Поиск оптимальной позиции ловушки

[trozki_187]

Есть прямая канализация, состоящая из $L$ секторов, каждый сектор пронумерован и нумерация стартует с нуля.
В канализации находится $N$ призраков, в каждом секторе канализации может быть не более одного призрака.
Имеется две последовательности $ A $ и $ B $, $A[i]$ содержит в себе номер сектора, в котором находится призрак, $B[i]$ содержит в себе жизненную силу призрака $A[i]$.
У нас есть одна ловушка для приведений, которая может ловить столько призраков, сколько позволяет её заряд энергии $E$.
Мы можем расположить ловушку в любом секторе канализации.
Стоимость поимки одного призрака рассчитывается по формуле [жизненная энергия призрака $ \times $ расстояние от призрака до ловушки], расстояние от призрака считается как разница между номерами секторов канализации. То есть, если ловушка стоит в нулевой ячейке, а призрак с жизненной энергией $2$ стоит в третьей ячейке, то стоимость его поимки $2\cdot(3-0) = 6$.
Надо вычислить максимальное количество призраков, которое мы можем поймать в ловушку.
Ограничения: $10 \leq L \leq 10^8$, $1 \leq N \leq 10^5$, $ 1 \leq E \leq 10^8$, $0 \leq A[i] \leq L-1$, $1 \leq B[i] \leq 100$

Мои наблюдения и мысли:
Скорее всего, нужно использовать префиксные суммы для решения задачи за оптимальное время. Завести цикл по всевозможным позициям и за константное время посчитать максимальное
количество призраков, которых можно поймать, используя посчитанные ранее префиксные суммы (возможно, нужны массивы для количества призраков от 0 до i-го сектора или их общая цена посчитанная по формуле из задачи при условии что ловушка сидит и в 0 и т.д.) Непонятно, каким образом считать количество призраков при заданной позиции ловушки и ограничении на общую цену сверху ($E$) за константное время. Возможно, наблюдения завели меня совсем не туда.

Спасибо всем за помощь!

[Ende]

Тема перемещена из форума «Олимпиадные задачи (CS)» в форум «Computer Science»
Причина переноса: в олимпиадном разделе размещаются задачи, решение которых известно топикстартеру, но он предлагает другим участникам попробовать свои силы в поисках этого решения.

[Cash]

Если сместиться вправо на один сектор, то целевая сумма изменится на суммарную жизненную силу привидений слева минус суммарная жизненная сила привидений справа. Отсюда уже очевидно, где надо располагать ловушку - там, где эти части примерно равны.

Upd. Ох, на дату поста не посмотрел...

[waxtep]

Cash в сообщении #1630269 писал(а):

Отсюда уже очевидно, где надо располагать ловушку - там, где эти части примерно равны

Тут, кажется, хитрее, например для $E=6,B=(1,1,1,1,1,100,0,105)$ поставим ловушку во вторую ячейку и поймаем пять призраков; а если в шестую - только двоих

[Cash]

waxtep, этим способом я думал узнать - сможем ли поймать всех привидений на подотрезке или нет? После чего 2 указателями найти отрезок с максимумом.
Но вижу, что здесь непрерывности нет и мы можем выкинуть толстое, заменив более далеким.

[Mihaylo]

Допустим ловушка помещена в $k$-ый сектор. И мы посчитали стоимость поимки всех привидений: слева от ловушки $E_1$, справа $E_2$. Также мы считаем суммы сил привидений слева $A_1$ и справа $A_2$ от ловушки.
Перемещаем ловушку в $(k+1)$-ый сектор. Что происходит? $E_1$ увеличивается на величину $A_1$ и на силу привидения $A[k]$, находившегося в $k$-ом секторе. $E_2$ уменьшается на величину $A_2$.
Несложный цикл сложности $O(N)$, чтобы найти $k$, при котором $E = E_1 + E_2$ имеет наименьшее значение.

Наверное не совсем верное решение... Кажется надо ввести левую и правую границу действия ловушки, т.е. $k_1$ и $k_2$ и похожим методом в цикле подбирать по условию $E \geqslant E_1 + E_2$.

[Null]

Ловушка стоит в секторе с привидением. Иначе ее можно сдвинуть в сторону где жизненной силы у пойманных приведений больше.
Приведений же можно пропускать? Не ловить живучего рядом, а более слабого дальше? Пойманные приведения не образуют непрерывный отрезок.

[EUgeneUS]

1. Нужно отметить, что вопрос в заголовке: "Поиск оптимальной позиции ловушки" и вопрос в тексте:

trozki_187 в сообщении #1606659 писал(а):

Надо вычислить максимальное количество призраков, которое мы можем поймать в ловушку.

Два существенно разных вопроса.

2.

waxtep в сообщении #1630273 писал(а):

Тут, кажется, хитрее,

Конечно, хитрее. Если таки нужно найти максимальное количество призраков, то для каждой позиции ловушки получаем задачу о рюкзаке, которая NP-полная.

3.

trozki_187 в сообщении #1606659 писал(а):

То есть, если ловушка стоит в нулевой ячейке, а призрак с жизненной энергией $2$ стоит в третьей ячейке, то стоимость его поимки $2\cdot(3-0) = 6$.

Тут непонятно. Разница между номерами ячейки или таки модуль разницы. Скорее всё таки модуль разницы, так как было бы довольно странно иметь отрицательную стоимость поимки не имея (явного) ограничения на вместимость ловушки снизу.

4.

Null в сообщении #1631153 писал(а):

Ловушка стоит в секторе с привидением. Иначе ее можно сдвинуть в сторону где жизненной силы у пойманных приведений больше.

Контрпример, $E=7$, $B=(2,1,0,1,1)$.
Если разместить ловушку во второй позиции, то все призраки не влезут. А если разместить в первой, не пустой, позиции (нумерация с нуля), то влезут.

[Null]

EUgeneUS в сообщении #1631168 писал(а):

Контрпример, $E=7$, $B=(2,1,0,1,1)$.
Если разместить ловушку во второй позиции, то все призраки не влезут. А если разместить в первой, не пустой, позиции (нумерация с нуля), то влезут.

Да, ловушка в секторе с призраком. Я так и сказал.

EUgeneUS в сообщении #1631168 писал(а):

Если таки нужно найти максимальное количество призраков, то для каждой позиции ловушки получаем задачу о рюкзаке, которая NP-полная.

Тут жадный алгоритм прокатывает - берем самых дешевых для данной позиции призраков по возрастанию.
Можно решить за $O(N^2\log N)$, но многовато выходит.

[Mihaylo]

EUgeneUS в сообщении #1631168 писал(а):

для каждой позиции ловушки получаем задачу о рюкзаке, которая NP-полная

Нет, к NP не сводится из-за линейных свойств, динамическое программирование здесь рулит. Сейчас уточню алгоритм...

Итак, пусть ловушка стоит в $k$-ом секторе. Найдем границы действия ("радиус" действия) ловушки $k_1$ и $k_2$ ($k_1 \leqslant k \leqslant k_2$) так, чтобы она убила максимум привидений, используя энергию $E$. Пока эту часть алгоритма не раскрываем, но предположим, что как-то найдены оптимальные $k_1$ и $k_2$ при данном $k$.

Перемещаем ловушку в положение $(k+1)$:

Mihaylo в сообщении #1631151 писал(а):

Перемещаем ловушку в $(k+1)$-ый сектор. Что происходит? $E_1$ увеличивается на величину $A_1$ и на силу привидения $A[k]$, находившегося в $k$-ом секторе. $E_2$ уменьшается на величину $A_2$.

Mihaylo в сообщении #1631151 писал(а):

И мы посчитали стоимость поимки всех привидений: слева от ловушки $E_1$, справа $E_2$. Также мы считаем суммы сил привидений слева $A_1$ и справа $A_2$ от ловушки.

Уточним, что $E_1$ и $A_1$ считаются от $k_1$ до $k$, а $E_2$ и $A_2$ считаются от $k$ до $k_2$.

При смещении ловушки в $(k+1)$-ый сектор могли измениться оптимальные границы действия ловушки, но информация о предыдущих границах не теряет смысл: $k_1$ и $k_2$ могут сдвинуться вправо, но никак влево. Придумайте алгоритм перебора, чтобы найти новые оптимальные границы. А я пока дальше пошел...

Итак, мы знаем оптимальные границы для $k$-го сектора и легко подобрали границы для $(k+1)$-го сектора. А теперь давайте найдем границы для сектора $k=1$. Это же просто! И если вы нашли тот алгоритм для $(k+1)$-го сектора, то дальше всё делает метод индукциирекурсия, точнее динамическое программирование.

-- 28.02.2024, 18:52 --

Извините, я массивы $A$ и $B$ перепутал.

waxtep в сообщении #1630273 писал(а):

например для $E=6,B=(1,1,1,1,1,100,0,105)$

Шаг 1. $k=1$
$E \leqslant 0 \cdot 1 + 1 \cdot 1 + 2 \cdot 1 + 3 \cdot 1 = 6$
$k_1 = 1$
$k_2 = 4$
$E_1 = 0$
$E_2 = 6$
$B_1 = 0$
$B_2 = 3$

Шаг 2. $k=2$
$E_1 = E_1 + B_1 + B[1] = 0 + 0 + 1 = 1$
$E_2 = E_2 - B_2 = 6 - 3 = 3$
$k_1 = 1$
$k_2 = 4$
$E \leqslant 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 + 2 \cdot 1 = 4$
$E_1 = 1$
$E_2 = 3$
$B_1 = 1$
$B_2 = 2$

Шаг 3. $k=3$
$E_1 = E_1 + B_1 + B[2] = 1 + 1 + 1 = 3$
$E_2 = E_2 - B_2 = 3 - 2 = 1$
$k_1 = 1$
$k_2 = 5$
$E \leqslant 2 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 + 2 \cdot 1 = 6$
$E_1 = 3$
$E_2 = 3$
$B_1 = 2$
$B_2 = 2$

Шаг 4. $k=4$
$E_1 = E_1 + B_1 + B[3] = 3 + 2 + 1 = 6$
$E_2 = E_2 - B_2 = 3 - 2 = 1$
$k_1 = 1$
$k_2 = 5$
$E \leqslant 2 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 = 4$
$E_1 = 3$
$E_2 = 1$
$B_1 = 2$
$B_2 = 1$

Шаг 5. $k=5$
$E_1 = E_1 + B_1 + B[4] = 3 + 2 + 1 = 6$
$E_2 = E_2 - B_2 = 1 - 1 = 0$
$k_1 = 1$
$k_2 = 4$
$E \leqslant 3 \cdot 1 + 2 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 = 6$
$E_1 = 6$
$E_2 = 0$
$B_1 = 3$
$B_2 = 0$

Шаг 6. $k=6$
$E_1 = E_1 + B_1 + B[5] = 6 + 3 + 1 = 10$
$E_2 = E_2 - B_2 = 0 - 0 = 0$
$k_1 = 2$
$k_2 = 6$
$E \leqslant 3 \cdot 1 + 2 \cdot 1 + 1 \cdot 1 + 0 \cdot 100 = 6$
$E_1 = 6$
$E_2 = 0$
$B_1 = 3$
$B_2 = 0$

Шаг 7. $k=7$
$E_1 = E_1 + B_1 + B[6] = 6 + 3 + 100 = 109$
$E_2 = E_2 - B_2 = 0 - 0 = 0$
$k_1 = 7$
$k_2 = 7$
$E \leqslant 0 \cdot 0 = 0$
$E_1 = 0$
$E_2 = 0$
$B_1 = 0$
$B_2 = 0$

Шаг 8. $k=8$
$E_1 = E_1 + B_1 + B[7] = 0 + 0 + 0 = 0$
$E_2 = E_2 - B_2 = 0 - 0 = 0$
$k_1 = 7$
$k_2 = 8$
$E \leqslant 0 \cdot 105 = 0$
$E_1 = 0$
$E_2 = 0$
$B_1 = 0$
$B_2 = 0$

Из всех секторов оптимальным является $k=3$.

[EUgeneUS]

Null в сообщении #1631181 писал(а):

Да, ловушка в секторе с призраком. Я так и сказал.

Да, Вы правы. Это был какой-то "отрицательный контрпример".

Null в сообщении #1631181 писал(а):

Тут жадный алгоритм прокатывает - берем самых дешевых для данной позиции призраков по возрастанию.
Можно решить за $O(N^2\log N)$, но многовато выходит.

Жадный алгоритм не гарантирует нахождения оптимального решения.

Mihaylo в сообщении #1631244 писал(а):

Нет, к NP не сводится из-за линейных свойств, динамическое программирование здесь рулит. Сейчас уточню алгоритм...

Если стоит вопрос с подсчетом максимального количества пойманных призраков, то это задача о рюкзаке, а она NP-полная. Как пишут, методы динамического программирования могут обеспечить псевдополиномиальное время.

[Mihaylo]

Это не задача о рюкзаке, а классическая задачка на динамическое программирование.
Разница в том, что в рюкзак привидения пришлось бы укладывать в произвольном порядке, а здесь - в строгом порядке секторов.

[Null]

EUgeneUS в сообщении #1631272 писал(а):

Если стоит вопрос с подсчетом максимального количества пойманных призраков, то это задача о рюкзаке, а она NP-полная.

Тут ценность всех вещей 1. Жадный алгоритм работает.

Mihaylo в сообщении #1631303 писал(а):

здесь - в строгом порядке секторов.

Такого требования нет(Вопрос к trozki_187). Да и если его добавить, то в вашем алгоритме проблема - в каждом секторе мы должны перебирать позицию окна с запасом вперед(может там дальше куча единичек стоит) и возвращаться если мы их не нашли. Долго работать будет. Опишите вычисление новых $k_1,k_2$ в вашем алгоритме.

[Mihaylo]

Когда мы переместили ловушку из $k$ в $(k+1)$, уничтожение привидений слева однозначно стало труднее или в тривиальных случаях не изменилось, а уничтожение привидений справа однозначно стало легче или в тривиальных случаях не изменилось. Отсюда следует, что $k_1$ и $k_2$ могут сдвинуться только вправо, либо в тривиальных случаях остаться на месте. Я думаю это понятно.

Возможен алгоритм перебора влоб с наихудшей сложностью $O(N)$ или $O(L)$. $k_1$ пробежится от текущего значения до $k$ при этом можно проскакивать сектора без привидений, а $k_2$ увеличивается по условию непревышения энергии $E$. В этом цикле фиксируется наилучшее решение и в конце цикла оно устанавливается.

-- 29.02.2024, 10:43 --

Итоговая сложность $O(L \cdot N)$ или $O(L^2)$. Какой вариант? Зависит от того, подготовим ли предварительно спецсловарь с адресами привидений или нет.