hey namdx, could you explain the concept of how giving chocolate bars to all but one is equivalent to taking chocolate bar from 1 only.

Maybe we can give some details for tricky part: we don't know how many chocolates to give at the beginning to get the mininal path. For example let's take as initial problem "1 2 4" and compute the difference between the minimum colleague (=1) and the others so you start with "0 1 3" :
if you add +5 chocolates, you get "6 7 4" and the difference increases to "2 3 0" => not good!
now add +2 chocolates so you get "3 4 4" and the difference is decrease to "0 1 1" => much better!!!
adding +1 chocolates "2 3 4" and "0 1 2" => intermediate solution.
So the optimal first move is adding +2 chocolates for every colleagues excepted the last one.

I actually made the very same reasonning and I have a code in O(n). I think they proposed to solve things using DP to voluntarily disturb the programmer. I am getting addicted to this website.

Thanks for your explanation!

Thanks. The solution worked for me but my code is getting timed out for certain test cases. The complexity is O(N^2). Any suggestions? Link - https://www.hackerrank.com/challenges/equal/submissions/code/19605416

so muuuuuuuch appreciate for your help

How come "giving chocolate bars to all but chosen one" is equivalent "taking away the chocolate bar(s) from each chosen one until every one is equal"?

This question can be tagged dynamic programming. Because in the main solution part, we memorize the differences. The nutshell of dynamic programming is memorization. It is clear from this slice of code from my solution:

static final delta[] = {0,1,2,5};
private static int solve(int a[]){
        Arrays.sort(a);
        int res = Integer.MAX_VALUE;
        for(int j = 0;j<delta.length;j++){
            int ans = 0;
            int d = 0;
            a[0]-=delta[j];
            for(int i = 1;i<a.length;i++){
                int diff = a[i]-a[i-1]; // refer to prev elements
                ans+=getMinSteps(diff+d);
                d+=diff; // memorizing diffs
            }
            a[0]+=delta[j];
            res = Math.min(res, ans+(delta[j] == 0?0:1));
        }
        return res;
}

Hi, I also used the same, but I am unable to findout correct solution if input is 1 5 5 10 10.

After first step(value-min) : 0, 4, 4, 9, 9

step required to make all zero = 0+2+2+3+3=10

but if we try to do in this way like

0, -1(4-5),-1(4-5),-1(9-2*5), -1(9-2*5) => total steps= 0+1+1+2+2;

-1, -1, -1, -1, -1 => total step = 1+0+0+0+0 = 1
So total operation is 7.

Please let me know if I am doing something worng/incorrect.

regarding f(c-min+i), why i?

i feel the approach of namdx is correct. for the first problem given with values 2 2 3 7 we can get the reach to the final result by taking away the value from one instead of adding to others. here if we remove 1 from 3 the set becomes 2 2 2 7 and then remove 5 from 7 we get 2 2 2 2 hence the final result remain same 2

please help me someone. why for input .

1
3
1 5 5

output is 3 
but ans should be 4 as
 
1- 1+2,5,5+2 -- 3,5,7
2- 3+2,5,7+2 -- 5,5,9
3- 5+2,5+2,9 -- 7,7,9
4- 7+2,7+2,9 -- 9,9,9 
 
ans is 4

How many steps would it take to decrease 900 chocolates down to 0?

This is the step where the problem authors expect you to use Dynamic Programming. It looks to me like @namdx1987 is suggesting a greedy approach instead, which works perfectly for the "decrease" amounts of 1,2,5.

But there are other decrease amounts for which a greedy approach would not work (such as 1,3,4). So just a slight tweak to this problem would make Dynamic Programming necessary.

Since it's filed under "Dynamic Programming", the problem might be better off with a slight change to the "decrease" amounts. Regardless, I still really like this problem, and I think it's a neat twist off the classic change-making problem.

Thank you.

I really liked your approach. But can you please give away less. This comment is basically an editorial.

nice theory and idea

You're literally describing it as a dynamic programming problem. And claiming that it's not after every sentence.

How to select which one to decrement and by which amount(1/2/5)?

Can you explain why you have to iterate from 0 to 4?

Why 1 ,2 , 5. In qu it's given 1,3,5. Am i missing something??

@namdx1987 what is c??thx

Why are we only reducing 1,2,5 and not 1,3,5 ? Because if we add a 3 in all other but one the effect can be compared to reduction of 3 bars from the chosen person. And after choosing the person for decreement still it is similar to minimum coin (of fixed denomination) question. should we not use Dynamic Programming?

may i know why are you considering 1,2 or 5 where as in the question it is given as 1,3 or 5

// please tell if there is some minute error, I am getting very very close answers

include

using namespace std ;

// returns the number of steps needed to make value reach the target int steps(int target,int value) { long steps = 0; long gap = value - target ; if(!gap) return 0;

steps += gap/5 ;
gap = gap % 5 ;
steps += gap/3 ;
gap = gap% 3;
steps += gap/1 ;
return steps ;    

}

