that’s an honor , thank you
3 Likes
sqrt(k) upper bound why?
1 Like
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))
3 Likes
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)
1 Like
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 ann + 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)
1 Like
@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!!