出現(xiàn)字跡模糊跡象

by Sachin Malhotra

由Sachin Malhotra

改變跡象：如何使用動態(tài)編程解決競爭性編程問題 (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.

在本科期間，我曾是一名狂熱的競爭性程序員，然后在作為開發(fā)人員@Hike時(shí)失去了與它的聯(lián)系。 但是，最近我再次開始進(jìn)入這個(gè)冒險(xiǎn)的編程世界，這一切都要?dú)w功于我的朋友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月的長期挑戰(zhàn)賽大約一個(gè)小時(shí)前結(jié)束，我決定將這篇文章寫為一篇文章，描述比賽中的一個(gè)問題。

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

不要浪費(fèi)更多的時(shí)間，讓我們開始吧。

解開問題陳述 (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.

考慮以下數(shù)字順序。

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.

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

-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:

問題說，結(jié)果序列應(yīng)滿足以下約束：

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

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

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.

通過執(zhí)行上述操作，我們只有2個(gè)有效的子序列。 注意：我們還沒有寫下所有可能的子序列。 那將是2 ^ n，在這種情況下就是16，因?yàn)閷τ诿總€(gè)數(shù)字，我們都有兩個(gè)選擇。 是否取消它。

So the two valid sequences are:

因此，兩個(gè)有效序列為：

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.

原始序列始終是有效序列之一，因?yàn)槠渲械乃袛?shù)字都是正數(shù)。

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 .

現(xiàn)在，問題要求我們找到具有最小總和的序列。 因此，對于我們考慮的示例，所需的序列將為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.

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

4 1 3 2

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

在這里，可以具有以下三個(gè)有效數(shù)字集：

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.

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

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”.

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

This smells like Dynamic Programming.

這聞起來像動態(tài)編程。

好的動態(tài)編程 (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.

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

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

任何動態(tài)編程問題中最重要的兩個(gè)步驟是：

Identifying the recurrent relation.

確定遞歸關(guān)系。

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

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

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

這里基于DP的方法分為兩個(gè)基本部分。

• 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 .

  一種是主要的遞歸，我們用它來找出最終集合的最小和 。 注意，動態(tài)編程不是直接用于獲得最終集合，而只是直接獲得最終數(shù)字集的總和。 因此，我們的動態(tài)編程方法將正確找到上述示例的總和為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.

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

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

讓我們進(jìn)入我們的動態(tài)編程方法的遞歸關(guān)系。

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.

在描述遞歸關(guān)系之前，這里需要做的一個(gè)重要觀察是，如果一個(gè)數(shù)字被取反， 那么任何與其相鄰的數(shù)字都不能為負(fù) 。 那是， 兩個(gè)相鄰的數(shù)字不能為負(fù)，因?yàn)槟菢訒a(chǎn)生長度為2的子串，其總和為負(fù)，并且根據(jù)問題不允許這樣做。

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.

對于遞歸關(guān)系，我們需要兩個(gè)變量。 一個(gè)是我們在數(shù)組中的位置的索引號，另一個(gè)是一個(gè)布爾值，它告訴我們前一個(gè)數(shù)字(前一個(gè)數(shù)字的左邊)是否被取反。 因此，如果當(dāng)前索引是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)知道數(shù)字是否可以取反。 由于我們正在使用基于記憶的解決方案進(jìn)行遞歸，因此只要我們在遞歸中位于索引i ，就可以確保到目前為止，尚未處理右邊的數(shù)字(從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的數(shù)字是否可以取反的選擇取決于右側(cè)(如果有一個(gè))和左側(cè)(如果有一個(gè))。 右側(cè)很容易。 我們需要檢查的是

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.

因?yàn)槿绻@不是真的，則將這兩個(gè)值相加會給子字符串[i, i + 1]賦予負(fù)值[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.

現(xiàn)在是棘手的部分。 我們需要查看是否對i取反會導(dǎo)致左邊的和為負(fù)數(shù)。 當(dāng)我們在遞歸中達(dá)到索引i時(shí)，我們已經(jīng)處理了它之前的數(shù)字，并且有些數(shù)字也可能被取反。

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 ).

