We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Best possible solution can be found from (min,min-1,min-2). I think we don't need to check for (min-3) and (min-4). I have submitted by calculating optimal from (min,min-1,min-2). Can you provide an example where min-3 or min-4 is more optimal ?

My code :

#include<bits/stdc++.h>usingnamespacestd;intmain(){intt,n;cin>>t;while(t--){cin>>n;intarr[n],i,op1=0,op2=0,op3=0,mn=10000,left;for(i=0;i<n;i++){cin>>arr[i];if(mn>arr[i])mn=arr[i];}for(i=0;i<n;i++){left=arr[i]-mn;// for (min)op1+=left/5;left%=5;op1+=left/2;left%=2;op1+=left/1;left=arr[i]-(mn-1);// for (min-1)op2+=left/5;left%=5;op2+=left/2;left%=2;op2+=left/1;left=arr[i]-(mn-2);// for (min-2)op3+=left/5;left%=5;op3+=left/2;left%=2;op3+=left/1;}op1=min(op1,op2);// optimal from min-1 and min-2cout<<min(op1,op3)<<endl;// Most Optimal}}

generally, in dp solution..we start with 1 and build up our solution till n..but i think here (min,min-1,min-2) will do. how did you conclude that we dont require min-3,min-4. Can you elaborate

6 9 9 => reduce 9 to 6 in Two Steps + reduce next 9 to 6 in Two Steps => Total 4. OR 6-2=9-5=9-5 => Total 3 Steps.

6 8 8 => 6-2=8-4=8-4 => Total 3 Steps. OR 6=8-2=8-2 Total 2 Steps. i.e. when the difference is '3' or '4' then we reduce them by '5' which is One Step (better than '2'+'1' OR '2'+'2') .

There is no need to go till min-3 or min-4. Solution passes all test case with just min, min-1, min-2. Makes sense too, logically. Taking min-1 as baseline is helpful for numbers that are min+4 as they can reach min-1 in 1 step (-5). They couldn't reach min or min-2 in 1 one step.

Similarily, Taking min-2 as baseline is helpful for numbers that are min+3 as they can reach min-2 in 1 step (-5). They would have to take 2 steps in reaching min or min-1.

Taking min-3 as baseline is not helpful for any numbers. min+1 number take 2 steps in reaching there. min+2 number takes one step in reaching (-5) but they could have easily reached min in one step too (-2) . min+3 number take 2 steps in reaching min-3 and 2 steps in reaching min again so we don't really need min-3.

## Equal

You are viewing a single comment's thread. Return to all comments →

Best possible solution can be found from (min,min-1,min-2). I think we don't need to check for (min-3) and (min-4). I have submitted by calculating optimal from (min,min-1,min-2). Can you provide an example where min-3 or min-4 is more optimal ?

My code :

generally, in dp solution..we start with 1 and build up our solution till n..but i think here (min,min-1,min-2) will do. how did you conclude that we dont require min-3,min-4. Can you elaborate

There is no need to go till min-3 or min-4. Solution passes all test case with just min, min-1, min-2. Makes sense too, logically. Taking min-1 as baseline is helpful for numbers that are min+4 as they can reach min-1 in 1 step (-5). They couldn't reach min or min-2 in 1 one step.

Similarily, Taking min-2 as baseline is helpful for numbers that are min+3 as they can reach min-2 in 1 step (-5). They would have to take 2 steps in reaching min or min-1.

Taking min-3 as baseline is not helpful for any numbers. min+1 number take 2 steps in reaching there. min+2 number takes one step in reaching (-5) but they could have easily reached min in one step too (-2) . min+3 number take 2 steps in reaching min-3 and 2 steps in reaching min again so we don't really need min-3.

Same logic can be applied for min-4 baseline too.