You have to focus on the difference. If every other colleagues receive a chocolate (because you have the greatest number of chocolates) the difference between your number of chocolates and the colleagues number will decrease.

That's still not really a problem: we only need to get the same amount of chocolate to everyone, not to get to 0 chocolates (when we think about this as subtraction)! In most cases, this just means lowering everyone's total to the min, and thinking about it this way gives the correct answer most of the time (as far as I can tell).

However, we run into some other problems when it would be "better" for us to have a lower min: what if we have 7 7 7 4 4 3? We could lower all of these to 3 in 8 moves (2x -2 for each 7, 1x -1 for each 4), but if we lower everything to 2, then we get fewer moves (1x -5 for each 7, 1x -2 for each 4, 1x -1 for the 3).

Passed all tests:

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector <int> a(n);
        for (int i=0;i<n;i++) cin >> a[i];
        
        // giving x chocs to every colleague other than chosen one 
        // is the same as taking away x chocs from the chosen one
        int min=*min_element(a.begin(),a.end());
        int numops=0;
        
        // consider taking away 5 chocs first (nChocs)
        for (int i=0;i<n;i++) {
            int nChocs=floor((a[i]-min)/5.0);
            a[i]-=(5*floor((a[i]-min)/5.0));
            numops+=nChocs;
        }
        min=*min_element(a.begin(),a.end()); // min of leftovers in a[]
        
        // fine tuning for last calc, get freq of diff first
        vector <int> freq(5); // stores diff of 0 to 4
        for (int i=0;i<n;i++) freq[a[i]-min]++; 
        
        // case of min num of chocs is min
        int extra_numops=1*(freq[1]+freq[2])+2*(freq[3]+freq[4]);
        
        // case of min num of chocs is min-1
        int extra_numops1=1*(freq[0]+freq[1]+freq[4])+
                          2*(freq[2]+freq[3]);
        if (extra_numops1<extra_numops) extra_numops=extra_numops1;
        
        // case of min num of chocs is min-2
        int extra_numops2=1*(freq[0]+freq[3])+
                          2*(freq[1]+freq[2]+freq[4]);
        if (extra_numops2<extra_numops) extra_numops=extra_numops2;

        cout << numops+extra_numops << endl;
    }
    return 0;
}

4 4 3; 7 4 6; 7 7 9; 8 8 9; 9 9 9

Make [][] diff of size [n] [4] rather than [n][n].

@Oleksandra28 I too didn't get that when I started the solution. But then it made sense after following the discussions here..

Think of this scenario. There are three inters with the chocolate count as follows: 5, 3, 3. In this case you can choose the intern with 5 chocolates and add 2 chocolates to other interns to make the chocolate count 5, 5, 5 or you can choose the intern with 5 chocolates and take 2 chocolates from him to make the chocolate count 3, 3, 3. Both require 1 operation. Does this make sense?

its memoization

Hi rmeghwal! If you are talking to me (it is not obvious from the comments arrangement), then I would like to point out, that my approach is not about making all zeros, but about making all the same. For that purpose I sort out the array first. After that, you see the following picture:

|  |   |   |    |
   |   |   |    |
           |    |
                |

The figure above is the visualization of numbers sorted in increasing order. After that you have to choose a pivot and increase the rest by either {1,2,5}, and repeat it utill all the numbers are the same. Intuitive step is to put pivot on greater number and adapt the smaller numbers to it and so on. Thus, we traverse the array, and at each iteration we choose current number as pivot, then adapt the prefix array to it. The total number of steps is the sum of steps required in each iteration. But sometimes encreasing the suffix array by either {1,2,5} can give the best result, due to discreteness of the steps. Therefore we need to select the minimum result among all options. You can check that out by yourself for correctness. If you still think that you are doing the same, please show me your code.

rather it can be written as f(c-(min-i)), now it might be clear to you why

As others have also explained very well. It would be easy if we do it other way that is using Reduction. Min(Elements) is 1. So min-1 and min-0 are 1 and 0. Considering two cases: i) Reducing it to 1: 1 --> 1 = 0 oper, 5 --> 1 = 2 oper and 5 --> 1 = 2 oper. Hence total 4 operations are required. ii) Reducing it to 0: 1 --> 0 = 1 oper, 5 --> 0 = 1 oper and 5 --> 0 = 1 oper. total 3 operations are required.

Therefore min(4,3) we choose reducing it to 0 instead of 1. So answer is 3.

By the way, if you do it by Increasing, still 3 operations required, just follow this: 1- 1,5+1,5+1 -- 1,6,6 2- 1+5,6,6+5 -- 6,6,11 3- 6+5,6+5,11 -- 11,11,11

1 (5) 5 ->adding 5
6 5 (10) ->adding 5
(11) 10 10 ->adding 1
11 11 11

The answer is 3 only.

Miss print, it should be 1, 2 and 5

First of all, change

steps += gap/3 ; gap = gap% 3;

to

steps += gap/2 ; gap = gap%2;

