At each turn, take the maximum element and the minimum element, and reduce each by 1. At this point the second point still holds true.

Consider the case when the maximum element got reduced by 1, and it became not the maximum. Then the sorted array looks like this:

$$$....., x, x - 1.$$$

Since the total sum is still even, there is another positive element ($$$\ge 1$$$), apart from these two. Then $$$x \le (x - 1) +$$$ "some elements, at least one of which is 1". So the second point still holds, and we continue with x as the maximum element.

I'll have a crack at a possible explanation.

The problem statement instructs us to pick 2 distinct indices and reduce each element by 1. Suppose the point in consideration "The biggest element has to be less or equal than the sum of all the other elements." were to be false. Let this biggest element be at index i. For all other indices j, if we pick (i, j) as our pair and reduce their values by 1, we should be able to see that it won't be possible to reduce the largest element to 0.

How this test case correct answer is YES, for problem 2? Can anyone explain that?

5

1000000000 1000000000 1000000000 1000000000 1000000000

Here is another way to think about it.

Consider 2 cases:

• Base case: the largest element is equal to the sum of all the others:

Let's say that each element of the array represents the number of marbles of a given color. We can take 2 bowls. On the 1st, we put all the marbles of the largest number, while on the 2nd we put all the remaining ones. On each operation, we can take one marble from both of them. As they contain the same number of marbles, they will become empty at the same time and we are finished!

• Second case: the sum is bigger than the largest element:

We will try to reduce this to the above case! Again, we fill the bowls with the same way. The difference is that now the 2nd bowl has more marbles. To solve this, we can begin picking pairs from it until they are equal! Note that, as the sum is an even number, the parity of the number of marbles on each bowl is the same (ie. both odd or both even). That guarantees us that we will 100% reach a point that they are equal!

First you must realize that finally, in last step of reduction, the array will be of form: 1 1 0 0 0 0...... So if we backtrack from here to generate all possible arrays, at each step you increment the whole sum of array by 2, but for any element, you can only increase it by 1 in that step.So even if a single element is focused on every time, max(arr[i])<=sum/2. Hope it helps!

One more proof:

Let's make an optimal selection of pairs — we would have P pairs and U unassigned.

1). If U is empty — we can zero array

2). If U is odd — sum of an array was odd and the answer is NO

3.1). If U is even and has more than 2 elements — all U must be coming from a single A[i] because our selection is optimal.

3.2). If there is a pair in P (a, b) and both a and b are not from i — we can reassign 2 elements from U and a, b and make U lower. Which is impossible because our selection is optimal. Thus, all pairs in P has one element from A[i] and other element from somewhere else. So it means, A[i] = U + P, and sum(A) - A[i] = P. A[i] must be biggest element and it is bigger than half of sum(A)

Explaining the case where the maximum element is less than the sum of the remaining elements:

Let's call the maximum element X, the sum of the remaining elements remSum and X+remSum is the total sum.

Since X+remSum must be even, then X and remSum must both be even or odd, then for remSum to be greater than X it has to be greater by an even amount remSum = X+2*k, otherwise the total sum won't be even.

Consider the case where X = 5 and remSum = 7 Notice: remSum is greater than X by 2 (an even amount)

1, 1, 2, 3, 5 where X = 5 and remSum = 1 + 1 + 2 + 3

decrease remSum by 2 using any pair of elements from remSum, e.g. the pair at indices 0 , 3

the resulting elements are 0, 1, 2, 2, 5

Now X = 5 and remSum = 5, subtracting X from all elements of remSum will then result in an array of all 0's.

Using this fact, we are sure that for any case where remSum > X and remSum+X is an even number, we can always remove the extra even amount 2*k from remSum and reach a feasible state where the sum of the remaining elements is equal to the maximum element.

he made the question and god knows the proof ..

I am 18 months late, if anyone still has a doubt...here you go

Let the elements of the array be [a,b,c,d] where d is the largest element

Let us assume d is smaller than or equal to a+b+c (sum of all other elements)

d = a+b+c — delta

we know that d+a+b+c is even, 2(a+b+c) — delta is even and hence delta must be even.

Now, we can keep picking any 2 elements from [a,b,c] and reduce them delta/2 times so that d becomes equal to a+b+c...

I am not sure, but try to swap rows "cin.tie(0)" and "iostream..."

in using colum[where[j]+k], where[j]+k is an invalid index. it is accessing an index beyond size of the vector.

Was binary search actually necessary? I thought that simply sorting and maintaining how many elements would require updating to increase the median for each i between n / 2 and n would suffice.

For instance, if the initial median were some 'x' and the successor of 'x' were to be 'y' in the given array, it would require 'y' — 'x' updates to make 'x' = 'y'. Now, as any further increments to 'x' would yield 'y' as the median, it mandates updating both terms (equal to 'y') to their succeeding value. This can be maintained using a 'termsToUpdate' counter.

Note that the array has to be sorted.

Sorry, I didn’t notice that the array in this problem is not sorted. It was hard to notice it for me because I have the same problem with sorted array in Polygon. Of course I meant linear solution with sorted array. Sorry for misunderstanding.

58273442 Is that what you meant?

Well, if we ignore the complexity of sorting the array then we can just iterate from i=n/2 to i = n-1 and keep making all elements between n/2 to i. equal to A[i]. We break the loop if k goes negative. Here is code. https://codeforces.net/contest/1201/submission/58290181

Igoring sorting, my solution is pretty fast.58914655

Every time you reach a row that has treasure, you have to get all treasure before you go to the next row, so you will finally stop at the leftmost or the rightmost treasure. It's the same for the next now that has treasure. So you can just calculate the cost of 4 paths: L1->L2 / L1->R2 / R1->L2 / R1->R2 , and save the minimum of L2 and R2 for the next row, continue to do the same thing.

O(nlogn) + O(nlogn) = O(nlogn)

Closest safe columns right to the leftest treasure, left to the leftest treasure and same for rightest treasure.

Why there must be a treasure to the left of it?

That doesn't ensure minimum number of moves.

1 2 3 6 8 -> 1 2 3 0 2 -> 1 1 2 0 2 -> 0 0 0 0 0 // done

What do you think? Looks greedy to me

Yeah, specifically the method of applying binary search in this condition.How do you realise that binary search must be done?

I think we can simply use dijkstra algorithm as this is akin to minimum cost to reach destination from source problem, where there are 4 nodes in every row

58326485

consider 5 2 2 2 2 2