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.

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

## Equal

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

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 casesHi , Can you please explain how did you come up with this formula ?

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)