NFS - Editorial

[iceknight1093]

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Daanish Mahajan
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef is playing NFS, and driving his car straight at U m/s. He wants to ensure that the car’s velocity is at most V m/s after S metres; and the maximum deceleration he can achieve is A m/s^2. Can he do this?

QUICK EXPLANATION

Check if V^2 \geq U^2 - 2*A*S.

EXPLANATION:

First, note that deceleration by A m/s^2 is the same as acceleration by -A m/s^2.
What does it mean for Chef to not be able to reach his target velocity?
It means that, even if Chef decelerates as much as possible for all S metres, his velocity at the end will be strictly greater than V m/s - and the square of his velocity will be strictly greater than V^2.
Applying the equation given in the statement, this means that V^2 < U^2 - 2*A*S.
Thus, if V^2 < U^2 - 2*A*S the answer is NO, otherwise the answer is YES.

What about sqrt?

It is also possible to AC by checking for V < \sqrt{U^2 - 2*A*S}, but it is possible for U^2 - 2*A*S to be negative, so blindly taking the square root will likely give you a runtime error. You can instead check for V > \sqrt{max(0, U^2 - 2*A*S)}

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

SOLUTIONS:

Setter's Solution (C++)

#include<bits/stdc++.h>
 
using namespace std;
 
const int maxv = 1e4, minv = 1, maxt = 1e5;
 
int main()
{   
    int t; cin >> t;
    int u, v, a, s; 
    while(t--){
        cin >> u >> v >> a >> s;
        string ans = "no";
        if(u * u - 2 * a * s <= v * v)ans = "yes";
        cout << ans << endl;
    }
}

Tester's Solution (C++)

//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
 
