NOTIME - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter:
Tester: Felipe Mota
Editorialist: Taranpreet Singh

DIFFICULTY

Cakewalk

PREREQUISITES

None

PROBLEM

There are X hours left for march challenge to end, while Chef needs H hours to complete last problem, with X < H. Check if Chef can solve the problem in at least one timezone. The timezone with their time difference to Chef’s timezone are given.

QUICK EXPLANATION

Chef can solve the problem if max(T_i) + X >= H where T_i denote time difference from Chef’s timezone.

EXPLANATION

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

Hence, Let’s try each timezone one by one and see if Chef can solve the problem in any of them. Chef can solve the problem in timezone T_i behind Chef’s timezone if T_i + X \geq 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 \geq H-X, we need to check if atleast one T_i \geq H-X holds. Hence, we can pick the timezone with largest T_i and hence, only one comparison would be sufficient.

Follow up

Let’s assume Chef’s friend selects the timezone in which Chef is transported. Chef’s friend chooses timezone to try to stop Chef from solving the problem. Can Chef still solve the problem?

TIME COMPLEXITY

The time complexity is O(N) per test case.
The memory complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#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;
} 
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char nxt){
  char ch=getchar();
  int v=0;
  int sgn=1;
  if(ch=='-')sgn=-1;  
  else{
    assert('0'<=ch&&ch<='9');
    v=ch-'0';
  }
  while(true){
    ch=getchar();
    if('0'<=ch && ch<='9')v=v*10+ch-'0';
    else{
      assert(ch==nxt);
      break;
    }
  }
  return v*sgn;
}

int main(){
  int n=rint(' ');
  assert(1<=n&&n<=100);
  int h=rint(' ');
  int x=rint('\n');
  assert(1<=x&&x<h&&h<=100);
  vector<int>t(n);
  bool can=false;
  for(int i=0;i<n;i++){
    t[i]=rint(i==n-1?'\n':' ');
    assert(1<=t[i]&&t[i]<=100);
    can|=(x+t[i]>=h);
  }
  if(can)puts("YES");
  else puts("NO");
  assert(getchar()==EOF);
  return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class NOTIME{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), H = ni(), x = ni();
        boolean canSolve = false;
        for(int i = 0; i< N; i++){
            int timeDiff = ni();
            if(timeDiff+x >= H)canSolve = true;
        }
        pn(canSolve?"YES":"NO");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new NOTIME().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile: