Can you all kindly please share your approach to Reduction Game Problem.
My approach was :- To keep A_n aside. And work with A from 1 to (n-1). In each iteration, we check for Compare value of min(A_i, A_(n-1)), and if value of this min is > k decrement both, A_(n-1) and A_i and I am continuously sorting array. Here is my code for reference. I know my
[1] will get TLE for highest constraints mentioned in problem, but can you help me optimize my code ?
Please share your approaches.
[1]: http://p.ip.fi/LEpo
My initial approach was same and you can optimise it further by taking decrement value = minimum(|a[i]-k|,|a[n-1] - a[n-2]|) but still not sufficient:(
We can infer below observations:
1. We want to maximise Resultant sum after performing possible decrements
2. We wan directly add elements <= k and remove them… Further decrease remaining elements by k and add k to our answer for each of them(since each would be atleast k)…Now we have new g elements and solve them for k=0 (for easy calculations I did this modifications)
3. Now our Aim is to maximise (Resultant value of g elements)
4. That is we want to maximise ( Greatest element(M1) - Resultant value of remaining (g-1) elements)
5. That is we want to minimise (Resultant value of (g-1) elements)
6. This would have two cases:
… I)… If second highest element(M2) is greater than Sum of remaining (g-2) elements then their minimum Resultant value = M2 - Sum of(g-2 elements)
…II)… Else this (g-1)elements would cancel out each other and either 0 or 1 would remain depending on their sum is even or odd(since we can decrement only in pairs)
Thus we can solve it with Time Complexity : O(n)
Here is my
[1]
I am not sure it would definitely work but it passed all the random cases I tried...your suggestions are most welcomed...Also if any confusion you are free to discuss :)
[1]: http://jdoodle.com/a/KvV
Just have a look at this problem. Think how you are tackling the case when you just take moves like (x,y,z) → (x+1,y+1,z) . Now generalise that to this: Given an array of n integers, you choose 2 integers at any time and reduce them by 1 each. Number of moves to make the whole array 0 or print if it is impossible to make. Now you are done. If you are still struggling have a look at my approach for that problem and here I explained my approach. (Its badly formatted though :p)
Basically my approach was to sort the given values and find the portion that has values above k. This allowed me to calculate a base sum which is effectively limiting every entry to max k, then work on the excess over k on the relevant large elements.
The basic idea is to try to leave the largest component as big as possible. To do this you want to reduce the second-largest component as much as possible by the smaller components. Then the remainder, if any, gets subtracted off the largest value. Finally if the second-largest component can be reduced completely by the smaller ones, you may still need to take one off the largest bar to ensure that parity is correct, since you always reduce by two in sum.
As you can tell by the above, you can treat the cases of 0, 1 or 2 values above k as special simpler cases.
By following this approach you would definitely reach to 0/1 if maximum<=sum(remaining elements):-
while(n>1) { max–; min–; Discard if 0 }
Solve it manually and see the pattern how the elements form pair and reduce each other…For exact proof you may try it by Induction…But I think an algorithm is enough to prove that there is always a way
Suppose the sum of the first g-2 elements is greater than g-1’st element. Therefore, there have to be at least 2 elements, both smaller than g-1’st element in the g-2 elements. Let the element at g-1 be x and the sum of the first g-2 elements be y. Since there are at least two elements in the first g-2, we can pair some of them up (y-x)/2 times to make the sum of them just smaller than x. Then we can conveniently pair all the remaining elements with the g-1’st element. If in turn, the sum was originally less than x, the optimal way is to pair everything with g-1’st element.
and you can optimise it further by taking decrement value = minimum(|a[i]-k|,|a[n-1] - a[n-2]|) but still not sufficient:(