# Basic Algorithms Course for Beginners : CodeNCode(1 Aug 2020 : New problem added)

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

10 June 2020 : 1 video added
L004 : Permutation & Cost of ith Cyclic Shift

1 Like

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?

1 Like

15 June 2020 : 1 new lecture added
L005 : Calculating Cost of ith Cyclic Shift

2 Likes

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.

12 July 2020 : new lecture added
E001 : Maximize Function (Medium) | HackerEarth

14 July 2020 : 1 video added
E003 : Rotation Matching | Codeforces

17 July 2020 : new video added
L006 : Range Update in O(1) time