Double Burgers Editorial - May-CookOff 2021 , BURGER

[ssrivastava990]

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 * (2ⁱ) until my (Y > (2ⁱ) ) [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 * (2ⁱ) until my (Y > (2ⁱ) ) [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 -

1^st minute = X ie, 1 => X * 2⁰ = 1 * 2 ⁰ = 1
2^nd minute = 2X ie, 2 => X * 2¹ = 1 * 2 ¹ = 2
3^rd minute = 4X ie, 4 => X * 2² = 1 * 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 -

1^st minute = X ie, 1 => X * 2⁰ = 1 * 2 ⁰ = 1
2^nd minute = 2X ie, 2 => X * 2¹ = 1 * 2 ¹ = 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

1^st minute = X ie, 1 => X * 2⁰ = 1 * 2 ⁰ = 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 -

1^st minute = X ie, 1 => X * 2⁰ = 2 * 2 ⁰ = 2
2^nd minute = 2X ie, 2 => X * 2¹ = 2 * 2 ¹ = 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

1^st minute = X ie, 1 => X * 2⁰ = 2 * 2 ⁰ = 2
2^nd minute = 2X ie, 2 => X * 2¹ = 2 * 2 ¹ = 4

2 minutes streak .

map > [ 2 → 2 times ] , ohhhoo , 2 minutes streak occur 2 times … shit chef need unique streaks

answer is -1

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

My solution : “CodeChef: Practical coding for everyone”

[darkmen]

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

[cp_guy]

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

[ssrivastava990]

1
2 12

[vruttant1403]

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

[cp_guy]

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

[ssrivastava990]

@ssrivastava990

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

X = 2 , Y = 12

Now -

1^st minute = X ie, 1 => X * 2⁰ = 2 * 1 ⁰ = 2
2^nd minute = 2X ie, 2 => X * 2¹ = 2 * 2 ⁰ = 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

1^st minute = X ie, 1 => X * 2⁰ = 2 * 1 ⁰ = 2
2^nd minute = 2X ie, 2 => X * 2¹ = 2 * 2 ⁰ = 4

2 minutes streak .

map > [ 2 → 2 times ] , ohhhoo , 2 minutes streak occur 2 times … shit chef need unique streaks

answer is -1

@cp_guy @vruttant1403

[vruttant1403]

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.

[samarth2017]

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.

[rananjay23]

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

[ssrivastava990]

Yup correct .

[rananjay23]

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

[turzo_sawroop]

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

[rananjay23]

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

[ssrivastava990]

U got it :+1

[darkmen]

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

[ssrivastava990]

Nope u did completely wrong , check editorial .

[darkmen]

where i can find it? i am new here

[ssrivastava990]

“CSUBS - Editorial”

[extremecoder12]

@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