假設(shè)我們有這組數(shù)字4 1 2 1而我們否定了前一個(gè)數(shù)字1 ，現(xiàn)在正在處理最后一個(gè)數(shù)字( 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.

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

-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，根據(jù)問題，該值無效。 排除數(shù)字的子序列后，最終集中的子字符串的總和應(yīng)嚴(yán)格為正。 所有長度> 1的子串

We cannot apply the following approach here directly:

我們無法在此處直接應(yīng)用以下方法：

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.

因?yàn)?#xff0c;盡管1 < ; 2，如果我們也否定最后一個(gè)1，我們將得到無效的數(shù)字集，如上所示。 因此，這種簡單的方法或檢查在這里行不通。

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.

這里談到的布爾變量，如果它告訴我們，給定一個(gè)指標(biāo)i ，在數(shù)字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將具有在對數(shù)的能力減少i — 1 。 在示例4 1 2 1 ，在索引1(基于0的索引)處取反1將使數(shù)字2(在索引2)的容量減少1。我們在此將數(shù)字的剩余值稱為容量。 在執(zhí)行檢查以查看數(shù)字是否可以取反時(shí)，我們需要考慮這種減少的容量。

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

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

number[i] < number[i - 1]

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

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

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.

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

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.

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

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.

但是，這個(gè)問題要求我們在進(jìn)行此類修改后實(shí)際打印出給出最小總和的最終數(shù)字集。 為此，我們需要使用一個(gè)父指針，該指針將告訴我們每個(gè)索引和布爾變量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的數(shù)字取反(如果可能！)給我們最小的總和，或者選擇忽略它給我們最小的總和。

回溯 (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.

現(xiàn)在是我們回溯以找到原始問題的解決方案的部分。 請注意，第一個(gè)數(shù)字的決定是進(jìn)一步傳播遞歸的原因。 如果第一個(gè)數(shù)字取反，則第二個(gè)數(shù)字為正，可以使用parent[2][true]找到第三個(gè)數(shù)字的決定。 同樣，如果第一個(gè)數(shù)字未取反，那么我們移到第二個(gè)數(shù)字，可以使用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).

如果您看一下所建議解決方案的空間復(fù)雜性，您會發(fā)現(xiàn)它是一種二維動態(tài)規(guī)劃解決方案，因?yàn)檫f歸的狀態(tài)由兩個(gè)變量表示，即索引i表示我們正在考慮的數(shù)組數(shù)量以及然后是布爾變量is_prev_negated 。 因此，空間復(fù)雜度和時(shí)間復(fù)雜度將為O(n * 2)，本質(zhì)上為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提出了一種更好的方法來解決此問題。 這個(gè)問題甚至可以通過基于一維動態(tài)編程的解決方案來解決。

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 .

本質(zhì)上講，布爾變量is_prev_negated可以幫助我們確定是否可以對索引i處給定的數(shù)字取反，就數(shù)組的左側(cè)而言，即all the numbers from 0 .. i-1因?yàn)橛沂譄o論如何，這邊都是安全的，因?yàn)樵撨叺乃袛?shù)字都是正數(shù)(因?yàn)檫f歸尚未到達(dá)它們)。 因此，對于右側(cè)，我們僅檢查i+1處的數(shù)字，但對于索引i的左側(cè)，我們必須使用布爾變量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.

事實(shí)證明，我們可以簡單地完全跳過此布爾變量，并簡單地向前看以確定是否可以取反數(shù)字。 這只是意味著如果您在索引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處，因?yàn)樵谶@種情況下， i+1和i+2處的元素都不能為負(fù)。

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處的數(shù)字，那么我們將跳轉(zhuǎn)到索引i+2因?yàn)樵谌魏吻闆r下，兩個(gè)連續(xù)的數(shù)字都不能取反。 因此，如果i處的數(shù)字為負(fù)數(shù)，則i+1處的數(shù)字必須為正。 吞下檢查的目的是確定i+2處的數(shù)字是否一定一定是正數(shù)，或者我們是否可以選擇是否取反。

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.

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

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.

我希望您能夠掌握上述算法的工作以及動態(tài)編程技術(shù)如何解決此問題。 我認(rèn)為這是一個(gè)有趣的問題，因?yàn)槟粌H必須使用動態(tài)編程，而且還必須使用父指針的概念來通過最佳解決方案追溯步驟并獲得問題中所需的答案。

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

出現(xiàn)字跡模糊跡象

總結(jié)

以上是生活随笔為你收集整理的出现字迹模糊迹象_改变迹象：如何使用动态编程解决竞争性编程问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。