Consider the case A = [1,5,5]
As stated in the editorial, it’s intuitively clear that it’s optimal to change A to [1,1,1] using 4 (2 minus 2) operations, but it’s better to change it to [0,0, 0] from 3 (1 minus 1, 2 minus 5) operations.
Therefore, if min = minimum element in array , then changing all elements to min may not be optimal.
The part that you do not understand is to satisfy this situation, we know that min may not be optimal, since min-x may be better, but how big is x ? Well it's 4 . The editors say that if we know that x not more than 4, we can simply brute-force min , min-1 ... min-4 to find out which one is the minimum without thinking too much.
Reasoning (not proof!) For x <= 4
If x> = 5, you should use at least additional N operations of type 3 (minus 5) for all elements that are definitely not worth it.
In principle, this does not apply to the type of operation, because you need to use the same operation for ALL elements , after that the problem will not be reduced, the relative difference between the elements is still the same, as long as you are aimed at making the relative difference at 0, you stand N for nothing.
In other words, if x> = 5, then x-5 should be a better target choice, and indeed, x% 5 should be a better target.
(below TL; part DR: version 2) Go to the last section if you are not interested in proving
In the process of writing the original solution, I suspect x <= 2 , and I tried to send the code to HackerRank, which checks the minimum for f(min-x) where x <= 2 , and it got Aced.
More formally, I argue
If 5> (z-min)% 5> = 3 and (z-min ')% 5 == 0, then F (min') <F (min) where min '= min-x for x <= 2, F (k) = min # operations for element z to become k
(Beware of the notation, I use F() , this is a different value from F() in the question)
Here is the proof:
If (z-min)%5 = 1 or 2 , then this requires at least (z-min)/5 + 1 operations, and the operation (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1 means F(min') = F(min)
If (z-min)%5 == 3 or 4 , then this requires at least (z-min)/5 + 2 operations, and the operation (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1 means F(min') < F(min) (or F(min') = F(min)+1)
So the proof
If 5> (z-min)% 5> = 3 and (z-min ')% 5 == 0, then F (min') <F (min) where min '= min-x
Now let the proof be the range x
As expected (z-min)%5 >= 3 and (z-min')%5 == 0 ,
so (z-min')%5 = (z-min+x)%5 = ((z-min)%5 + x%5)%5 == 0
Now, if x >= 3 , then (z-min)%5 never be> = 3 to make ((z-min)%5 + x%5)%5 == 0
If x = 2, then (z-min)% 5 may be 3; if x = 1, then (z-min)% 5 can be equal to 4 to satisfy both conditions: 5> (z-min)%5 >= 3 and (z-min')%5==0
So together we show
If 5> (z-min)% 5> = 3 and (z-min ')% 5 == 0, then F (min') <F (min) where min '= min-x for x <= 2
Note: you can always create an array P such that f (min ') <f (min), since you can always repeat an integer that can be improved with this method until its number is an integer. This is due to the fact that for elements that cannot be improved, they will always need exactly 1 more operation
for example: Let P = [2,2,2,10] f (min) = 0 + 3 = 3, f (min-2) = 3 + 2 = 5
Here 10 is an element that can be improved, but 2 cannot, so we can just add more than 10 to the array. Each 2 will use another 1 operation to get to min' = min-2 , while each 10 will save 1 operation to get min' . Therefore, we need to add 10 more, until we select the number (compensate) "waste" 2:
P = [2,2,2,10,10,10,10,10,10], then f (min) = 0 + 15 = 15, f (min-2) = 3 + 10 = 13
or just just
P = [2,10,10,10], f (min) = 6, f (min-2) = 5
(End of TL; part of DR!)
EDITED
OMG TEST CASE ON HACKERRANK WEAK!
The story, when I come to my office this morning, I think a little about this problem and think that there is a problem in my code (which was ACed!)
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int T, n, a[10005], m = 1<<28; int f(int m){ m = max(0, m); int cnt = 0; for(int i=0; i<n;i++){ cnt += (a[i]-m)/5 + (a[i]-m)%5/2 + (a[i]-m)%5%2; } return cnt; } int main() { cin >> T; while(T--){ m = 1<<28; cin >> n; for(int i=0; i<n;i++) cin >> a[i], m = min(m,a[i]); cout << min(min(f(m), f(m-1)),f(m-2)) << endl; } return 0; }
Do you see the problem?
Problem m = max(0, m); !
This ensures that min-x must be at least 0, but wait, my proof above says nothing about the min-x range! It could be negative!
Remember that the original question is about “adding,” so there is no maximum goal; while we model the question by "subtraction", there is also no minimum goal value (but I set it to 0!)
Try this test case with the code above:
It forces min-x = 0, so it gives 4 as output, but the answer should be 3
(If we use the “added” model, the goal should be 10, from +5 to [0], a [2], +5 to [0], a [1], +2 to [1], a [2] )
So everything finally worked out right (I think ...) when I delete the line m = max(0, m); , it allows min-x to get a negative result and give 3 as the correct output, and of course the new code will also be ACed ...