PROBLEM LINK:
Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest
Author: Smit Mandavia
Testers: Felipe Mota and Radoslav Dimitrov
Editorialist: Vichitr Gandas
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given meeting time P. Also given N other time intervals (numbered 1 through N); for each valid i, the i-th interval is from a time L_i to a time R_i (both inclusive). Check if L_i \le P \le R_i for each valid i.
QUICK EXPLANATION
For each given time interval [L, R], check if it contains the meeting time P ie L \le P \le R.
EXPLANATION
Iterate over all N time intervals and check if they contain the time P. To check if a time interval [L, R] contains the time P, we have three cases.
Case-1: Both L and R are in AM.
Now if P is in PM then obviously it’s not in the range [L, R] because they are in AM. If time P is also in AM then check if L <= P and P <= R.
Case-2: Both L and R are in PM.
Now if P is in AM then obviously it’s not in the range [L, R] because they are in PM. If time P is also in PM then check if L <= P and P <= R.
Case-3: Time L is in AM and time R is in PM.
In this case we have two subcases.
Case-3a: Time P is in AM: then check L <= P. In this case we don’t need to check if P <= R.
Why?
Because P is in AM and R is in PM then obviously P <= R.
Case-3b: Time P is in PM: then check P <= R. In this case we don’t need to check if L <= P.
Why?
Because L is in AM and P is in PM then obviously L <= P.
Here its not possible that time L is in PM and time R is in AM because then the interval [L, R] would be invalid time interval.
Now for given two time intervals T_1, T_2, where T_1 is H_1 hours and M_1 minutes. And T_2 is H_2 hours and M_2 minutes. And they both are either in AM or in PM. How to check if T_1 <= T_2?
If H_1 < H_2 then YES. if H_1 > H_2 then NO. If H_1=H_2 then check if M_1 <= M_2.
Corner cases
When H_1=12 and H_2 \ne 12. In this case, its YES ie T_1 < T_2.
When H_2=12 and H_1 \ne 12. In this case, its NO ie T_1 > T_2.
Pseudo Code
def check:
if h1 == 12 and h2 != 12:
return True
if h2 == 12 and h1 != 12:
return False
if h1 == h2:
return m1 <= m2
return h1 < h2
Time complexity of this solution is \mathcal{O}(N) as we just iterate over all time intervals. Checking if a time interval contains the meeting time, is \mathcal{O}(1). Space complexity is also \mathcal{O}(1).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
// compare two time in format HH:MM AM or HH:MM PM
bool compare(string L,string R){
// remove last char as it will always be M
L.pop_back();
R.pop_back();
// HH:MM AM <= HH:MM PM always hence return if last char of both time are not equal
if(L.back()!=R.back())
return L.back() < R.back();
// Now both time will be either AM or PM so we can just ignore last char
// 12:MM < 01:MM < 02:MM ... < 11:MM hence replace 12 by 00
if(L[0]=='1' && L[1]=='2')
L[0]=L[1]='0';
if(R[0]=='1' && R[1]=='2')
R[0]=R[1]='0';
// now time is in format HH:MM where 00<=HH<=11 and 00<=MM<=59 hence we can directly compare both strings
return L<=R;
}
int main() {
FIO;
int t,n,k,i,j;
string s,Li,Ri,p;
cin >> t;
while(t--){
p="";
// input p
cin >> s;
p+=s;
cin >> s;
p+=s;
cin >> n;
while(n--){
Li=Ri="";
// input Li
cin >> s;
Li+=s;
cin >> s;
Li+=s;
// input Ri
cin >> s;
Ri+=s;
cin >> s;
Ri+=s;
// check if Li <= p <= Ri that is if Li <= p and p <= Ri
if(compare(Li,p) && compare(p,Ri))
cout << "1";
else
cout << "0";
}
cout << "\n";
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = readIntLn(1, 500);
while(t--){
auto readTime = [](bool nl){
string time = readStringSp(5, 5);
string ampm;
if(nl) ampm = readStringLn(2, 2);
else ampm = readStringSp(2, 2);
int val = 0;
val = ((time[0] - '0') * 10 + time[1] - '0') * 60 + (time[3] - '0') * 10 + time[4] - '0';
val %= (12 * 60);
if(ampm == "PM"){
val += 12 * 60;
}
return val;
};
int p = readTime(true);
int n = readIntLn(1, 500);
string ans(n, '0');
for(int i = 0; i < n; i++){
int l = readTime(false);
int r = readTime(true);
if(l <= p && p <= r) ans[i] = '1';
}
cout << ans << '\n';
}
return 0;
}
Editorialist's Solution
/***************************************************
@author: vichitr
Compiled On: 06 Feb 2021
*****************************************************/
#include<bits/stdc++.h>
using namespace std;
bool check(int h1, int m1, int h2, int m2){
// if h1=12 and h2 != 12 then T1 < T2.
// if h2=12 and h1 != 12 then T1 > T2.
// because in 12 hr format 12:00 AM then 1,2,...upto 11:59 AM
// similarly 12:00 PM then 1,2,...upto 11:59 PM
if(h1 == 12 and h2 != 12)
return 1;
if(h2 == 12 and h1 != 12)
return 0;
if(h1 == h2)
return m1 <= m2;
return h1 < h2;
}
void solve(){
// Here P1 is time and P2 is AM/PM
string P1, P2; cin>>P1>>P2;
// get hour and minute for time P
int hp = stoi(P1.substr(0, 2));
int mp = stoi(P1.substr(3, 2));
int n; cin>>n;
string ans;
for(int i=0;i<n;i++){
// here L1, R1 are time
// and L2, R2 are AM/PM
string L1, L2, R1, R2;
cin >> L1 >> L2 >> R1 >> R2;
// fetch Hour, Min for time L
int hl = stoi(L1.substr(0, 2));
int ml = stoi(L1.substr(3, 2));
// fetch hour and minutes for time R
int hr = stoi(R1.substr(0, 2));
int mr = stoi(R1.substr(3, 2));
// case-1 and case-2
// either both AM or both PM
if(L2 == R2){
// check P2 = L2, ie P and L,R all should be either AM or PM
// check L <= P and P <= R
if(P2 == L2 and check(hl, ml, hp, mp) and check(hp, mp, hr, mr))
ans += "1";
else
ans += "0";
}
else // case-3
{
// case - 3a: P is in AM
if(P2 == "AM"){
// check L <= P
if(check(hl, ml, hp, mp))
ans += "1";
else
ans += "0";
}
// case - 3b: P is in PM
else{
// check P <= R
if(check(hp, mp, hr, mr))
ans += "1";
else
ans += "0";
}
}
}
cout<<ans<<"\n";
}
signed main()
{
int t=1;
cin >>t;
for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}