Day 15 | Binary Search [Cont.] | C++

A Note before we start -

When I see problems that contain words like minimum, maximum, minimize, and maximize, I try to solve them with the following tricks in the given order [It is not 100% of the time, but 90% of the time, it works like a charm]

1. Binary Search - It is the first thing I try to apply to a problem with words given above

2. Dynamic Programming - According to my experience it is the second thing I use

3. Greedy Approach

4. Mathematics

I am basically like this but for all min/max problems (not limited to div 3)

Yesterday, we discussed binary search and I gave some questions for you to try. Let's solve them today.

Vanya and Lanterns | C++ Implementation

This question can be easily (and in a better way) done without the binary search. But we will solve it using binary search.

Step 1 - We need a variable on which we can apply binary search

For that d is a very good candidate.

Reason if we can cover the whole road with light radius d then we know that it will also be possible with d+1, d+2, and so on

And if it's not possible with d, then it won't be possible with any value lesser as well.

Step 2 - How to check if we can light up the whole street with radius d

For this, it should follow 3 conditions

1. Light up the area between 0 and lamp 1 that is d >= a[0]

2. Light up the area between l and the last lamp that is d >= a.back()

3. Light up the area between any two adjacent lamps that is for any i, a[i] - d <= a[i-1] + d (both light overlap)

So we can run a binary search on radius and then as per step 1 if it is possible then we further search in space [start, mid], else we try to find in space [mid, end]

Note: We are not using mid-1 or mid+1, because we are going into accuracy.

We can code it like this

long double lo = max(a[0], l - a.back()), hi = l, ans = hi, error = 1e-10;
    while(hi-lo > error){
        long double mid = (lo + hi) / 2;
        int prev = 0;
        bool possible = true;
        for(int i = 0; i < a.size(); i++){
            if(a[i] - mid > prev + mid){
                possible = false;
                break;
            }
            prev = a[i];
        }
        if(possible){
            ans = mid;
            hi = mid;
        }else{
            lo = mid;
        }
    }

Hamburgers | C++ Implementation

Like the previous problem, here as well we need to do two steps

Step 1 - Figure out what we will run binary search on.

Here we can run a search on the number of burgers.

Reason - If we can make X burgers, then we can make X-1, X-2,...0 burgers as well.

Similarly, if we cannot make X burgers we cannot make X+1, X+2,... burgers as well

Step 2 - How to figure out if we can make X burgers

Actually, this step is relatively easier, we just calculate the cost and check if it in our budget.

Books | C++ Implemenation

We will be breaking the problem into 2 steps here as well.

Step 1 - Figure out what we will run binary search on.

Here we can run a search on the number of books we can read.

Reason - If we can read X books, then we can read X-1, X-2,...0 books as well.

Similarly, if we cannot make X books we cannot read X+1, X+2,... books as well

Step 2 - How to figure out if we can read X books

To do this efficiently we will be using a technique called sliding window.

Let's say we want to check if there are any continuous X books that we can read in T seconds or not.

Let's first store the sum of the first window of X elements which is the sum from A[0] to A[X-1].

Now we keep sliding this window from left to right like

1. Subtract A[0] from the sum and add A[X]

2. Subtract A[1] from the sum and then add A[X+1]

and so on.

If you notice, we are sliding a window of elements, hence the name sliding window.

K-th Not Divisible by n | C++ Implementation

This problem is pretty much like the problem we discussed yesterday. Find SQRT(X).

Dividing it into two parts again

Step 1 - Figure out what we will run the binary search on.

Here we can run a search on natural numbers themselves.

Reason - If up to X there are less than K numbers that are not divisible by n, then the answer must be greater than X, else it should be less than X.

Step 2 - How to figure out if we can read X books

As discussed, we just need to check the number of not divisible numbers up to X.

There will be some edge cases like what if X is itself divisible by n

NOTE - I used unsigned int because I was worried about integer overflow.