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.

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.

## Equal

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

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 >= 0does not work for all cases. When the condition allowstargetto be-veor+veit works for all test casesThat 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