как использовать динамическое программирование для решения конкурсного вопроса

1656607824 kak ispolzovat dinamicheskoe programmirovanie dlya resheniya konkursnogo voprosa

автор Сачин Малхотра

zGtTB9aAifr96mox-3mchz3QFHXXY4lThHrB

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

Во время обучения я был упорным конкурентоспособным программистом, а потом потерял связь с этим, когда работал разработчиком @Hike. Однако недавно я снова попал в этот авантюрный мир программирования, все благодаря моей подруге Девье Годайал.

Долгий вызов CodeChef May 2018 закончился примерно час назад, и я решил написать эту статью как сообщение с описанием одного из вопросов конкурса.

Не тратя больше времени, давайте приступим к этому.

Y6UspCo7zHVxvZE-xRG3pERSJQy4CfD6EGU3

Разгадка постановки проблемы

Давайте рассмотрим несколько примеров, чтобы лучше понять, что требует формулировки проблемы.

Рассмотрим следующую числовую последовательность.

4 3 1 2

Теперь вопрос просит нас проделать определенную операцию (возможно, 0 раз, оставляя последовательность без изменений). Мы можем отменить определенную последовательность чисел и получить новую последовательность.

-4 3 1 24 -3 1 -24 3 -1 24 3 1 -2-4 -3 1 2 etc.

Вопрос говорит о том, что полученная последовательность должна удовлетворять следующему ограничению:

Сумма элементов любой подстроки длиной более 1 строго положительна.

Очевидно, что следующие последовательности не действительны:

-4 3 1 24 -3 1 -2 4 3 1 -2 -4 -3 1 2 -4 -3 -1 -24 3 -1 -2

У нас есть только 2 действительные подпоследовательности, которые можно получить, выполнив описанную выше операцию. Примечание: мы не записали все возможные подпоследовательности. Это было бы 2^n, то есть в данном случае 16, потому что для каждого числа у нас есть два варианта. Либо отрицать это, либо нет.

Итак, две действительные последовательности:

4 3 1 2

и

4 3 -1 2

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

Теперь вопрос просит нас найти последовательность с минимальной суммой. Следовательно, для рассматриваемого нами примера необходимая последовательность будет такой. 4 3 -1 2 .

Сработает ли Greedy?

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

4 1 3 2

Здесь можно иметь эти три действительных набора чисел:

4 1 3 2           4 -1 3 2           4 1 3 -2

Очевидно, что оба числа 2 и 1 можно отменить. Но не оба одновременно. Если мы жадно отрицаем число – то есть если число можно отменить, то мы его отрицаем – то вполне возможно, что мы можем отрицать число 1. Тогда вы не сможете отрицать число 2. Это даст нам неоптимальное решение.

Так что этот жадный подход здесь не сработает. Мы должны «попробуйте конкретный выбор, отрицать или нет для числа, и посмотрите, какой выбор дает нам оптимальное решение».

Это похоже на динамическое программирование.

Старое хорошо динамическое программирование

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

Два из важнейших шагов в любой задаче динамического программирования:

  1. Выявление повторяющегося отношения.
  2. Выясняя, что делать запоминать. (не запоминать :P)

Подход на базе DP тут разделен на две главные части.

  • Одна из них – это основная рекурсия, которую мы используем, чтобы узнать минимальная сумма окончательного набора. Обратите внимание, что динамическое программирование не используется непосредственно для получения окончательного набора, а сумма окончательного набора чисел. Следовательно, наш подход к динамическому программированию правильно выяснил бы сумму для вышеприведенного примера как 8. 4 + 3 + (-1) + 2 = 8 .
  • На самом деле, нам нужен окончательный модифицированный набор чисел, где некоторые (возможно, никакие) чисел отрицаются. Мы используем понятие а родительский указатель и возвращение назад чтобы узнать реальный набор чисел.

Давайте перейдем к нашему отношению рекурсии для нашего подхода к динамическому программированию.

Прежде чем описывать рекурсивное отношение, следует сделать важное наблюдение: если число было отменено, то любое соседнее с ним число не может быть отрицательным. Это, два соседних числа не могут быть отрицательными, поскольку это даст подстроку длиной 2, сумма которой отрицательна, а это не допускается в соответствии с вопросом.

