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.
I think we don't need to use dynamic programming here. First of all, if you give chocolate bars to all but chosen one, it is equivalent to take away the chocolate bar(s) from each chosen one until every one is equal. So the challenge becomes decrease from each individual 1, 2 or 5 until all are equal. Second to calculate the ops we need to use to decrease an integer n until it reaches 0 (call it the function f) is equivalent to convert 1, 5 (no need to use dynamic programming here). Finally, to solve this challenge, we find the min (call it m) of the given list, then for i from 0 to 4, we find min of ops[i]=sum(f(c-min+i)) where c is each individual colleague and thus no need to use dynamic programming here :)
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.
@decuqa I have understood how the reduction will work. But i am unable to realise the same answer using the increment algo. For ex: 2 5 5 5 5 5, the operation count would be 6 as we reduce it to 0. But how in just 6 operations we can achieve this using increment technique which is our real problem statement. So, how exactly they are same in real?
Thanks. Got it.
But there is an cal error in your operations. Instead of 12 12 12 (19) 19 19, it should be 12 12 12 (17) 17 17.
Therefore, finally it would be 27 27 27 27 27 27.
logic is about making equal not zero.So in 2 5 5 5 5 5.If we reduce 3 from all 5 we left with each having 2 chocolate and that's what we want equal chocolates.
Thanks.But I got some other method which would solve by 4 operations please suggest any loop holes in my metghod.
step 1:place the values in the list
step 2:[1,3,5] are the possible ways to give chocolates
step 3: calculate minimum_of_list and maximum_of_list and index where maximum_of_list is present in list(if we have multiple maximum_of_list it has to return first_index)
step 4:diff = maximum_of_list - minimum_of_list
step 5:add the diff to all the list elements except to maximum_of_list
step 6:repeat step 3 to step 5 until all the values are equal in alist
Example:
(x):assume x is a small value
[x]:assume x is maximum_of_list
2 5 5 5 5
(2) [5] 5 5 5
(5) 5 [8] 8 8
(8) 8 8 [11] 11
(11) 11 11 11 [14]
14 14 14 14 14
It doesn't give optimal solution in all cases.
TC => 2 5 5 5 5 5
expected=> 6
actual=>10
I implemented it so I know. The problem occurs because we are always adding to lower elements which causes problems as it is not proved to be safe move.
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.
Finaly the problem becomes: "reducing the difference between the number of colleague chocolates".
But if we start immediately to answer this new problem we will have an issue: how to deal with this example : "4 4 3"? In this case it is better to not start the reducing part because the initial state is not optimal. Let's transform it to "4 5 4" and then "5 5 5" and removing -5 chocolates is quicker than removing -2 chocolates with the initial state ("4 4 3"). Five operations < six operations!
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).
The cost to equalize the colleagues is the sum of the reduce operations through all colleagues. Naturally you use as the baseline the minimum colleague and you are taking away from other colleagues until they are equal. However, given you can reduce by 1, 2, or 5, you naturally want to take bigger steps and use as many 5 reductions as possibly and then 2 and only after that reduce by 1.
Now imagine reducing the case 3 7 7. If you would be strictly equalizing them with the miminum colleague then you need to reduce them all to 3 in which case you cannot apply -5 because 7-5=2 is too low hence you need to apply -2 twice. In this case it is cheaper to adjust the minimum to 2. I.e. 377->327->322->222 is cheaper then 377->357->337->335->333.
Now thinking about it again, it is not necessary to calculate for 5 different baselines, 3 is enough: the minimum in the sequence M, M - 1, M - 2 (given M > 2).
In other words reducing by 1 or 2 is cheap (1 operation), by 3 or 4 is expensive (2 operations), 5 is cheap again. By cheaply reducing the basiline by 1 or 2 with a single operation reduction you can save multiple 2 operation reductions on other colleagues.
Very nice. This is one of those problems that once I see it explained well, it makes total sense. But coming to that solution on my own would be the tricky part. I suppose practice makes perfect... I am kind of just getting started with these kinds of problems.
Now if you compare partitions of delta and delta' into {1, 2, 5} it's evident that delta' has one more 5 in each element di' so compared to number of ops in delta it requires n extra -5 operations. For that reason each of the cases min-5, min-6 etc are always less optimal than cases min, min-1, ... min-4.
I dont find a generic algorithm with proof of correctness but everyone is trying to explain seme solution with a trivial example. Please correct me if I am wrong.
I'm not clear if you want the solution of the case: 3 coworkers with the following allocation of chocolates:
( 1 3 1123834 )
OR
the case 5 coworkes with the allocation (1 3 1 123 834).
Assume it's the first case. If it's the second just follow below steps closely.
First we find min { 1, 3, 1123834 } = 1. We have two cases and we need to try both and check which has less steps.
Case 1: target = (1 1 1)
delta = (1 3 1123834) - (1 1 1) = (0 2 1123833)
We next find min number of -5, -2 and -1 steps to get from (1 3 1123834) to (1 1 1)
0 = 0 * 5 + 0 * 2 + 0 * 1
2 = 0 * 5 + 1 * 2 + 0 * 1
1123833 = 224766 * 5 + 1 * 2 + 1 * 1
Total # of steps: (# of steps to make 0 -> 1) + (# of steps to make 2 -> 1) + (# of steps to make 1123833 -> 1) = (0 + 0 + 0) + (0 + 1 + 0) + (224766 + 1 + 1) = 224769
Case 2: target = (0 0 0)
delta = (1 3 1123834) - (0 0 0) = (1 3 1123834)
We next find min number of -5, -2 and -1 steps to get from (1 3 1123834) to (0 0 0)
1 = 0 * 5 + 0 * 2 + 1 * 1
3 = 0 * 5 + 1 * 2 + 1 * 1
1123834 = 224766 * 5 + 2 * 2 + 0 * 1
Total # of steps: (# of steps to make 1 -> 0) + (# of steps to make 3 -> 0) + (# of steps to make 1123834 -> 0) = (0 + 0 + 1) + (0 + 1 + 1) + (224766 + 2 + 0) = 224771
We see that case 1 requires fewer steps so min number of steps is 224769.
@hariharan90000
Had the same doubt seeing the above comments but no one mentioned why and i couldn't find any logic to that arguement.
It can be
There is nothing wrong with our M-x becoming -ive cause in the original question we are adding values to nos. so they can never be negative.It is just to make our compress our question we are subtracting and getting -ive values and so it won't affect the original problem.
Consider the eg:
1 4 4
M=1
if x = 0 M-x = 1
ans = 4
if x = 1 M-x = 0
ans = 4
if x = 2 M-x = -1
ans = 3 ( 1 4 4 1 6 6 6 6 11 11 11 11)
I had the same doubt and I think you're right. Considering the 1 4 4 example it should be necessary to take into account a -ve baseline as originally the question was of addition.
I like this explanation. After struggling with this problem for ages, implementing this method (almost) worked. But for input 15 only, my code still got WA about half the time when minimum%5==0, whether minimum==0 or some higher value. Can't work out why... So I ended up considering target=(min...min-4) for all inputs, which is slower but worked. I am not sure about the reasoning why target must always be >= 0.
Your explaination was really helpful in solving this question with just one minor change. I didn't imposed any condition on target and let that loop run from min to min-3 as it would satisfy the case 1 4 4 suggested by someone here by setting target at -1.
thank you.
@dragan_ostojic thank you for the explanation. Its amazingly clear and efficient. I just want to add that target >= 0 does not work for all cases. When the condition allows target to be -ve or +ve it works for all test cases
@baran_jana, In the above example, 377 is reduced to 333 using 2 operations, that is, 377 -> 355 and 355 -> 333. But I didn't follow how it is reduced to 222. In one operation if you are using 5 to reduce, then 377 -> 322. But how did 322 become 222? Can you please explain a bit?
@dragan_ostojic, thanks for your response. when we reduce 377 by 1, we need to choose one of the interns, and reduce every other by 1. This means, 377 should become 267 or 366. how did it become 277?
no, it's not how it works. if you reduce, you choose only ONE at a time. if you increase you choose all EXCEPT the one you chose when you reduce. these two problems are equivalent i.e. if you solve reduction problem you also solved addition problem. note that the problem as originally stated is addition. the reason we choose reduction approach is because it's simpler. let me demonstrate first reduction solution and then how you derive addition solution from it.
Reduction:
3 7 7->2 7 7->2 2 7->2 2 2
steps:
dec 1st by 1
dec 2nd by 5
dec 3rd by 5
Addition:
3 7 7->3 8 8->8 8 13->13 13 13
steps:
inc all BUT 1st by 1
inc all BUT 2nd by 5
inc all BUT 3rd by 5
This is how Christy the intern is required to solve it. But she will first pretend that she was asked to solve it by taking away one at a time. Once she did that she would know how to solve by adding chocolates.
Look at my response to an earlier question, I explained in detail how you exactly find the solution for any reduction problem. Once you know the steps for reduction problem you can easily derive the steps for the equivalent addition problem as required.
Hey, Baran Jana! I am getting some segmentation fault while using your logic. I am only checking for M,M-1 and M-2. Is there something else where I might be going wrong?
Yeah you said that right! Got ac with that! I wrote that >=0 condition and got wa in #13th case, But why this is happening? How can chocolates balance in negative lol!
I think answer is possible because real operations is giving choclates and making them equal and not make equal by removing. So we must just be concered with making them equal as we are removing choclates and making equal, answer will be correct even if we make it negative.
intmain(){intt;cin>>t;while(t--){intn;cin>>n;vector<int>a(n);for(inti=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 oneintmin=*min_element(a.begin(),a.end());intnumops=0;// consider taking away 5 chocs first (nChocs)for(inti=0;i<n;i++){intnChocs=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 firstvector<int>freq(5);// stores diff of 0 to 4for(inti=0;i<n;i++)freq[a[i]-min]++;// case of min num of chocs is minintextra_numops=1*(freq[1]+freq[2])+2*(freq[3]+freq[4]);// case of min num of chocs is min-1intextra_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-2intextra_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;}return0;}
I actually saw an explanation under another comment explaining this. It has something to do with; when to reduce 3/4 to zero it can be cheaper to do it via -5 (-1|-2) and reducing the and then others by 2|1.
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.
@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?
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:
staticfinaldelta[]={0,1,2,5};privatestaticintsolve(inta[]){Arrays.sort(a);intres=Integer.MAX_VALUE;for(intj=0;j<delta.length;j++){intans=0;intd=0;a[0]-=delta[j];for(inti=1;i<a.length;i++){intdiff=a[i]-a[i-1];// refer to prev elementsans+=getMinSteps(diff+d);d+=diff;// memorizing diffs}a[0]+=delta[j];res=Math.min(res,ans+(delta[j]==0?0:1));}returnres;}
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.
Hi Zhassan,
can you please look into my code and say where i am doing wrong (apart from time complexity),
t1 = 1
t3 = 3
t5 = 5
for _ in range(int(input().strip())):
l = int(input().strip())
c = [int(f) for f in input().strip().split(' ')]
e = 0
count = 0
while(max(c)!=min(c)):
count += 1
mi = min(c)
mx = max(c)
d = mx-mi
if d >= t1 and d < t3:
e = t1
elif d >= t3 and d < t5:
e = t3
elif d >= t5:
e = t5
for i in range(len(c)):
if c[i] != mx:
c[i]+=e
print(count)
#print(c)
my answer - 933
expected - 10605
but still all are having same numbers of chocolates.
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
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
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.
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?
// 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" ;
}
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".
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?
Equal
You are viewing a single comment's thread. Return to all comments →
I think we don't need to use dynamic programming here. First of all, if you give chocolate bars to all but chosen one, it is equivalent to take away the chocolate bar(s) from each chosen one until every one is equal. So the challenge becomes decrease from each individual 1, 2 or 5 until all are equal. Second to calculate the ops we need to use to decrease an integer n until it reaches 0 (call it the function f) is equivalent to convert 1, 5 (no need to use dynamic programming here). Finally, to solve this challenge, we find the min (call it m) of the given list, then for i from 0 to 4, we find min of ops[i]=sum(f(c-min+i)) where c is each individual colleague and thus no need to use dynamic programming here :)
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.
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.
@decuqa I have understood how the reduction will work. But i am unable to realise the same answer using the increment algo. For ex: 2 5 5 5 5 5, the operation count would be 6 as we reduce it to 0. But how in just 6 operations we can achieve this using increment technique which is our real problem statement. So, how exactly they are same in real?
(2) 5 5 5 5 5
2 (7) 7 7 7 7
7 7 (12) 12 12 12
12 12 12 (19) 19 19
19 19 19 19 (24) 24
24 24 24 24 24 (29)
29 29 29 29 29 29
It's a same choice.
Thanks. Got it. But there is an cal error in your operations. Instead of 12 12 12 (19) 19 19, it should be 12 12 12 (17) 17 17. Therefore, finally it would be 27 27 27 27 27 27.
Possible in 5 step.
You Miss this condition you give chocolate bars to all but chosen one. so you wont able to give chocolates to all at once.
They should really bold this in the question. I didn't realize this making the problem seem very hard for me.
In second step, U have added 3, but addition of 1, 2 and 5 is ony possible
logic is about making equal not zero.So in 2 5 5 5 5 5.If we reduce 3 from all 5 we left with each having 2 chocolate and that's what we want equal chocolates.
what's woring in it?
We need to add to all except one element. You are adding to just one element.
12 12 12 (19) 19 19 19 19 19 19 (24) 24 ???
we can end it at 13 13 13 13 13 13 also but operations required are 6 only.
Thanks.But I got some other method which would solve by 4 operations please suggest any loop holes in my metghod. step 1:place the values in the list step 2:[1,3,5] are the possible ways to give chocolates step 3: calculate minimum_of_list and maximum_of_list and index where maximum_of_list is present in list(if we have multiple maximum_of_list it has to return first_index) step 4:diff = maximum_of_list - minimum_of_list step 5:add the diff to all the list elements except to maximum_of_list step 6:repeat step 3 to step 5 until all the values are equal in alist Example: (x):assume x is a small value [x]:assume x is maximum_of_list 2 5 5 5 5 (2) [5] 5 5 5 (5) 5 [8] 8 8 (8) 8 8 [11] 11 (11) 11 11 11 [14] 14 14 14 14 14
Have you implemented this approach??
the ways to give choclates is {1,2,5} and not {1,3,5}
That's not what the problem states.
I guess you figured out that statement has changed since. It was {1,2,5} two months ago
You cannot add 3 to any number. # will be added as combination of 1 and 2 which leads to 2 operation. Eveny my approach was same but got it wrong.
Could you please tell me how to solve 1 2 3 4 5 6
somebody changed the problem to [1,3,5] from [1,2,5] but didn't change the solutions
Yup.
In bird culture that is considered a dick move
Spent a few hours debugging my solution before going to forum in desperation and reading this comment...
Has this been resolved now?
if the difference is other than 1,2,5 how will you proceed next??
This would have slow performance.
It doesn't give optimal solution in all cases. TC => 2 5 5 5 5 5 expected=> 6 actual=>10
I implemented it so I know. The problem occurs because we are always adding to lower elements which causes problems as it is not proved to be safe move.
Also it give TLE.
yup according to
edemohankrishna1
Shouldn't be 3 2 3 5 7 1) 7 8 10 (7) 2) 10 11 (10) 10 3) 11 (11) 11 11
How did you decide you need to add 2 for the first iteration and 5 for the second iteration ?
(2) 5 5 5 5 5 (5) 5 8 8 8 8 (8) 8 8 11 11 11 (11) 11 11 11 14 14 (14) 14 14 14 14 17 (17) 17 17 17 17 17
only 5 steps
Yeah, with the differene method, 5 is coming only. But, in the test case it is saying 6 steps
@singhavdeshk for 2 5 5 5 5 5 operartion count will not be 6 it will be 5 2 5 5 5 5 5 5 5 8 8 8 8 8 8 8 11 11 11 11 11 11 11 14 14 14 14 14 14 14 17 17 17 17 17 17 17
This case operation count : 5
Please let me know if I am doing something wrong..
@iam_byungwoo :
you are correct; for the input [2, 5, 5, 5, 5], a minimum of 5 operations will suffice.
However, @singhavdeshk enquired about a different input [2, 5, 5, 5, 5, 5], which requires a minimum of 6 operations.
Thank you for your answer.
for [2,5,5,5,5] need 4 opration
You should look at your answer again. How did you add a 3 in 1 single operation?
Looks like the proble statement has been updated. It now states that chocolates can be given in groups of 1, 3, or 5.
The answers are still for 1,2,5
you dont need 6 steps in reduction method.
in reduction method reduce all 5 to 2
so it will take 5 steps
and in increment method as @zabed_akbar said only 5 steps required
2 (5) 5 5 5 5
5 5 (8) 8 8 8
8 8 8 (11) 11 11
11 11 11 11 (14) 14
14 14 14 14 14 (17)
17 17 17 17 17 17
you can't add 3 in your 1st step .....as the problem stated she can give wither 5 or 2 or 1 at once to all but chosen one
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.
Finaly the problem becomes: "reducing the difference between the number of colleague chocolates".
But if we start immediately to answer this new problem we will have an issue: how to deal with this example : "4 4 3"? In this case it is better to not start the reducing part because the initial state is not optimal. Let's transform it to "4 5 4" and then "5 5 5" and removing -5 chocolates is quicker than removing -2 chocolates with the initial state ("4 4 3"). Five operations < six operations!
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).
baseline is not necessarily 0. It is a number between the minimum in the sequence M and the max(0, (M - 4)).
Can you please elaborate why? I can't seem to formalize this
The cost to equalize the colleagues is the sum of the reduce operations through all colleagues. Naturally you use as the baseline the minimum colleague and you are taking away from other colleagues until they are equal. However, given you can reduce by 1, 2, or 5, you naturally want to take bigger steps and use as many 5 reductions as possibly and then 2 and only after that reduce by 1.
Now imagine reducing the case 3 7 7. If you would be strictly equalizing them with the miminum colleague then you need to reduce them all to 3 in which case you cannot apply -5 because 7-5=2 is too low hence you need to apply -2 twice. In this case it is cheaper to adjust the minimum to 2. I.e. 377->327->322->222 is cheaper then 377->357->337->335->333.
Now thinking about it again, it is not necessary to calculate for 5 different baselines, 3 is enough: the minimum in the sequence M, M - 1, M - 2 (given M > 2).
In other words reducing by 1 or 2 is cheap (1 operation), by 3 or 4 is expensive (2 operations), 5 is cheap again. By cheaply reducing the basiline by 1 or 2 with a single operation reduction you can save multiple 2 operation reductions on other colleagues.
Thank you so much for the wonderful explaination
Very nice. This is one of those problems that once I see it explained well, it makes total sense. But coming to that solution on my own would be the tricky part. I suppose practice makes perfect... I am kind of just getting started with these kinds of problems.
I still don't get it. Can someone explain to me how would baran_jana's algorithm work for the problem test case?
(it should return '2').
2237->2227->2222 ( for base line M=2 )
Can you explain for this case
First find min {1 5 5}. In this case it's 1.
In general, you need to try the following targets: min, min-1, min-2, min-3 and min-4 and target >=0.
So in this particular case min=1 so we try only min and min-1.
Case 1: target is (1 1 1)
Find the delta between (1 5 5) and (1 1 1):
delta = (1 5 5) - (1 1 1) = (0 4 4)
In terms of {1, 2, 5} operations we can minimally partition (0 4 4) elements as follows:
0 = 0 * 5 + 0 * 2 + 0 * 1
4 = 0 * 5 + 2 * 2 + 0 * 1
4 = 0 * 5 + 2 * 2 + 0 * 1
Note that you get above partition as follows:
For some delta = (d0 d1 ... dn-1)
di = ai * 5 + bi * 2 + ci * 1
ai = di / 5
bi = (di % 5) / 2
ci = (((di % 5) % 2) / 1)
Now count the occurences of {1, 2, 5} in (0 4 4) partition and this is the min number of operations to reduce (1 5 5) -> (1 1 1):
min number of ops = (0 + 0 + 0) + (0 + 2 + 0) + (0 + 2 + 0) = 4
Case 2: target is (0 0 0)
Find the delta between (1 5 5) and (0 0 0):
delta = (1 5 5) - (0 0 0) = (1 5 5)
In terms of {1, 2, 5} operations we can minimally partition (1 5 5) elements as follows:
1 = 0 * 5 + 0 * 2 + 1 * 1
5 = 1 * 5 + 0 * 2 + 0 * 1
5 = 1 * 5 + 0 * 2 + 0 * 1
Now count the occurences of {1, 2, 5} in (1 5 5) partition and this is the min number of operations to reduce (1 5 5) -> (0 0 0):
min number of ops = (0 + 0 + 1) + (1 + 0 + 0) + (1 + 0 + 0) = 3
Case 1 requires 4 steps and case 2 requires 3 steps, so case 2 is optimal and min number of steps is 3.
Why do we not look min-5, min-6 etc? Suppose min-5 >=0 so (min-5 min-5 ... min-5) is a valid (non-negative elements) target.
delta' = (v0 - (min -5) ... vn-1 - (min -5)) = (v0 - min + 5 ... vn-1 - min + 5)
When we did (min ... min) target, delta was:
delta = (v0 - min ... vn-1 - min)
Now if you compare partitions of delta and delta' into {1, 2, 5} it's evident that delta' has one more 5 in each element di' so compared to number of ops in delta it requires n extra -5 operations. For that reason each of the cases min-5, min-6 etc are always less optimal than cases min, min-1, ... min-4.
Can you do it in case of
1
3
1 123 834
I dont find a generic algorithm with proof of correctness but everyone is trying to explain seme solution with a trivial example. Please correct me if I am wrong.
I'm not clear if you want the solution of the case: 3 coworkers with the following allocation of chocolates:
( 1 3 1123834 )
OR
the case 5 coworkes with the allocation (1 3 1 123 834).
Assume it's the first case. If it's the second just follow below steps closely.
First we find min { 1, 3, 1123834 } = 1. We have two cases and we need to try both and check which has less steps.
Case 1: target = (1 1 1)
delta = (1 3 1123834) - (1 1 1) = (0 2 1123833)
We next find min number of -5, -2 and -1 steps to get from (1 3 1123834) to (1 1 1)
0 = 0 * 5 + 0 * 2 + 0 * 1
2 = 0 * 5 + 1 * 2 + 0 * 1
1123833 = 224766 * 5 + 1 * 2 + 1 * 1
Total # of steps: (# of steps to make 0 -> 1) + (# of steps to make 2 -> 1) + (# of steps to make 1123833 -> 1) = (0 + 0 + 0) + (0 + 1 + 0) + (224766 + 1 + 1) = 224769
Case 2: target = (0 0 0)
delta = (1 3 1123834) - (0 0 0) = (1 3 1123834)
We next find min number of -5, -2 and -1 steps to get from (1 3 1123834) to (0 0 0)
1 = 0 * 5 + 0 * 2 + 1 * 1
3 = 0 * 5 + 1 * 2 + 1 * 1
1123834 = 224766 * 5 + 2 * 2 + 0 * 1
Total # of steps: (# of steps to make 1 -> 0) + (# of steps to make 3 -> 0) + (# of steps to make 1123834 -> 0) = (0 + 0 + 1) + (0 + 1 + 1) + (224766 + 2 + 0) = 224771
We see that case 1 requires fewer steps so min number of steps is 224769.
Thanku very much....ur explanation is very helpful to solve this problem efficiently..:)
could you explain for 1 123 834 please
if u consider the case of 1 4 1123834. You need to consider (-1,-1,-1) as well to get the ans.
case 1:(1,4,1123834)->(1,1,1)=(0,3,1123833) steps (0,2,224768), Total = 224770
case 2:(1,4,1123834)->(0,0,0)=(1,4,1123834) steps (1,2,224768) Total = 224771
case 2:(1,4,1123834)->(-1,-1,-1)=(2,5,1123835) steps (1,1,224767) Total = 224769
ans = min(224770,224771,224769) = 224769.
thanks. it is like i got it with baran_jana but i finally got it 100% with your example... i guess i needed a practical explanation :)
your solution is great, but I don't get the di=ai*5+bi*2+ci*1 part. what does a,b,c's denote here. what if the problem has more than 3 collegaues.
a is the number of decution by 5 steps, b is the number of deduction by 2 steps, c is the number of deduction by 1 steps
They are nothing to do with the number of colleagues.
You have 3 ways either deduct 5 or 2 or 1.
got it , thanks a lot. :)
thank you so much
@dragan_ostojic Why should the baseline be >= 0 ? Why cant we make it -1,-2 ( upto minimum - 4 ) and try to make all the numbers reach -1 or -2?
@hariharan90000 Had the same doubt seeing the above comments but no one mentioned why and i couldn't find any logic to that arguement.
It can be
There is nothing wrong with our M-x becoming -ive cause in the original question we are adding values to nos. so they can never be negative.It is just to make our compress our question we are subtracting and getting -ive values and so it won't affect the original problem.
Consider the eg:
1 4 4
M=1 if x = 0 M-x = 1 ans = 4
if x = 1 M-x = 0 ans = 4
if x = 2 M-x = -1 ans = 3 ( 1 4 4 1 6 6 6 6 11 11 11 11)
that's lesser than wat we would get for M-x>=0
Plz Correct me if i'm wrong.
I had the same doubt and I think you're right. Considering the 1 4 4 example it should be necessary to take into account a -ve baseline as originally the question was of addition.
I can confirm that you are correct. for my case if m is min of given list of chocolates, then we gotta check m,m-1,m-2 to find the correct answer.
For some cases, my algorithm only worked when I checked targets<0. But maybe it's just my shoddy coding...
can you share me the proof of correctness of your algorithm in mathematical form
I like this explanation. After struggling with this problem for ages, implementing this method (almost) worked. But for input 15 only, my code still got WA about half the time when minimum%5==0, whether minimum==0 or some higher value. Can't work out why... So I ended up considering target=(min...min-4) for all inputs, which is slower but worked. I am not sure about the reasoning why target must always be >= 0.
hello, I am also getting WA for test case 15. But even after taking target till (min-4) I am not getting it right. Can U suggest something to debug.
For me, it was because I skip if baseLine is negative:
It helped.Thanks
@dragan_ostojic you must really be a genius
Your explaination was really helpful in solving this question with just one minor change. I didn't imposed any condition on target and let that loop run from min to min-3 as it would satisfy the case 1 4 4 suggested by someone here by setting target at -1. thank you.
Thanks, I was stuck in this problem your explanation really helped.
@dragan_ostojic, thank you for this explanation, it's clear and easy to follow.
One question: You can use the same argument used to eliminate (min-5) as a viable target to also eliminate (min-3) and (min-4). Stated differently:
Let (min-3) >= 0 such that [min-3 min-3 ... min-3] is a valid non-negative target.
delta'' = [v0 - (min-3) ... vn-1 - (min-3)] = [v0 - min + 3 ... vn-1 - min + 3]
Compared to our original target of [min ... min], and
delta = [v0-min ... vn-1 - min],
it's clear that delta'' results in 2n more operations than delta. Therefore, we should not need to consider (min-3).
Similarly, we shouldn't need to consider (min-4), because
delta''' = [v0 - min + 4 ... vn-1 - min + 4] results in 2n more operations than
delta = [v0-min ... vn-1 - min].
So my question: Isn't it sufficient to check ONLY for (min), (min-1) and (min-2)?
@dragan_ostojic thank you for the explanation. Its amazingly clear and efficient. I just want to add that target >= 0 does not work for all cases. When the condition allows target to be -ve or +ve it works for all test cases
That was amazing explanation.
I am having problem with test case#11. @baran_jana can you explain it for 1 5 5
Take a look into explanation I provided above: https://www.hackerrank.com/challenges/equal/forum/comments/227783
@baran_jana, In the above example, 377 is reduced to 333 using 2 operations, that is, 377 -> 355 and 355 -> 333. But I didn't follow how it is reduced to 222. In one operation if you are using 5 to reduce, then 377 -> 322. But how did 322 become 222? Can you please explain a bit?
To reduce to 222 is to decompose (377) - (222) = (155)
1 = 0*5 + 0*2 + 1*1
5 = 1*5 + 0*2 + 0*1
5 = 1*5 + 0*2 + 0*1
We see that reduction consist of one -1 followed by 2 -5:
377->277->227->222
Total of 3 operations
To be clear you can reduce by ONE operation at a time.
@dragan_ostojic, thanks for your response. when we reduce 377 by 1, we need to choose one of the interns, and reduce every other by 1. This means, 377 should become 267 or 366. how did it become 277?
no, it's not how it works. if you reduce, you choose only ONE at a time. if you increase you choose all EXCEPT the one you chose when you reduce. these two problems are equivalent i.e. if you solve reduction problem you also solved addition problem. note that the problem as originally stated is addition. the reason we choose reduction approach is because it's simpler. let me demonstrate first reduction solution and then how you derive addition solution from it.
Reduction:
3 7 7->2 7 7->2 2 7->2 2 2
steps:
dec 1st by 1
dec 2nd by 5
dec 3rd by 5
Addition:
3 7 7->3 8 8->8 8 13->13 13 13
steps:
inc all BUT 1st by 1
inc all BUT 2nd by 5
inc all BUT 3rd by 5
This is how Christy the intern is required to solve it. But she will first pretend that she was asked to solve it by taking away one at a time. Once she did that she would know how to solve by adding chocolates.
Look at my response to an earlier question, I explained in detail how you exactly find the solution for any reduction problem. Once you know the steps for reduction problem you can easily derive the steps for the equivalent addition problem as required.
@dragan_ostojic okay. can you also post the link to your response to the other question?
https://www.hackerrank.com/challenges/equal/forum/comments/227783
Oh, its for the same problem. Thanks for sharing it. I'll go through it and get back to you in case I've any followup questions. Thanks!
awesome explanation, thanks !
Thank you for such a clear explaination. I was so close to this. I was thinking about M, M - 1, M - 2, M - 5.
what is the output for the test case
my answer is 4 but correct output showing is 3 can someone explain me the reason for this test case?
The optimal solution for 1 5 5 is as follows: 1- 1+5,5,5+5 -- 6,5,10 2- 6+5,5+5,10 -- 11,10,10 3- 11,10+1,10+1 -- 11,11,11
So that could be done in 3 steps.
This is the explanation i was looking for this test case. Thanks!
Hey, Baran Jana! I am getting some segmentation fault while using your logic. I am only checking for M,M-1 and M-2. Is there something else where I might be going wrong?
That was the theory what would be the algo
can u give answer for : 1 4 1 5 5 5
I under stand your approch. It is greedy. But Why this question is marked as DP? Thing thing is really creating confusion.
By using your condition of max(0,(M-4)) last test case fails. I think we must run code fore M to M-4 irrespective of whether it is >=0.
Yeah you said that right! Got ac with that! I wrote that >=0 condition and got wa in #13th case, But why this is happening? How can chocolates balance in negative lol!
I think answer is possible because real operations is giving choclates and making them equal and not make equal by removing. So we must just be concered with making them equal as we are removing choclates and making equal, answer will be correct even if we make it negative.
Yeah you are right!
So true it hurts
Passed all tests:
Thanks for the solution :) :) I like the use of the freq table. Are able to offer an explanation of the last few lines?
It appears you getting the min of the operatins for the cases of min, min-1 and min-2. Why not min-3 and min -4?
Thanks in advance :).
They are redundant cause they will never be smaller than the case of min.
I actually saw an explanation under another comment explaining this. It has something to do with; when to reduce 3/4 to zero it can be cheaper to do it via -5 (-1|-2) and reducing the and then others by 2|1.
Reducing 6 9 9 Option 1 (4 moves) -2@1 6 7 9 -2@2 6 7 7
-1@1 6 6 7 -1@2 6 6 6
Option 2 (3 moves) 6 9 9 -5@1 6 4 9 -5@2 6 4 4 -2@0 4 4 4
Reducing by 5 first is faster :).
4 4 3; 7 4 6; 7 7 9; 8 8 9; 9 9 9
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
Make [][] diff of size [n] [4] rather than [n][n].
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"?
@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?
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:
its memoization
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
Please let me know if I am doing something worng/incorrect.
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.
Hi Zhassan, can you please look into my code and say where i am doing wrong (apart from time complexity),
t1 = 1 t3 = 3 t5 = 5 for _ in range(int(input().strip())): l = int(input().strip()) c = [int(f) for f in input().strip().split(' ')] e = 0 count = 0 while(max(c)!=min(c)): count += 1 mi = min(c) mx = max(c) d = mx-mi if d >= t1 and d < t3: e = t1 elif d >= t3 and d < t5: e = t3 elif d >= t5: e = t5 for i in range(len(c)): if c[i] != mx: c[i]+=e print(count) #print(c)
my answer - 933 expected - 10605 but still all are having same numbers of chocolates.
Hi! I think possible steps are {1,2,5} not {1,3,5} as you stated in the code. Please try one more time with that correction.
oh my bad, but still, no luck, but perhaps i found it, some wrong assumptions. thanks bro
regarding f(c-min+i), why i?
rather it can be written as f(c-(min-i)), now it might be clear to you why
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 .
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
Thank you i got it..
1 (5) 5 ->adding 5
6 5 (10) ->adding 5
(11) 10 10 ->adding 1
11 11 11
The answer is 3 only.
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)?
Sorry , but I am unable to understand. Why 4 ? Elaborate , please.
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??
Miss print, it should be 1, 2 and 5
@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;
}
int main() { int testcases ; cin >> testcases ;
}
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".
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?