出現字跡模糊跡象

by Sachin Malhotra

由Sachin Malhotra

改變跡象：如何使用動態編程解決競爭性編程問題 (Change the signs: how to use dynamic programming to solve a competitive programming question)

If you’re a competitive programmer like I am, one of the best feelings in the world is seeing your program getting accepted on first try on one of the most famous programming platforms, CodeChef.

如果您是像我這樣的有競爭力的程序員，那么世界上最好的感覺之一就是看到您的程序在最著名的編程平臺之一CodeChef上首次嘗試就被接受。

I was an avid competitive programmer during undergrad, and then lost touch with it when working as a developer @Hike. However, I recently started out into this adventurous world of programming again, all thanks to my friend Divya Godayal.

在本科期間，我曾是一名狂熱的競爭性程序員，然后在作為開發人員@Hike時失去了與它的聯系。 但是，最近我再次開始進入這個冒險的編程世界，這一切都要歸功于我的朋友Divya Godayal 。

The CodeChef May 2018 Long Challenge ended about an hour ago, and I decided to write this article as a post describing one of the questions in the competition.

CodeChef 2018年5月的長期挑戰賽大約一個小時前結束，我決定將這篇文章寫為一篇文章，描述比賽中的一個問題。

Without wasting any more time, let’s get to it.

不要浪費更多的時間，讓我們開始吧。

解開問題陳述 (Unravelling the Problem Statement)

Let’s look at some examples to better understand what the problem statement is asking for.

讓我們看一些例子，以更好地理解問題陳述的要求。

Consider the following number sequence.

考慮以下數字順序。

4 3 1 2

Now the question asks us to perform a certain operation (possibly 0 times, leaving the sequence unchanged). We can negate a certain subsequence of numbers and get a new sequence.

現在，問題要求我們執行某些操作(可能為0次，序列保持不變)。 我們可以否定數字的某個子序列并獲得新的序列。

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

The question says that the resulting sequence should satisfy the following constraint:

問題說，結果序列應滿足以下約束：

The sum of elements of any substring with length greater than 1 is strictly positive.

長度大于1的任何子字符串的元素之和嚴格為正。

Clearly, the following sequences are not valid:

顯然，以下序列無效：

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

We only have 2 valid subsequences that can be obtained by performing the operation mentioned above. Note: we haven’t written down all the possible subsequences. That would be 2^n, that is 16 in this case, because for every number we have two options. Either to negate it, or not.

通過執行上述操作，我們只有2個有效的子序列。 注意：我們還沒有寫下所有可能的子序列。 那將是2 ^ n，在這種情況下就是16，因為對于每個數字，我們都有兩個選擇。 是否取消它。

So the two valid sequences are:

因此，兩個有效序列為：

4 3 1 2

and

和

4 3 -1 2

The original sequence would always be one of the valid sequences as all the numbers in it are positive.

原始序列始終是有效序列之一，因為其中的所有數字都是正數。

Now the question asks us to find the sequence with the minimum sum. So for the example we have considered, the sequence required would be 4 3 -1 2 .

現在，問題要求我們找到具有最小總和的序列。 因此，對于我們考慮的示例，所需的序列將為4 3 -1 2 。

貪婪會工作嗎？ (Would Greedy Work?)

A greedy approach in this question would be that if it is possible to negate a number while satisfying the given constraints, then we should negate that number. This approach however, would not always give the right results. Consider the following example.

這個問題中的一種貪婪方法是，如果可以在滿足給定約束的情況下否定一個數字，那么我們應該否定那個數字。 但是，這種方法并不總是能給出正確的結果。 考慮以下示例。

4 1 3 2

Here, it is possible to have these three valid sets of numbers:

在這里，可以具有以下三個有效數字集：

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

Clearly, both the numbers 2 and 1 can be negated. But not both of them at the same time. If we negate a number greedily — that is, if a number can be negated, then we negate it — then it is possible that we might end up negating the number 1. Then you won’t be able to negate the number 2. This would give us a suboptimal solution.

顯然，數字2和1都可以取反。 但不是兩個都同時出現。 如果我們貪婪地否定一個數字(也就是說，如果一個數字可以取反，那么我們將其取反)，那么我們最終可能會否定一個數字1。那么您將無法否定這個數字2。會給我們一個次優的解決方案。

So this Greedy approach would not work here. We have to “try out a specific choice of whether to negate or not for a number and see what choice gives us the optimal solution”.

因此，這種貪婪方法在這里行不通。 我們必須“嘗試確定是否對某個數字求反的特定選擇，并查看哪種選擇可以為我們提供最佳解決方案” 。

This smells like Dynamic Programming.

這聞起來像動態編程。

好的動態編程 (Good ol’ Dynamic Programming)

