Unable to understand algorithm

Question

Here is the link of problem https://www.hackerrank.com/challenges/equal

I read its editorial and unable to understand it. And if you are not make any account on hackerrank then surely you will not see it's editorial so here is some lines of editorial.

This is equivalent to saying, christy can take away the chocolates of one coworker by 1, 2 or 5 while keeping others' chocolate untouched.
Let's consider decreasing a coworker's chocolate as an operation. To minimize the number of operations, we should try to make the number of chocolates of every coworker equal to the minimum one in the group(min). We have to decrease the number of chocolates the ith person A[i] by (A[i] - min). Let this value be x.

This can be done in k operations.

k = x/5 +(x%5)/2 + (x%5)%2 

and from here i unable to understand

Let f(min) be sum of operations performed over all coworkers to reduce each of their chocolates to min. However, sometimes f(min) might not always give the correct answer. It can also be a case when

f(min) > f(min-1)

f(min) < f(min-5)

as f(min-5) takes N operations more than f(min) where N is the number of coworkers. Therefore, if

A = {min,min-1,min-2,min-3,min-4}
then f(A) <= f(min) < f(min-5)

can someone help me to understand why this is necessary to check f(min),f(min-1),...,f(min-4)

Answer 1

Consider the case A = [1,5,5]

As the editorial said, it is intuitive to think it is optimal to change A to [1,1,1] with 4 (2 minus 2) operations, but it is better to change it to [0,0,0] with 3 (1 minus 1, 2 minus 5) operations.

Hence if min = minimum element in array, then change all elements to min may not be optimal.

The part you do not understand is to cater this situation, we know min may not be optimal as min-x maybe better, but how large is x? Well it is 4. The editorial is saying if we know x is at most 4, we can just simply brute force min, min-1...min-4 to see which one is the minimum without thinking too much.

Reasoning (Not proof!) for x <= 4

If x >= 5, then you have to use at least extra N type 3 (minus 5) operations on all elements which is definitely not worth.

Basically it is not a matter of the type of operation, it is because you need to use same operation on ALL elements, after you do that, the problem is not reduced, the relative difference between elements is still the same while you aim to make the relative difference to 0, you cost N operations for nothing.

In other words, if x >= 5, then x-5 must be a more optimal choice of goal, indeed x%5 must be the best goal.

---

(Below is TL;DR part: Version 2) Jump to the Last Section If You are Not Interested in the proof

In the process of writing the original solution, I suspect x <= 2 indeed, and I have tried to submit a code on HackerRank which only check minimum for f(min-x) where x <= 2, and it got ACed.

More formally, I claim

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 # of operation for element z to become k

(Beware the notation, I use F(), it is different meaning from f() in the question)

Here is the proof:

If (z-min)%5 = 1 or 2, then it needs at least (z-min)/5 + 1 operations, while (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1 operation, means F(min') = F(min)

If(z-min)%5 == 3 or 4, then it needs at least (z-min)/5 + 2 operations, while (z-min')%5 == 0 needs (z-min')/5 = (z-min)/5 + 1 operation, means F(min') < F(min) (or F(min') = F(min)+1)

So we proof

If 5> (z-min)%5 >= 3 and (z-min')%5==0, then F(min')< F(min) where min'=min-x

Now let's proof the range of x

As we assume (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 can never be >= 3 in order to make ((z-min)%5 + x%5)%5 == 0

If x = 2, then (z-min)%5 can be 3; if x = 1 then (z-min)%5 can be 4, to meet both conditions: 5> (z-min)%5 >= 3 and (z-min')%5==0

Thus 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 one can always generate array P, such that f(min') < f(min), as you can always repeat integer which can be improved by such method until it out number those integers cannot. This is because for elements that cannot be improved, they will always need exactly 1 more operations

eg: Let P = [2,2,2,10] f(min) = 0+3 = 3, f(min-2) = 3+2 = 5

Here 10 is the element which can be improved, while 2 cannot, so we can just add more 10 in the array. Each 2 will use 1 more operation to get to min' = min-2, while each 10 will save 1 operation to get min'. So we only have to add more 10 until it out number (compensate) the "waste" of 2:

P = [2,2,2,10,10,10,10,10], then f(min) = 0+15 = 15, f(min-2) = 3+10=13

or simply just

P = [2,10,10], f(min) = 6, f(min-2) = 5

(End of TL;DR part!)

---

EDITED

OMG THE TEST CASE ON HACKERRANK IS WEAK!

Story is when I arrive my office this morning, I keep thinking this problem a bit, and think that there maybe a problem in my code (which got 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;
}

Can you see the problem?

The problem is m = max(0, m); !

It ensure that min-x must be at least 0, but wait, my proof above did not say anything about the range of min-x! It can be negative indeed!

Remember the original question is about "adding", so there is no maximum value of the goal; while we model the question to "subtracting", there is no minimum value of the goal as well (but I set it to 0!)

Try this test case with the code above:

1
3
0 3 3

It forces min-x = 0, so it gives 4 as output, but the answer should be 3

(If we use "adding" model, the goal should be 10, with +5 on a[0],a[2], +5 on a[0],a[1], +2 on a[1], a[2])

So everything finally got right (I think...) when I remove the line m = max(0, m);, it allows min-x to get negative and give 3 as a correct output, and of course the new code get ACed as well...