Для рекуррентного отношения нам нужны две переменные. Один – это номер индекса, где мы находимся в массиве, а второй – логическое значение, указывающее нам, отменено ли предыдущее число (один слева от предыдущего числа) или нет. Итак, если текущий индекс есть iтогда логическое значение подскажет нам, если число в i — 2 было упразднено или нет. В следующем абзаце вы узнаете о важности этой булевой переменной.

Нам нужно знать в O(1) если число может возражать или нет. Поскольку мы следим за рекурсией с решением на основе мемоизации, когда мы находимся в индексе i в рекурсии мы уверены, что числа справа (i+ 1 далее) не обработан до этого момента. Это значит, что они все еще положительны.

Выбор будет ли число в индексе i можно возражать, зависит от правой стороны (если она есть) и левой (если она есть). Правая сторона легкая. Все, что нам нужно проверить, это если

number[i] < number[i + 1]

потому что если это не так, то добавление этих двух даст отрицательное значение для подстроки. [i, i + 1] что делает его недействительной операцию.

Теперь наступает сложная часть. Нам нужно проверить, отрицаем ли число в i повлечет за собой подряд отрицательной суммы слева или нет. Когда мы достигаем индекса i в нашей рекурсии мы уже обработали числа, которые были перед ней и некоторые также могли быть отменены.

Так что скажем, что у нас есть этот набор чисел 4 1 2 1 и мы возразили первое 1 и сейчас мы обрабатываем последний номер ( 1 ).

4 -1 2 [1]

Последнее число в квадратных скобках – это то, которое мы сейчас обрабатываем. Что касается правой стороны, поскольку ее нет, мы можем ее отрицать. Нам нужно проверить, приведет ли возражение этого 1 по индексу 3 (индексация на основе 0) к возникновению любой подстроки слева от ≤ 0 суммы. Как видим, он создаст такую ​​подстроку.

-1 2 -1

Эта подстрока имела бы сумму 0, и это недействительно в соответствии с вопросом. После отрицания подпоследовательности чисел подстроки в конечном наборе должны иметь сумму, строго положительную. Все подрядки длиной >1.

Мы не можем применить здесь такой подход:

if number[i] < number[i - 1], then it is good to go on negation.

потому что, хотя 1 <; 2 , если мы также отрицаем последнюю 1, то получим недействительный набор чисел, как показано выше. Так что этот простой подход или проверка здесь не сработает.

Здесь появляется булевая переменная, которая указывает нам если, с помощью индекса iномер в i — 2 было упразднено или нет. Рассмотрим два сценария.

  • Да, номер в индексе i — 2 было отменено, как в только что показанном примере. В этом случае отрицание числа at i — 2 будет иметь уменьшение емкости для количества at i — 1. В примере 4 1 2 1 , отрицание 1 по индексу 1 (индексация на основе 0) уменьшит емкость числа 2 (по индексу 2) на 1. Мы называем остальные значения числа емкостью здесь. Нам нужно учитывать эту уменьшенную емкость во время проверки, чтобы увидеть, можно ли отменить число или нет.
number[i] < reducedCapacityOfNumberAt(i - 1)
  • В случае если номер в индексе i — 2 не было отменено, номер у i — 1 находится на полную мощность. Простая проверка
number[i] < number[i - 1]

было бы достаточно, чтобы увидеть, сможем ли мы отрицать число в index i .

Давайте посмотрим код рекурсии, содержащий все идеи, обсужденные выше.

a4tshHUm1WyoHHO0hK-050EfDySLR3KHVwzY

Это все красиво и модно. Но это только рекурсия, а в заглавии написано динамическое программирование. Это означает, что подпроблемы будут перекрываться. Давайте посмотрим на дерево рекурсии, чтобы увидеть, есть ли оно.

-6EItwtVtgzqUHrsbEJODoMoxV2woN6iN7Nv

Как видите, в дереве рекурсии есть перекрывающиеся подпроблемы. Поэтому мы можем использовать запоминание.