One of the most interesting algorithmic techniques out there, and possibly one of the most dreaded, is dynamic programming. This is the technique we are going to use to solve this particular problem.

動態編程是目前最有趣的算法技術之一，而且可能也是最令人恐懼的算法之一。 這是我們將用來解決此特定問題的技術。

Two of the most important steps in any dynamic programming problem are:

任何動態編程問題中最重要的兩個步驟是：

1. Identifying the recurrent relation.
   確定遞歸關系。

2. Figuring out what to memoize. (not memoRize :P)

   找出要記住的內容 。 (不是memoRize：P)

The DP-based approach here is divided into two basic parts.

這里基于DP的方法分為兩個基本部分。

• One is the main recursion that we use to find out the minimum sum of the final set. Note, the dynamic programming is not directly used to obtain the final set, just the sum of the final set of numbers. So our dynamic programming approach would correctly find out the sum for the example given above as 8. 4 + 3 + (-1) + 2 = 8 .

  一種是主要的遞歸，我們用它來找出最終集合的最小和 。 注意，動態編程不是直接用于獲得最終集合，而只是直接獲得最終數字集的總和。 因此，我們的動態編程方法將正確找到上述示例的總和為8。4 4 + 3 + (-1) + 2 = 8 。

• What we actually need is the final modified set of numbers where some (possibly none) of the numbers are negated. We use the concept of a parent pointer and backtracking to find out the actual set of numbers.

  我們真正需要的是最終的一組修改的數字，其中一些(可能沒有)數字被取反了。 我們使用父指針和回溯的概念來找出實際的數字集。

Let’s move onto our recursion relation for our dynamic programming approach.

讓我們進入我們的動態編程方法的遞歸關系。

Before describing the recursive relation an important observation to make here is that if a number has been negated, then any adjacent number to it can not be negative. That is, two adjacent numbers cannot be negative as that would give a substring of length 2 whose sum is negative, and that is not allowed according to the question.

在描述遞歸關系之前，這里需要做的一個重要觀察是，如果一個數字被取反， 那么任何與其相鄰的數字都不能為負 。 那是， 兩個相鄰的數字不能為負，因為那樣會產生長度為2的子串，其總和為負，并且根據問題不允許這樣做。

For the recurrence relation, we need two variables. One is the index number of where we are in the array, and one is a boolean value that tells us if the previous number (one left to the previous number) is negated or not. So if the current index is i, then the boolean value would tell us if the number at i — 2 was negated or not. You will know the importance of this boolean variable in the next paragraph.

對于遞歸關系，我們需要兩個變量。 一個是我們在數組中的位置的索引號，另一個是一個布爾值，它告訴我們前一個數字(前一個數字的左邊)是否被取反。 因此，如果當前索引是i ，那么布爾值會告訴我們，如果在號碼i — 2被否定或不。 在下一段中，您將知道此布爾變量的重要性。

We need to know in O(1) if a number can be negated or not. Since we are following a recursion with memoization-based solution, whenever we are at an index i in the recursion, we are sure that the numbers to the right (i+ 1 onwards) have not been processed up to this point. This means that all of them are still positive.

我們需要在O(1)知道數字是否可以取反。 由于我們正在使用基于記憶的解決方案進行遞歸，因此只要我們在遞歸中位于索引i ，就可以確保到目前為止，尚未處理右邊的數字(從i+ 1開始)。 這意味著他們所有人仍然是積極的。

The choice of whether the number at index i can be negated is dependent upon the right hand side (if there is one) and the left hand side (if there is one). The right hand side is easy. All we need to check is if

索引i的數字是否可以取反的選擇取決于右側(如果有一個)和左側(如果有一個)。 右側很容易。 我們需要檢查的是

number[i] < number[i + 1]

because if this is not true, then adding these two would give a negative value for the substring [i, i + 1] thus making it an invalid operation.

因為如果這不是真的，則將這兩個值相加會給子字符串[i, i + 1]賦予負值[i, i + 1]從而使其無效。

Now comes the tricky part. We need to see if negating the number at i will cause a substring of negative sum to the left or not. When we reach the index i in our recursion, we have already processed the numbers before it, and some might have been negated as well.

現在是棘手的部分。 我們需要查看是否對i取反會導致左邊的和為負數。 當我們在遞歸中達到索引i時，我們已經處理了它之前的數字，并且有些數字也可能被取反。

So say we have this set of numbers 4 1 2 1 and we had negated the first 1 and we are now processing the last number ( 1 ).

假設我們有這組數字4 1 2 1而我們否定了前一個數字1 ，現在正在處理最后一個數字( 1 )。

4 -1 2 [1]

