# Double Burgers Editorial - May-CookOff 2021 , BURGER

Problem Link : BURGER

Approach : Do what exactly problem want -

1. If Y is not divisible by X then answer is -1 .why (think about this)
2. Now for other cases -
we have to subtract the sum of all X * (2i) until my (Y > (2i) ) [for all i>=0 ] now increase the count of βiβ into map .

we have two situation left either my Y is zero , or Y is something remaining.

if Y is zero then we have to print answer.

for other case do the same as above ie., we have to subtract the sum of all X * (2i) until my (Y > (2i) ) [for all i>=0 ] now increase the count of βiβ into map .

but note that if we rest then we have to increase the answer by 1 , as in question it is mentioned that " Chef also allows you take a break from eating for exactly 1 minute."

Now for printing the answer we have to check whether in our map the frequency of each element (basically that βiβ which is stored ) is one or not . if it is more than one that means we have 2 same time of eating streaks and in question it is clearly mentioned that chef requires all unique time streaks
[You can check this by using set too]

Letβs take sample test case-

X = 1 , Y = 7

Now -

1st minute = X ie, 1 => X * 20 = 1 * 2 0 = 1
2nd minute = 2X ie, 2 => X * 21 = 1 * 2 1 = 2
3rd minute = 4X ie, 4 => X * 22 = 1 * 2 2 = 4

in one go how many minutes we take 3 right ?

now while printing check 3 occurs only once β¦yeah it occur only once .
1 + 2 + 4 = 7 , required minutes is 3.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

X = 1 , Y = 4

Now -

1st minute = X ie, 1 => X * 20 = 1 * 2 0 = 1
2nd minute = 2X ie, 2 => X * 21 = 1 * 2 1 = 2

2 minutes streak ,

β>> now wait for 1 min because if we subtract 4 (which is from 3 minute then Y will be -ve) [ do not store this into map]

start again

1st minute = X ie, 1 => X * 20 = 1 * 2 0 = 1

1 min streak .

map > [ 2 β 1 times , 1 β 1 times ] ,all are occur once print answer -

1 + 2 + 1 = 4 , required minutes is 3 + 1 [that rest minute]

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Now take an example in which Y is divisible by X but still answer is -1

X = 2 , Y = 12

Now -

1st minute = X ie, 1 => X * 20 = 2 * 2 0 = 2
2nd minute = 2X ie, 2 => X * 21 = 2 * 2 1 = 4

2 minutes streak ,

β>> now wait for 1 min because if we subtract (2*4) (which is from 3 minute then Y will be -ve) [ do not store this into map]

start again

1st minute = X ie, 1 => X * 20 = 2 * 2 0 = 2
2nd minute = 2X ie, 2 => X * 21 = 2 * 2 1 = 4

2 minutes streak .

map > [ 2 β 2 times ] , ohhhoo , 2 minutes streak occur 2 times β¦ shit chef need unique streaks

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

My solution : βCodeChef: Practical coding for everyoneβ

2 Likes

You can help me for Chef and subarrays problem?
my solution https://www.codechef.com/viewsolution/46828687

https://www.codechef.com/viewsolution/46818504
Where am I wromg?

1
2 12

Hey @ssrivastava990 β¦ can you help me identify the mistake in my code ?
https://www.codechef.com/viewsolution/46831133

I used the same logic that we take the closest possible burgers we can eat less than y, and subtract it from y and repeat. Idk which TC is this wrong for

Thanks I got it. I did not see that all the pairs will be different

1 Like

If you check my solution , I have made sure that 1 streak will be used only once. for X=2,Y=12 im getting -1.

Looks nice, my approach was a bit different. Assuming that answer is k and streaks are of length a_1, a_2,..,a_k, we eat: \sum\limits_{i=1}^{k} X \times (2^{a_i} - 1) burgers in a time of (k - 1 + \sum\limits_{i=1}^{k} a_i).
So we must have \sum\limits_{i=1}^{k} X \times (2^{a_i} - 1) = Y. Therefore Y\%X == 0. Next \sum\limits_{i=1}^{k} 2^{a_i} = k + Y/X. Therefore the condition is that number of set bits in (Y/X + k) should be exactly k. Also k \leq 61. So iterate on k and we can find the time and values of a_i.

1 Like

How to prove this solution ? So you are saying we should subtract as much as possible ?

Yup correct .

1 Like

Ok so greedy solution here. But i still cannot figure out why this way will be optimal . Could you help here ?

I converted it into a minimizing coin problem (With the condition that you can use one coin only once) and solved it

One way we can prove is that we will repeat the length of streaks if we donβt take the biggest one. Hmm understood. Thanks

1 Like

U got it :+1

1 Like

hey can you help me tell what is wrong in my approach
https://www.codechef.com/viewsolution/46828687

Nope u did completely wrong , check editorial .

where i can find it? i am new here

βCSUBS - Editorialβ

@ssrivastava990 Why my code gives Wa I have precomputed all possible sums for burgers then I have check if we could break into two parts then took minimum. CodeChef: Practical coding for everyone