RACINGEN - Editorial

PROBLEM LINK:

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

Author: Le Duc Minh
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Ann has X energy, and in each second can either run (if she has more than 0 energy) and lose 1 energy, or rest (and gain 1 energy, if she has less than X). She cannot have more than X energy. It takes her R minutes of running to finish a race - is there some sequence of running and resting which lets her finish the race within M minutes?

EXPLANATION:

Before anything else, to simplify calculation, convert R and M to seconds by multiplying them by 60.
What is the least amount of time within which Ann can run for R seconds?
She can first run for X seconds, and expend all the energy she initially has. After that, running for one second requires two seconds of time - one to rest and gain 1 energy, and then one to actually run. This is optimal.

Proof

The strategy described above is, in simpler words, to run when Ann has positive energy and rest when she has none. Optimality can be proved using an exchange argument.
Consider any optimal strategy where Ann has positive energy at some time, but decides to rest.
We can then find a time i such that Ann has positive energy at time i, rests at time i, and runs at time i+1.
Exchange her actions at these two times - i.e, suppose she runs at time i and rests at time i+1. Keep all other actions the same.
The amount of time she ran is exactly the same in both cases, and her remaining energy is either the same (if her energy at time i was < X), or greater (if her energy at time i was X). Thus, exchanging the actions gives a solution which is not worse than the original.

tl;dr, the strategy described of always running when possible is no worse than any other optimal solution.

So,

  • If R\leq X, she needs exactly R seconds
  • If R > X, she needs X + 2*(R-X) seconds
    Simply compute this number, and check whether it is \leq M.
Be wary of overflow!

Note that the constraints have R,M \leq 10^9, and converting them to seconds will result in integers upto 6*10^{10}. This will not fit in a 32-bit integer, so make sure you use the correct data type.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

SOLUTIONS:

Setter's Solution (C++)
#include<bits/stdc++.h>
using namespace std;

int q;
long long x, t, m;

int main() {
	cin >> q;

	while (q--) {
		cin >> x >> t >> m;

		// Convert to seconds
		t *= 60;
		m *= 60;

		long long time_needed = min(x, t);
		if (x < t) {
			time_needed += (t - x) * 2;
		}

		if (time_needed <= m) {
			cout<< "YES\n";
		}
		else {
			cout << "NO\n";
		}
	}
}
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 tests;
    cin>>tests;
 
    while(tests--){
        long long int x, t, m;
        cin>>x>>t>>m;
        t *= 60;
        m *= 60;
        long long int curr = min(m, x);
        m -= curr;
        curr += m / 2;
        if(curr >= t) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
 
    return 0;
}
Editorialist's Solution (Python)
q = int(input())
for _ in range(q):
    x, t, m = map(int, input().split())
    t *= 60
    m *= 60
    if m < t:
        print('NO')
    elif t <= x:
        print('YES')
    elif x + 2*(t-x) <= m:
        print('YES')
    else:
        print('NO')
2 Likes

Setter solution gives wrong answer.
i tried same idea. can anybody tell me what is wrong in the code.
void solve(){
lli x,r,m,t;
cin>>x>>r>>m;

r=r*60;m=m*60;
if(r<=x&&m>=x){
    cout<<"YES"<<endl;return;
}
lli leftr=r-x;
lli leftm=m-x;
lli timetake=2*leftr;
if(timetake<=leftm){
    cout<<"YES"<<endl;return;
}
cout<<"NO"<<endl;

}

Oops, you’re right regarding the setter’s solution: I pulled the wrong submission. Should be fixed now.

Editorial solution also gives WA :thinking:

1 Like

Convert r and m to seconds.
Suppose r and m are less than x and r>m.
Will your code always give NO?

Test case
1
60000000 4 3

That is definitely not true, it gives AC.

how did pypy3 of the same code give TLE, isnt pypy3 supposed to be faster than python3 ?

https://www.codechef.com/viewsolution/44230786

@rk173238 I guess you are not checking for m<x condition.

Suppose, r=10 (600 sec), m=15 (900 sec), X=1200