Запоминание так просто:

""" This comes at the top. We check if the state represented by the tuple of the index and the boolean variable is already cached """
if(memo[i][is_prev_negated] != INF) {    return memo[i][is_prev_negated];}
...... CODE
# Cache the minimum sum from this index onwards.memo[i][is_prev_negated] = min(pos, neg);
# The parent pointer is used for finding out the final set of #sparent[i][is_prev_negated] = min(pos, neg) == pos ? 1 : -1;

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

Однако этот вопрос требует от нас фактически напечатать окончательный набор чисел, дающий минимальную сумму после внесения таких изменений. Для этого нам нужно использовать родительский указатель, который бы сообщал нам о каждом индексе и булевой переменной. is_prev_negated ‘s значение относительно того, какие оптимальные действия были сделаны.

parent[i][is_prev_negated] = min(pos, neg) == pos ? 1 : -1;

Поэтому мы просто сохраняем 1 или -1 в зависимости от того, отрицание ли числа в индексе i (если возможно!) дало нам минимальную сумму, или если мы решили игнорировать это, дали минимальную сумму.

Возврат назад

Теперь наступает часть, где мы возвращаемся назад, чтобы найти решение нашей первоначальной проблемы. Заметьте, что решение для самого первого числа – это то, что распространяет рекурсию дальше. Если бы первое число было отменено, то второе число было бы положительным и решение третьего числа можно было бы найти с помощью parent[2][true]. Аналогично, если первое число не было отменено, мы переходим ко второму числу, и его решение можно найти с помощью parent[1][false] и так дальше. Давайте посмотрим код.

-rimpa-Iqfb1y22u7qbQZgjxkU-A2ziBQZrW

Лучший подход

Если вы посмотрите на пространственную сложность предлагаемого решения, вы увидите, что это решение двумерного динамического программирования, поскольку состояние рекурсии представлено двумя переменными, то есть индексом i представляет, какой номер массива мы рассматриваем, а затем булевую переменную is_prev_negated . Таким образом, сложность пространства и временной сложности будет O(n*2), что по существу O(n).

Однако существует несколько лучший подход к решению этой проблемы, как это предложил Девья Годайал. Эту проблему можно решить даже посредством одномерного динамического программирования.

По сути, булевая переменная is_prev_negated помогает нам решить, можем ли мы отрицать данное число в индексе i или нет, что касается левой части массива, то есть all the numbers from 0 .. i-1 потому что правая часть все равно безопасна, поскольку все числа на этой стороне положительны (поскольку рекурсия еще не достигла их). Для правой стороны мы просто проверили номер в i+1 но для левой части индекса i мы должны были использовать булевую переменную is_prev_negated .

Оказывается, мы можем просто вообще пропустить эту булевую переменную и просто заглянуть вперед, чтобы решить, можно ли отменить число или нет. Это просто означает, что вы находитесь в индексе iвы проверяете, этот элемент вместе с элементом at i+2 обладают способностью проглотить элемент i+1 есть

numbers[i] + numbers[i+2] >= numbers[i+1  (SWALLOW)

Если есть такая возможность, то мы непосредственно переходим к i+3если мы отрицаем элемент at i поскольку элемент в i+1 и i+2 оба не могут быть отрицательными в таком сценарии.

В случае, если условие глотания не выполняется, и мы в конечном счете отрицаем число в индексе i тогда мы перейдем к индексу i+2 потому что в любом случае два последовательных числа нельзя отменить. Итак, если номер у i было отменено, то число в i+1 должно быть положительным. Проверка глотания состоит в том, чтобы проверить, есть ли номер в i+2 безусловно, должно быть положительным или если мы можем сделать выбор, отрицать или нет.

Посмотрите код для лучшего понимания.

xfOALns0BeiZRPCX-3eL6gpcwxRQu4DCn0W7

Следовательно, только одна переменная, то есть индекс, используется для определения состояния рекурсии. Таким образом, сложность времени и пространства была уменьшена до половины того, что было в предыдущем решении.

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

Добавить комментарий

Ваш адрес email не будет опубликован.