The last number in square brackets is the one we are processing right now. As far as the right hand side is concerned, since there is none, we can negate it. We need to check if negating this 1 at index 3 (0 based indexing) would cause any substring to the left of ≤ 0 sum. As you can see, it will produce such a substring.

方括號中的最后一個數字是我們現在正在處理的數字。 就右側而言，既然沒有，我們可以否定它。 我們需要檢查在索引3處否定此1(基于0的索引)是否會導致任何子串在≤0 sum的左邊。 如您所見，它將產生這樣的子字符串。

-1 2 -1

This substring would have a 0 sum, and that is invalid according to the question. After negating a subsequence of numbers, the substrings in the final set should have a sum which is strictly positive. All the substrings of length > 1.

該子字符串的總和為0，根據問題，該值無效。 排除數字的子序列后，最終集中的子字符串的總和應嚴格為正。 所有長度> 1的子串

We cannot apply the following approach here directly:

我們無法在此處直接應用以下方法：

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

because, although 1 <; 2 , if we negate that last 1 as well we will have an invalid set of numbers as seen above. So this simple approach or check won’t work here.

因為，盡管1 < ; 2，如果我們也否定最后一個1，我們將得到無效的數字集，如上所示。 因此，這種簡單的方法或檢查在這里行不通。

Here comes the boolean variable which tells us if, given an index i, the number at i — 2 was negated or not. Consider the two scenarios.

這里談到的布爾變量，如果它告訴我們，給定一個指標i ，在數字i — 2是否定或沒有。 考慮這兩種情況。

• Yes, the number at index i — 2 was negated like in the example just showcased. In that case, negation of the number at i — 2 would have a capacity reduction for number at i — 1. In the example 4 1 2 1 , negating the 1 at index 1(0 based indexing) would reduce the capacity of the number 2 (at index 2) by 1. We refer to remaining values of numbers as capacities here. We need to consider this reduced capacity when performing the check to see if a number can be negated or not.

  是的，索引i — 2被否定，就像剛剛展示的示例一樣。 在這種情況下，在號碼否定i — 2將具有在對數的能力減少i — 1 。 在示例4 1 2 1 ，在索引1(基于0的索引)處取反1將使數字2(在索引2)的容量減少1。我們在此將數字的剩余值稱為容量。 在執行檢查以查看數字是否可以取反時，我們需要考慮這種減少的容量。

number[i] < reducedCapacityOfNumberAt(i - 1)

• In case the number at index i — 2 wasn’t negated, the number at i — 1 is at it’s full capacity. The simple check

  如果在索引數量i — 2并沒有否定，人數為i — 1是它的滿負荷生產。 簡單檢查

number[i] < number[i - 1]

would be enough to see if we can negate the number at index i .

足以確定我們是否可以否定索引i的數字。

Let’s look at the code for the recursion containing all the ideas discussed above.

讓我們看一下包含上面討論的所有想法的遞歸代碼。

That’s all nice and dandy. But, this is just recursion, and the heading says dynamic programming. That means there would be overlapping subproblems. Let us look at the recursion tree to see if there are any.

很好，花花公子。 但是，這只是遞歸，標題說的是動態編程。 這意味著將存在重疊的子問題。 讓我們看一下遞歸樹，看是否有遞歸樹。

As you can see, there are overlapping subproblems in the recursion tree. That is why we can use memoization.

如您所見，遞歸樹中有重疊的子問題。 這就是為什么我們可以使用記憶。

The memoization is as simple as:

備注很簡單：

