Codeforces Round #741 Two Hundred Twenty One Solution (Java/C++)

Solution:

First, we define $b[i]=a[i]\cdot (-1)^{(i-1)}$, $sum(l,r)=\sum_{i=l}^r{b[ i]}$.

So for any i, b[i] is either 1 or -1. Therefore, if the final sum is 0, then there must be the same number of 1 as the number of -1. So there must be, if the sum is to be 0, then the length of this interval must be an even number.

Let me start with the conclusion:
When the length of the original interval is odd, you only need to delete one number to make the interval sum to 0.
When the length of the original interval is an even number, you need to delete one number to make an odd length, that is, you need to delete two numbers in total.
Of course, if the sum of the original interval is 0, there is no need to delete any numbers.

Let us prove:

We consider deleting the numbers which the index is x from [l,r]. We found that after deleting, sum(l,x-1) will not be affected in any way, and the value of sum(x+1,r) just needs to be multiplied by -1.
So we get that if the sum of the interval after deleting x is 0, there must be sum(l,x-1)=sum(x+1,r).

Now, let us assume that sum(l,r)>0, and r-l+1 is an odd number.
At the beginning, we set x=r, that is, we delete the rightmost number. At this point, if sum(l,x-1)=0, then this is the answer we want. Therefore, we only consider the case where sum(l,x-1)>0.
Next, we set x=r-1. Considering the interval sums on the left and right sides of x, we find that the value of sum(l,x-1)-sum(x+1,r) changes correspondingly with the change of x. The only possible changes are -2, 0, 2.
At the same time, we notice that when x moves to l, sum(l,x-1)=0, sum(x+1,r)>0.
Thus, as x changes from r to l, sum(l,x-1)-sum(x+1,r) changes from a value that must be greater than 0 to a value that must be less than 0. And each change can only be -2, 0, 2. Therefore, there must be such an x such that sum(l,x-1)-sum(x+1,r)=0.

Thus, we get that when r-l+1 is an odd number, only one number needs to be deleted.

Now the remaining question is how to find such x such that sum(l,x-1)-sum(x+1,r)=0.

After transforming the original equation, we can get: sum(1,r)-sum(1,x)=sum(1, x-1)-sum(1,l-1). After further transformation can be obtained: sum(1,x)+sum(1, x-1)=sum(1,r)+sum(1,l-1).

Therefore, we only need to maintain a prefix sum, and when calculating the prefix sum, record the corresponding index of sum(1,x)+sum(1, x-1) through the map. In this way, every time we only need to find out all the index whose sum is equal to sum(1,r)+sum(1,l-1), and then choose any one of these indexes that belongs to [l,r].

Code:

Java

C++