PCJ18D - Editorial

PROBLEM LINK:

Practice
Contest

Author: Madhav Sainanee
Tester: Prakhar Gupta
Editorialist: Prakhar Gupta

DIFFICULTY:

EASY

PREREQUISITES:

Binary Search

PROBLEM:

Find out the minimum number of cookies to bake initially to eat at least N cookies, provided you can make 1 cookie from the crumbs of B cookies.

QUICK EXPLANATION

We binary search on the number of cookies to bake initially.

EXPLANATION:

I advise you to read about binary search from this article once.

To find the total number of cookies we eat if we have K cookies in the beginning, we use the following algorithm:

  1. Initialise eaten = 0, crumbs = 0.

  2. Eat all the cookies, i.e. eaten += K, crumbs += K.

  3. Make new cookies from the crumbs, i.e. K = crumbs / B, crumbs = crumbs % B .

  4. Repeat from step 2 if K > 0.

     int eaten = 0;
     int crumbs = 0;
    
     while(k > 0)
     {
         eaten += k;
         crumbs += k;
    
         k = crumbs / b;
         crumbs %= b;
     } 
     return eaten;
    

We start the binary search from lo = 1 and hi = N.

  1. Find mid = \lfloor\frac{lo + hi} {2}\rfloor, and find total = cookies(mid).

  2. If total < N, then set lo = mid + 1. Else, set hi = mid.

  3. Repeat step 1 if lo < hi.

     int lo = 1;
     int hi = n;
    
     while(lo < hi)
     {
         int mid = (lo + hi) / 2;
         int total = cookies(mid, b);
    
         if(total < n)
             lo = mid + 1;
         else
             hi = mid;
     }
    

The answer will be hi.

Complexity: The time complexity is O(log(N) * log(B)) per test case.

ALTERNATE SOLUTION:

You have N-1 crumbs available to eat at least N cookies since you won’t be able to use the crumbs of the last cookie. You can make a maximum of \lfloor\frac{N-1}{B}\rfloor extra cookies from the crumbs. So in all, you have to bake at least N - \lfloor\frac{N-1}{B}\rfloor cookies in the beginning.

Complexity: The time complexity is O(1) per test case.

AUTHOR’S SOLUTIONS:

O(log(N) * log(B)) solution can be found here.
O(1) solution can be found here.

2 Likes

@madhav_1999 @prakhar17252 Can you guys pls post the editorial for PCJ18G ?? Help will be appreciated.

@na0013 The editorial for G has already been posted. Here is the link.

Thank You @prakhar17252 !!