""" 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;

As pointed out earlier, this recursive approach would return the minimum sum of the set of numbers possible after making the valid set of modifications to them.

如前所述，這種遞歸方法在對數字進行有效修改后將返回可能的最小數字總和。

The question, however, asks us to actually print the final set of numbers that gives the minimum sum after making such modifications. For that, we need to use a parent pointer that would tell us at every index and boolean variable is_prev_negated ’s value as to what optimal action was taken.

但是，這個問題要求我們在進行此類修改后實際打印出給出最小總和的最終數字集。 為此，我們需要使用一個父指針，該指針將告訴我們每個索引和布爾變量is_prev_negated的值，以了解采取了什么最佳操作。

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

So we simply store 1 or -1 depending upon if negating the number at index i (if possible!) gave us the minimum sum or if choosing to ignore it gave the minimum sum.

因此，我們簡單地存儲1或-1，具體取決于是否對索引i的數字取反(如果可能！)給我們最小的總和，或者選擇忽略它給我們最小的總和。

回溯 (Backtracking)

Now comes the part where we backtrack to find the solution to our original problem. Note that the decision for the very first number is what propagates the recursion further. If the first number was negated, the second number would be positive and the third number’s decision can be found using parent[2][true]. Similarly, if the first number wasn’t negated, then we move onto the second number and it’s decision can be found using parent[1][false] and so on. Let’s look at the code.

現在是我們回溯以找到原始問題的解決方案的部分。 請注意，第一個數字的決定是進一步傳播遞歸的原因。 如果第一個數字取反，則第二個數字為正，可以使用parent[2][true]找到第三個數字的決定。 同樣，如果第一個數字未取反，那么我們移到第二個數字，可以使用parent[1][false]等找到它的決定。 讓我們看一下代碼。

更好的方法 (A Better Approach)

If you take a look at the space complexity of the solution suggested, you will see that it’s a 2 dimensional dynamic programming solution because the state of the recursion is represented by two variables i.e. the index i representing what number of the array we are considering and then the boolean variable is_prev_negated . So the space complexity and the time complexity would be O(n*2) which is essentially O(n).

如果您看一下所建議解決方案的空間復雜性，您會發現它是一種二維動態規劃解決方案，因為遞歸的狀態由兩個變量表示，即索引i表示我們正在考慮的數組數量以及然后是布爾變量is_prev_negated 。 因此，空間復雜度和時間復雜度將為O(n * 2)，本質上為O(n)。

However, there is a slightly better approach as well to solving this problem as suggested by Divya Godayal. This problem can even be solved by 1 dimensional dynamic programming based solution.

但是， Divya Godayal提出了一種更好的方法來解決此問題。 這個問題甚至可以通過基于一維動態編程的解決方案來解決。

Essentially, the boolean variable is_prev_negated is helping us to decide if we can negate a given number at index i or not as far as the left hand side of the array is concerned i.e. all the numbers from 0 .. i-1 because the right hand side is anyways safe as all the numbers on that side are positive (as the recursion hasn’t reached them yet). So for the right hand side we simply checked the number at i+1 but for the left hand side of index i we had to make use of the boolean variable is_prev_negated .

本質上講，布爾變量is_prev_negated可以幫助我們確定是否可以對索引i處給定的數字取反，就數組的左側而言，即all the numbers from 0 .. i-1因為右手無論如何，這邊都是安全的，因為該邊的所有數字都是正數(因為遞歸尚未到達它們)。 因此，對于右側，我們僅檢查i+1處的數字，但對于索引i的左側，我們必須使用布爾變量is_prev_negated 。

It turns out, that we can simply skip this boolean variable altogether and simply look ahead to decide if a number can be negated or not. Which simply means if you are at an index i, you check if that element along with the element at i+2 have the capacity to swallow the element at i+1 i.e.

事實證明，我們可以簡單地完全跳過此布爾變量，并簡單地向前看以確定是否可以取反數字。 這只是意味著如果您在索引i ，您將檢查該元素以及i+2處的元素是否具有吞下i+1處的元素的能力，即

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

If there is a such a possibility, then we directly jump to i+3if we negate element at i because element at i+1 and i+2 both can’t be negative in such a scenario.

如果有這種可能性，那么如果我們否定i處的元素，則我們直接跳到i+3處，因為在這種情況下， i+1和i+2處的元素都不能為負。

In case the swallow condition is not satisfied and we end up negating the number at index i , then we would jump to index i+2 because in any case, two consecutive numbers cannot be negated. So if the number at i was negated, then the number at i+1 has to be positive. The swallow check is to see if the number at i+2 would definitely have to be positive or if we can exercise the choice of whether to negate or not there.

如果不滿足吞咽條件并且我們最終否定了索引i處的數字，那么我們將跳轉到索引i+2因為在任何情況下，兩個連續的數字都不能取反。 因此，如果i處的數字為負數，則i+1處的數字必須為正。 吞下檢查的目的是確定i+2處的數字是否一定一定是正數，或者我們是否可以選擇是否取反。

Have a look at the code for a better understanding.

查看代碼以更好地理解。

Hence, just a single variable i.e. the index is used to define the state of the recursion. So the time and space complexity, both got reduced to half of what they were in the previous solution.

因此，僅使用一個變量(即索引)來定義遞歸的狀態。 因此，時間和空間的復雜性都降低到了以前解決方案的一半。

I hope you were able to grasp the working of the algorithm described above and how the dynamic programming technique fits into this problem. I think it’s an interesting problem, because you not only have to use dynamic programming but also the concept of parent pointer to retrace the steps through the optimal solution and get the answer required in the question.

我希望您能夠掌握上述算法的工作以及動態編程技術如何解決此問題。 我認為這是一個有趣的問題，因為您不僅必須使用動態編程，而且還必須使用父指針的概念來通過最佳解決方案追溯步驟并獲得問題中所需的答案。

翻譯自: https://www.freecodecamp.org/news/just-change-the-signs-how-to-solve-a-competitive-programming-question-f9730e8f04a9/

出現字跡模糊跡象