Educational Codeforces Round 80

please help in explanation of the editorial
problem: 1288A Deadline
https://codeforces.com/blog/entry/73105

Read it thoroughly as to why we have to iterate till square root of d.
That is the important part

Found it in comments section of the editorial
useful tip would be skim through that as well,
a lot of people have similar doubts so you can even ask at times XD
and read up more

1 Like

Simple make a quadratic equation by the given inequality and since solutions are to be non negative, so make Discriminant <= 0 .

1 Like

There’s a way simpler solution…

Just iterate over x in range [1 to n] :stuck_out_tongue:

import math

t = int(input())

while(t>0):
    n,d = map(int,input().split())
    flag = 0
    for x in range(0,n+1):
        if x + math.ceil(d/(x+1)) <= n:
            flag=1
            break
        
    if flag == 1:
        print("YES")
    else:
        print("NO")
    t-=1
1 Like

i saw a lot of solutions like this being hacked :stuck_out_tongue:

AM >= GM (a+b>=2*sqrt(ab))

x + (d/x) >= 2*sqrt(d)

hence x=sqrt(d) for minimum value of the function.

Can be done in O(1)

int main() {
    int t;cin>>t;
    while(t--){
        int n,d;cin>>n>>d;
        double mn = sqrt(d)*2.0;
        if(mn<=n+1){
            cout<<"YES\n";
        }else cout<<"NO\n";
    }
}
2 Likes

Well guess what😉 it passed system tests

2 Likes