HOURS_LEFT - Editorial

editorial
1

PROBLEM LINK:

HOURS_LEFT

Setter: chayan_d
Tester: debrc

DIFFICULTY:

Easy

PREREQUISITES:

Arrays and arithmetic operations

PROBLEM:

You have only X hour left for the contest you are giving right now and there are few problems yet to solve. However, you are sure that you cannot solve the problem in the remaining time. From experience, you figures out that you needs exactly H hours to solve remaining problems.

Now, you decides to use your special power which you has gained through years of meditation. You can travel back in time. Specifically, your power allows you to travel to N different time zones, which are T_1,T_2,…,T_N hours respectively behind the current time.

Find out whether you can use one of the available time zones to solve the problem and submit it before the contest ends.

EXPLANATION:

Let’s see what happens when you teleports to a timezone with time Z hours behind current timezone. The result is that you get Z more hours to solve the problem.

Hence, Let’s try each timezone one by one and see if you can solve the problem in any of them. You can solve the problem in timezone T_i behind current timezone if T_i + X >= H. Checking each of these condition can be done in O(1) each, which is sufficient to solve the problem.

Optional observation

Can we solve above problem while checking above condition only once? Yes. Rewriting
T_i >= H-X, we need to check if atleast one T_i >= H-X holds. Hence, we can pick the timezone with largest T_i and hence, only one comparison would be sufficient.

TIME COMPLEXITY

The time complexity is O(N)

SOLUTIONS:

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

const int maxn = 100, maxt = 100, maxx = 99, maxh = 100;

int main()
{   
    int n, h, x; cin >> n >> h >> x;
    int maxv = -1;
    int val;
    for(int i = 0; i < n; i++){
        cin >> val;
        maxv = max(maxv, val);
    }
    string ans = "NO";
    if(maxv + x >= h)ans = "YES";
    cout << ans << endl;
}

Feel free to share your approach.

Suggestions are welcomed as always had been.