There's been an error in statement/test cases. At some point of time statement said "For each operation, she can give 1,3,5 chocolates to all but one colleague" but test cases were made for "1, 2, 5".

Hi! First we must realize that adding to all but the chosen one is the same as subtracting from only the chosen one.

Then the other idea is that we must find the optimal solution. For example, 0 4 4 could be solved like this: 0 4 4 --> 0 4 2 --> 0 4 0 --> 0 2 0 --> 0 0 0 -->

But the optimal solution is this: 0 4 4 --> 0 4 -1 --> 0 -1 -1 --> -1 -1 -1 -->

This is what I call the 'base'. and I add it to the delta, and it turns out you have to make at least 3 trials. Hope this helps.

Additional comment for clarity. The bases are there because adding to all but the chosen one is not completely the same as subtracting from only the chosen one. (Not until we consider adding the bases 0, 1, 2).

For example, to elaborate on the given example, if we had 0 4 4, under the division of (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1 without bases, we technically cannot account for the option of -5 because we can't apply that to the number delta 4 (or if delta = 3 for that regard). Try running through delta = 4 on your own and you'll see what I mean.

Adding +1 (or +2 for delta = 3) here would fix that problem. We only need bases 0, 1, 2 to account for delta = 3 or 4. Once delta = 2, the superior choice would be to -2 and not -5, so we don't need additional bases.

Yes you are right! Thx

Yes this helps us to change our range update to a single element update !

yeah, really weird. Don't know why they changed both the problem statement and the examples in the problem statement to use {1,3,5}, but all the testcases are still {1,2,5}.

here, we have to equalize the number of chocolates that each person has. I have categorized the solution into four steps -

1> first thing you have to understand is that giving some chocolates to everyone except one is same as taking away chocolates from one of them. for example - Out of 4 people in a competition,3 gets selected for next round --> 1 person loses. Out of 4 people in a competition, 1 person loses --> 3 gets selected for next round.

2> Using the set of numbers which are given in the question (1,2,5), we can reduce any given value(say 201) to any desired value(say 0,10,37,99....upto 200).So, logically, we would want to reduce the rest of the numbers in the array to the minimum value in it and calculate the number of steps.

3>Now,we require the minimum number of steps, so for every element in array,first we will find the difference between the minimum value in array with the current element and divide it by 5(start with largest number in the set to smallest), then the remainder is divided by 2 and then by 1 and count the number of steps.

2 2 3 7 --> 2 2 2 7 --> 2 2 2 2 (2 steps)

4>But, here comes the tricky part. lets say the input is - 3 6 6. Based on our logic, 3 6 6 --> 3 4 6 --> 3 3 6 --> 3 3 4 --> 3 3 3 (4 steps)

but, there is another minimal way 3 6 6 --> 1 6 6 --> 1 1 6 --> 1 1 1 (3 steps)

So, we will have to check for all the values (min,min-1,min-2,min-3 and min-4) to find out the best possible solution out of all the options.

Hope it helps!

You should do two additional per element subtractions by "mini - 1" and "mini - 2" where the smallest element becomes 1 and 2 instead of 0.

Considering the input 1 3 1 5 5 it's not beneficial to transform the array to zero baseline shape 0 4 4 since the algorithm will break the two fours into two 2s resulting in four operations. Correct answer would be three operations.

int count_operations(vector<int> counts_choc)
{
    int min_elem = *min_element(begin(counts_choc), end(counts_choc));
    int n_ops0 = 0; //number of operation assuming base 0
    int n_ops1 = 0; //number of operation assuming base 1
    int n_ops2 = 0; //number of operation assuming base 2
    for(int colleague = 0; colleague < counts_choc.size(); colleague++)
    {
        counts_choc[colleague] -= min_elem; //smallest element 0
        n_ops0 += counts_choc[colleague]/5;
        n_ops0 += (counts_choc[colleague]%5)/2;
        n_ops0 += (counts_choc[colleague]%5)%2;
        counts_choc[colleague] ++; //smallest element 1
        n_ops1 += counts_choc[colleague]/5;
        n_ops1 += (counts_choc[colleague]%5)/2;
        n_ops1 += (counts_choc[colleague]%5)%2;
        counts_choc[colleague] ++; //smallest element 2
        n_ops2 += counts_choc[colleague]/5;
        n_ops2 += (counts_choc[colleague]%5)/2;
        n_ops2 += (counts_choc[colleague]%5)%2;
    }
    
    return min(n_ops0, min(n_ops1, n_ops2));
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n_tests;
    cin >> n_tests;
    vector<vector<int>> data;
    for(int test = 0; test < n_tests; test++)
    {
        int n_colleagues;
        cin >> n_colleagues;
        vector<int>counts_choc;
        for(int colleague = 0; colleague < n_colleagues; colleague++)
        {
            int count;
            cin >> count;
            counts_choc.push_back(count);
        }
        data.push_back(counts_choc);
    }
    for(int test = 0; test < n_tests; test++)
    {
        cout << count_operations(data[test]) << endl;
    }
    return 0;
}