int main() { int testcases ; cin >> testcases ;

for(int i=0;i<testcases;i++)
{
    int n ;    // number of collegues
    cin >> n ;
    int arr[n] ;   int min = 9999;
    for(int i=0;i<n;i++)
    {
        int chocs; 
        cin >>chocs ;
        arr[i] = chocs ;
        min = (min<chocs)?min:chocs ;   // gets the minimum number out of the input elements

    }

    // soln[i][j] means steps needed to make elements till i th position reach to min - j .
    long soln[n][5] ;
    for(int i=0;i<5;i++)
    {
        soln[0][i] = steps(min - i , arr[0]) ;
    }


    for(int i=1 ; i<n ;i++)
    {
        for(int j=0;j<5;j++)
        {
            soln[i][j] = soln[i-1][j] + steps( min - j , arr[i]) ; // may be here is the issue
        }
    }

    long answer = 99999 ;
    for(int i=0;i<5;i++)
    {
        answer = (answer > soln[n-1][i])?soln[n-1][i]:answer ;
    }

    cout << answer << "\n" ;

}

}

This is just brilliant. Instead of 'increasing all but one', your idea focuses on 'decreasing one at a time' which makes it much more intuitive. B-e-a-utiful.

OK, so this was fairly challenging for me. I first pig-headedly went down the route of adding chocolates to all colleagues but one, and got partially there, but that was real hard and convoluted, and cases 11,12,13, and 15 were still failing. I then went back to this comment and accepted the idea that adding chocolates to all but one was equivalent to removing the same amount of chocolates to one colleague only. Way easier to write and read, but still the same cases were failing. So I read again the end of the comment about getting the minimum value from ops[i]=sum(f(c-min+i)), with i in {0,1,2,3,4}. And the resulting code passed all tests. But for the life of me I cannot figure out why by varying i between 0 and 4 we can get a better output. I'm guessing 4 because 4 is the last integer before 5, but that doesn't cut it. Could someone explain in layman terms why we should run 5 variations to obtain the best result please?

if we have {2,6,6,6} if i use addition approach it will be {(2),7,7,7} {7,(7),12,12} {12,12,12,(17)} {17,17,17,17} and know if i use subtraction approach i.e subtracting one ,two or five from one element at one time it will give me same number of operations . {1,6,6,6} {1,1,6,6} {1,1,1,6} {1,1,1,1} so number of operations are same in both the cases. now you got it

Can you explain how calculating min(op[i]) will give us optimal answer.

why do we have to iterate i from 0 to 4

Thanks for sharing this. Could you please help me in understanding in the below logic. I didnt understand what we are doing here.

for(int base = 0; base < 3; base++) { int current_sum = 0; for(int i = 0; i < cookies.length; i++) { int delta = cookies[i] - cookies[0] + base; current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1; } sum = Math.min(current_sum,sum); }

Your solution is O(n*log n) because of sorting. To make it O(n) just find minimum with linear search without sorting.

Its not showing correct answer

int delta = cookies[i] - cookies[0] + base; current_sum += (int)delta / 5 + delta % 5 / 2 + delta % 5 % 2 / 1;

hai i am not understanding the delta is the adding element or not.

My solution is similar to yours but it is not able to pass the last test case... its giving wrong result for a few sets. Can you please help me understand what I did wrong.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Main {
    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int n;
        int q1 = 0,q2 = 0,r1 = 0 ,r2 = 0;
        int sum = 0;
        int low;
        for(int ai = 0 ; ai < t ; ai ++){
            n = sc.nextInt();
            int[] a = new int[n];
            for(int i = 0 ; i < n ; i++){
                a[i] = sc.nextInt();
            }
           sum = 0;
           int k =0;
           long sum1 = 1000000000;
           Arrays.sort(a);
           low = a[0];
           for(low = a[0] ; low >= 0 ; low--){
             sum = 0;
           for(int i = 0 ; i < n ; i++){
               k = a[i]-low;
               //System.out.println(low + " " + a[i]);
               q1 = k/5;
               r1 = k % 5;
               q2 = r1/2;
               r1 = r1 % 2;
               sum = sum + r1 + q2 + q1;
               //System.out.println(a[i] + "---" + q1 + " " + q2 + " " + r1);
           }
           //System.out.println(sum + "");
           if(sum < sum1)
            sum1 = sum;
           }
           System.out.println(sum1); 
        }
    }
}

Thanks for the code and explaination.

Great remark, when you re-state the problem like this, it becomes easy. Thanks!

Thank you very much. When explain like that, the problems seem easier than

I did the same thing but my last testcase is going wrong :/

How does it make this easier?

The frustrating thing is that if you do the problem with 1,3,5 (as it is currently written) rather than 1,2,5 (which it should be), then your answers will end up being quite close to correct.

@amititkgp @hackerrank, any ideas on why this is done?