that’s an honor , thank you

sqrt(k) upper bound why?

since we want smallest x such that Ax^2 + Bx + C >= K

let f(x) = Ax^2 + Bx + C

so if you put x = sqrt(K) , you can prove f(sqrt(K)) >= K (even if you consider Ax^2 term , it will be A * sqrt(K) * sqrt(K) , which is greater than K).

so we are sure upto sqrt(K) , we can find an x , such that f(x) >= K , so that’s why we don’t need to go beyond ceil(sqrt(K))

thank you I understood.Similarly i was able to solve that problem on cubic polynomials

and there i took cube root of k and got AC .I really loved your video and now i am able to implement binary search very well and i also solved a div 2 C problem using it.

Problem - B - Codeforces . If possible can u please explain how to solve this using binary search because in the tags it was mentioned binary search.I tried my best and wrote this code based on binary search but got TLE this is my code pastebin

**Monk’s Encounter with polynomial**

```
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
ll fx(int A,int B,int C, int X)
{
return (A*X*X + B*X + C);
}
ll BSearch(int A,int B,int C,ll K)
{
if(C >= K)
{
return 0;
}
int L = 1;
int H = ceil(sqrt(K));
while(L <= H)
{
int mid = L + (H-L)/2;
ll x = fx(A,B,C,mid);
ll y = fx(A,B,C,mid-1);
if( x>= K && y<K)
{
return mid;
}
else if( x < K)
L = mid + 1;
else
H = mid - 1;
}
}
int main()
{
int T,A,B,C;
ll K;
cin>>T;
for(int i=0;i<T;i++)
{
cin>>A>>B>>C>>K;
cout<<BSearch(A,B,C,K)<<endl;
}
return 0;
}
```

This solution isn’t passing all the Test cases. I can’t seem to figure out what’s wrong.

I just realised that there might be overflow where I’m calculating the value of the quadratic expression.

so you solved it now?

(apologies for late reply)

nice 1

thanks

Hey! For the Monk’s encounter question, I basically have the same code as yours but mine is failing for some inputs(Input#8-Input#13). Can u pls help.

My code:

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

ll a,b,c,k;

ll eqn(ll n){

return a*n*n + b*n + c;

}

int main(){

ll t;

cin >> t;

while(t–){

// ll a,b,c,k;

cin >> a >> b >> c >> k;

ll L = 1;

ll H = k;

ll x = -1;

if(c >= k){

x = 0;

}

else{

while(L<=H){

ll mid = (L+H)/2;

if(eqn(mid) >= k && eqn(mid-1) < k){

x = mid;

break;

}

else if(eqn(mid) < k){

L = mid+1;

}

else

H = mid-1;

}

}

cout << x << ‘\n’;

}

}

I have set H = sqrt(K) not equal to K.

K can be as large as 10^10 , so if you set H = k this will result in integer overflow when you will evaluate f(x)

@waqar_ahmad224 Could you please upload a video on this question of spoj as well as I am unable to solve it and I found it very interesting as well

seems like a variation of LIS.

I will try it.

please make video on greedy algorithm.Please!!