int main(){
    fastio;
 
    int t; 
    cin>>t;
 
    while(t--){
        long long int u, v, a, s;
        cin>>u>>v>>a>>s;
 
        if(v * v >= u * u - 2 * a * s) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

Editorialist's Solution (Python)

t = int(input())
for _ in range(t):
    u, v, a, s = map(int, input().split())
    if u*u - 2*a*s <= v*v:
        print('Yes')
    else:
        print('No')

[akshay_012]

#include <algorithm> 
#include <vector>
#define ll long long int 
#define nl '\n'
#define fst ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std; 



int main()
{
ll t;
cin>>t;
while(t--)
{
    ll u,v,a,s;
    cin>>u>>v>>a>>s;
    
    double ans=0;    
ans=ceil(sqrt((u)^(u)-(2*a*s)));

int x=0;
x=(u)^u-(2*a*s);
if(x<0)
ans=0;

    //cout<<ans<<" "<<v<<endl;
    if(u<=v)
    cout<<"YES"<<nl;
    else
    {
    if(ans<=v)
    cout<<"YES"<<nl;
    else
    cout<<"NO"<<nl;

    }    
}

return 0 ;



}
why i am getting wa ans only becuz sqrt @iceknight1093

[akshay_012]

why doing sqrt will get wa ans @ceknight1093

[iceknight1093]

You want to calculate the square root of u^2 - 2*a*s, not the square root of u ^ u - 2*a*s.
Also, the ^ in your code is the xor operator - what you want to do is sqrt(u*u - 2*a*s).
Finally, u*u - 2*a*s might be negative, so take care of that before taking the square root.

[akshay_012]

my bad thk

[ninjacoder14]

Scanner scan = new Scanner(System.in);
int t=scan.nextInt();
while(t>0) {
int v=scan.nextInt();
int u=scan.nextInt();
int a=scan.nextInt();
int s=scan.nextInt();
if(v==u || Math.sqrt(((uu)-(2a*s)))<=v) {
System.out.println(“YES”);
}else {
System.out.println(“NO”);
}
t–;
}

I am getting TLE, pls see

[witcomenight]

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

int main() {
int t;
cin>>t;
while (t–)
{
int u,v,a,s;
cin>>u>>v>>a>>s;
float finalspeed = sqrt(pow(u,2)-2as);
// cout<<finalspeed<<endl;

    if(finalspeed<=v){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}
   
return 0;

}
This is my code why I was getting wrong answer while submitting.

[polmbil]

int main()
{
int t;
cin>>t;
while(t–)
{
float u,v,a,s;
float ans=-1;
cin>>u>>v>>a>>s;
if(u<=v)
{
cout<<“Yes”<<endl;
}
else
{
ans=sqrt((uu)-(2a*s));
if(ans<=v)
{
cout<<“Yes”<<endl;
}
else
{
cout<<“No”<<endl;
}
}
}
}

Why am I getting a WA I don’t understand

[kunal_srivast]

@ninjacoder14
Use BufferReader for taking input…
Scanner class is bit slow wrt. BufferReader class.

[abhicoder_03]

for i in range(int(input())):
u,v,a,s = list(map(int, input().split()))
vf = ((u ** 2) - 2 * a * s)
vf_pow = vf ** 0.5
if (vf < 0 and u == v == a == s == 1):
print(“Yes”)
elif (vf < 0):
print(“No”)
elif (vf_pow > 0 and v >= vf_pow):
print(“Yes”)
elif (vf > 0 and vf_pow > v):
print(“No”)
else:
print(“No”)

What’s wrong in this code?

[iceknight1093]

@abhicoder_03

Consider this case

1
1 100 20 20

Is the answer really ‘No’?

@witcomenight @polmbil
What happens if you take square root when u^2 - 2*a*s < 0? (This is discussed in the last part of the editorial, please read that)

@ninjacoder14
As kunal_srivast mentioned, Scanner is slow. Also, you have the same issue as above - think about when you can and cannot take square root.

[nike07]

#include <bits/stdc++.h>
#include<string.h>
using namespace std;
int main() {
	
	int t;
	cin>>t;
	while(t--)
	{
	    int u,v,A,s;
	    float v1;
	    cin>>u>>v>>A>>s;
	    if(v>=u){
	        cout<<"Yes"<<"\n";
	    }
	    else{
	        v1=sqrt(u*u-2*A*s);
	        if(v1<=(float)v){
	            cout<<"Yes"<<"\n";
	        }
	        else{
	            cout<<"No"<<"\n";
	        }
	    }
	}
	
	return 0;
}

my doubt is why is this wrong, i have checked all cases it should be correct. After competition when I tried this, it showed correct:-

#include <bits/stdc++.h>
#include<string.h>
using namespace std;
int main() {
	
	int t;
	cin>>t;
	while(t--)
	{
	    int u,v,A,s;
	    float v1;
	    cin>>u>>v>>A>>s;
	    if(v>=u){
	        cout<<"Yes"<<"\n";
	    }
	    else{
	        v1=sqrt(u*u-2*A*s);
	        if((int)v1<=v){
	            cout<<"Yes"<<"\n";
	        }
	        else{
	            cout<<"No"<<"\n";
	        }
	    }
	}
	
	return 0;
}

In the 2nd one, i type converted float to int and it gave correct answer, but in the first one type converted int to float, which should give more accurate result, and should be correct. Please tell me why is my 1st method wrong.

[smoothcodes]

@iceknight1093 Sorry to ask again for the same Q.
But can you tell me what went wrong here. I was just fixing the runtime error. The output worked for given cases I think the problem lies with type declaration but I don’t know .

long long t;
cin>>t;
int u,a,s;
long long x,v;
while(t--){
	cin>>u>>v>>a>>s;
	x= sqrt((u*u)+(2*a*s));
	if(v+1>x){
		cout<<"YES"<<br;
	}else{
		cout<<"NO"<<br;
	}

}

Can you assist here ?

[iceknight1093]

You can decelerate upto A m/s^2, or accelerate at -A m/s^2.
Your equation needs a minus sign, not plus. Change that and it passes.

[nike07]

@iceknight1093 could you please clarify this query?

[iceknight1093]

First, it’s not quite true to say that float is more ‘accurate’ than int - for example, it can’t even represent all the integers which int can without precision loss. However, that isn’t the problem here.

The main issue in your code is that you compute \sqrt{u^2 - 2*a*s} when the quantity inside the square root can be negative. float treats such a quantity as nan, whereas when you typecast it to int, it becomes INT_MIN which luckily works out for the comparison because if u^2 - 2*a*s < 0 the answer is always going to be true.

tl;dr whenever you compute the square root of something, make sure the that thing is not negative - you just got lucky here that C++ casts nan to INT_MIN when converted to int; and that might not always be what you want.

[anjaligoswami]

Can anybody please explain me why I am getting WA upon submission. And which case i am missing here

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
ll u,V;
cin>>u>>V;
ll a,s;
cin>>a>>s;

  if(u<=V)
  cout<<"Yes"<<"\n";
  
  else
  {
     float v = ( sqrt(float (u*u - 2*a*s) ) );
    
     if(v<=V)
     cout<<"Yes"<<"\n";
     
     else
     cout<<"No"<<"\n";
   
  }
    
    
}
return 0;

}

[abhicoder_03]

@iceknight1093
1
1 100 20 20

For this case, the answer is no.

[iceknight1093]

Why would it be No?
Chef is driving at 1 m/s, and wants to be at \leq 100 m/s after 20\ m.
He can achieve that by simply not decelerating at all.
In general if u\leq v the answer is going to be Yes, irrespective of what a and s are.

[abhicoder_03]

Oh okay i got that.
Thanks @iceknight1093