I realize so quickly, that I always expect a BS on answer problem.

I'm bad at binary search problems but what I've realized recently is that if the problem requires a bunch of different possibilities to be checked and there isn't any greedy stuff, its either going to be dynamic programming or binary search. Usually dynamic programming problems have lower constraints and binary search problems will have higher ones.

if it is maximixation or minimization, then just try once is it possible by bs on answer ?

if you need to use bs on answer on some problems, it usually have a monotic property, so if you figure out what is that, let's call it f(x)=true or false, since this function is monotic, then there will be a point where f(x)=true turn into false (this depends on problem), for example:

f(1)=true f(2)=true f(3)=true f(4)=false f(5)=false

and i think the hardest part in this type of problems is that figure out what exactly f(x) is, after that it will become more easily and you just need to binary search on that function.

I'll try to help you visualize it:

https://mirror.codeforces.com/problemset/problem/1873/E

For this question and most other questions from my experience, we are trying to snipe down a specific answer. We know that as the answer increases, so does the amount of water we use, and vice versa. This is a crucial trend among binary search problems. If x and the answer fluctuated without correlation, then we cannot use binary search.

So in order to get the answer, we have to make smart guesses to try and get as close to the target (x) as possible. That is when we can use BS as it is the most efficient method of searching for a specific value within a sorted data set. It cuts down half of the answers at every step, yielding a time complexity of log2(n). We will guess the midpoint of all the possible values each time, and check if that number we've chosen is greater than or less than the target. Eventually with each check, we will get closer and closer to the answer.

It's fine if you still can't grasp it after reading this. I'd suggest you should practice a lot of BS problems and eventually it will become more intuitive. Practice makes perfect after all.

Whenever you need to find the max/min valid value, check if:

• When $$$x$$$ is valid $$$\implies$$$ any $$$y$$$ is valid, where $$$y \gt x$$$ (if you want to minimise the value) or $$$y \lt x$$$ (if you want to maximise it), and
• It's easy to efficiently check if $$$x$$$ is valid

If these are true, then you can BS the answer

In this problem, we must find the largest possible value of $$$h$$$ — this is the first hint that we can BS the answer, so we check:

• If $$$h_1$$$ is a valid value of $$$h$$$, then $$$h_2 \lt h_1$$$ is also valid, since a lower tank will need at most as much water as a higher one, so if there's enough water for a tank of height $$$h_1$$$, there's also enough for a tank of size $$$h_2$$$
• It's easy to check if there's enough water for a tank of height $$$h_1$$$ by simply checking the amount of water in each column. The water in column $$$i$$$ will be equal to $$$w_i = \max(0,h_1 - a_i)$$$. If the sum of these is at most $$$x$$$, then $$$h_1$$$ is valid, otherwise it's not. Note that the complexity of this is $$$O(n)$$$, which is efficient enough (The full complexity is $$$(O(n\log n))$$$)

So, we can use BS for this problem.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MID (l+r)/2
const ll INF=1e10;
int main(){
    ll tc;
    cin>>tc;
    
    while(tc--){
        ll n, x;
        cin>>n>>x;
        ll a[n];
        for(ll i=0; i<n; i++){
            cin>>a[i];
        }
        
        ll l=1, r=INF;
        while(l<r){
            // Calculate the amount of water needed
            ll y=0;
            for(ll i=0; i<n; i++){
                if(a[i]<MID) y+=MID-a[i];
            }
            
            // If it's not too much, the answer is at least MID
            if(y<=x) l=MID;
            else r=MID-1;  // Otherwise, it’s less than MID
        }
        cout<<MID<<endl;
    }
}

When you can divide the problem into a subproblem where you are given the answer, you have to check whether the answer can be a valid answer or not.

And, you need to check whether the answers make a graph such that for the first x candidate answers, if the answer is No, the next every candidate answer must be Yes and vice versa.

Lastly, you need to practice too much binary search on answer problems to use it to its fullest.

You can see if answer needs "both min and max". Giving an example, problems such as "maximize f(a) while minimizing g(a)". f(A) and g(A) means calculating A in some ways. I didn't said you could use binary search in all these case, but if you saw it, you could have a try. It's really uesful.

I apply binary search when i notice a pattern of TT..TF..FF or F..FTT..T .

It's actually really simple. A problem needs binary search on answer iff:

1. It's a minimization / maximization problem.

2. There is no easy way to find the solution directly, but checking if a given value provides a valid solution is easy.

3. There is a boundary, such that every point before that boundary provides a valid solution and every point after provides an invalid solution (or vise versa).

Example taken from CP4 book 1 page 150: "The abridged version of UVa 11935 — Through the Desert is as follows: Imagine that you are an explorer trying to cross a desert. You use a jeep with a ‘large enough’ fuel tank – initially full. You encounter a series of events throughout your journey such as ‘drive (that consumes fuel)’, ‘experience gas leak (further reduces the amount of fuel left)’, ‘encounter gas station (allowing you to refuel to the original capacity of your jeep’s fuel tank)’, ‘encounter mechanic (fixes all leaks)’, or ‘reach goal (done)’. You need to determine the smallest possible fuel tank capacity for your jeep to be able to reach the goal. The answer must be precise to three digits after decimal point."

Notice this problem has all three properties described above:

1. It's a minimization problem.

2. There is no easy way to solve the problem directly, because changing the capacity alters some events in non-trivial ways. That said, if I give you a value and ask "can you finish the trip with this capacity?" you simply have to simulate the trip (can be a bit tedious, but it's not hard, just have to implement it).

3. If it's possible to finish the trip with capacity X then it's possible for all values ≥ X. Similarly, if it's not possible for a value Y, then it's not possible for all values ≤ Y. So there is a decision boundary Z at some point where it's not possible for all Y < Z and it's possible for all X > Z.

it usually askes the max/min of a value

many problems have a "find the maximum value of all minimum answers from different possibilities" kind of sentence, and that is 100% BS

when the question asks to minimize a maximum or maximize a minimum, it is usually a binary search problem

If you find the words like make the Minimize the maximum, or maximize the minimum.

You will think you need to use the binary answer and check.This is some of my ideas.

And the best way to do is to exersize much and then you will find some similarities between problems.

Good luck!

First you have to know some classic usages such as maximize the minimum value...

But its principle is the most important:find the value you should binary search.The value usually have one thing in common:they all have monotonicity.