It will not hit the first if con, if(r<=x && m>=x) and then code will go to calculate,

leftr=-600,
leftm=-300

And then checking with 2*<> condition.

Negative values of leftr and leftm are counterintuitive as they only need to be checked if we have outcrossed our energy, X and now recharging and going in each cycle.

hey, can someone point out the mistake in this code:

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

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

#ifndef ONLINE_JUDGE
    freopen("input", "r", stdin);
    freopen("output", "w", stdout);
#endif
    
    int t; cin >> t;
    while (t--) {
        int x, r, m;
        cin >> x >> r >> m;

        int rest_time = (m - r) * 60;
        int rest_needed = (r * 60) - x;

        if (rest_needed <= rest_time) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}
1 Like

why is this giving WA. can someone help.

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

void solve(){

unsigned long long int x,r,m;
cin>>x>>r>>m;
r=r*60;
m=m*60;
if(r>m){
    cout<<"NO"<<"\n";
}
unsigned long long int reSec = r-x;
unsigned long long int avSec = m-x;
unsigned long long int maxSec = avSec/2;
if(maxSec >= reSec){
	cout<<"YES"<<"\n";
	return;
}
cout<<"NO"<<"\n";

}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t>0){
solve();
t–;
}

}

Seems like it was an issue on the server’s side - I resubmitted the same code and it passes.

I done the same but WA

What’s wrong in my code?

#include<iostream>

using namespace std;

int main(){

    int T,X,R,M,P;

    cin>>T;

    while(T--){

        cin>>X>>R>>M;

        if(X+(60*M-X)/2>=60*R){

            cout<<"YES\n";

        }

        else{

            cout<<"NO\n";

        }

    }

    return 0;

}

@gautamsuthar int is wrong, shud be long long int as it will overflow.

1 Like

I missed the edge cases during the contest; but here’s my approach anyway:
First convert M and R to seconds. We first check for edge cases where it’s impossible to ever get a valid answer M < R and where it’s always possible, if our initial energy is enough to complete the race without any rest X \geq M. After we’ve dealt with edge cases, this is how we can proceed.

Given initial energy X, for every unit run, one unit energy is spent, and for every second rest, one unit energy is gained. After R units of running and rest of rest, my remaining energy should either be positive, or 0 at the very least.
\implies E = X-R+rest \geq 0
Also, the time we have spent running R and resting time rest should not exceed M
\implies rest + R \leq M

Rearranging and adding both inequalities, rest cancels out and we’re left with the sufficient condition for truth.
X \geq 2*R - M

Link

1 Like

@gautamsuthar Say, R=15, M=10, X=1200
X+(60M-X)/2 = 1200+(-600)/2 = 900
60
R=900

It will print yes, but shud be NO.

Certain edge conditions are missing like, r>m, x>r, etc

1 Like

Can anybody help where am I wrong?

void solve(){
int X, R, M;    cin >> X >> R >> M;

if(X >= R*60) cout << "Yes" << endl;
else {

    M = M * 60;
    R = R * 60;
    int left = 2*(R - X);

    if((left+X) <= M )  cout << "Yes" << endl;
    else                cout << "No"  << endl;


}

}

@skaarss Check for this test case. X=240 R=2 M=1

Can someone help me figure out the mistake in my code?

#include <iostream>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        long long int x,r,m;
        cin>>x>>r>>m;
    
        r*=60;
        m*=60;
    
        if(r-x<=(m-x)/2){
            cout<<"YES"<<endl;
        } else {
            cout<<"NO"<<endl;
        }
    }
}
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    ll t,n,i,j,x,r,m,a,b,c,d;
    cin>>t;
    while(t--)
    {
        cin>>x>>r>>m;
        a=r*60;
        b=2*(a-x);
        c=m*60;
        d=c-x;
        if(x>=a){
            cout<<"YES\n";
        }else{
            if(b<=d){
                cout<<"YES\n";
            }else{
                cout<<"NO\n";
            }
        }
    }
    return 0;
}

My approach was the same too…although I got WA…Can anybody please tell me why did this happen