MEET - Editorial

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;
}

VIDEO EDITORIAL:

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



// Driver function 
int main() 
{ 


ll t=0;
cin>>t;




string p="";
string l="";
string r="";
//string x="";

int n=0;
ll c1=0;
char c=0;
char d=0;
char f=0;

while(t--)
{



//vector<int > p1;

for(int i=0; i<7; i++){
cin>>c;
p.push_back(c);}

// x=p;

 if(p[0]=='1' && p[1]=='2' && p[5]=='A'){
p[0]=p[0]+ (-1);
p[1]=p[1]+ (-2);}

if(p[5]=='P' && p!="12:00PM"){
p[0]=p[0]+1;
p[1]=p[1]+2;}


cin>>n;
//cin.ignore(numeric_limits<streamsize>::max(),'\n');

for(int i=0; i<n; i++)
{
for(int i=0; i<7; i++)
{
cin>>d;
r.push_back(d);
}

//string d1=r;

for(int i=0; i<7; i++)
{
cin>>f;
l.push_back(f);
}
//string b=l;




if(r[5]=='P' && r!="12:00PM"){
r[0]=r[0]+1;
r[1]=r[1]+2;}
//cout<<d1[0]<<endl;

//cout<<r<<endl;

if(l[5]=='P'&& l!="12:00PM"){
l[0]=l[0]+1;
l[1]=l[1]+2;}


//cout<<p<<endl;


if(r[0]=='1' && r[1]=='2' && r[5]=='A'){
r[0]=r[0]+ (-1);
r[1]=r[1]+ (-2);}


if(l[0]=='1' && l[1]=='2' && l[5]=='A'){
l[0]=l[0]+ (-1);
l[1]=l[1]+ (-2);}


if(p[5]=='P')
c=1;
if(p[5]=='A')
c=2;

if(c1==1){
r[5]='P';
l[5]='P';}


if(c1==2){
r[5]='A';
l[5]='A';}


//cout<<"p="<<x<<endl;
//cout<<"r="<<r<<endl;
//cout<<"l="<<l<<endl;
//p.clear();

if(r<=p && p<=l)
{
//p.clear();
//p="";
//p.erase(p.begin(),p.end());
cout<<"1";

}
else
{
//p.clear();
//p="";

cout<<"0";
}
r.clear();
l.clear();


//cout<<endl;
//cout<<r<<" "<<p;
//p.clear();

}
//p.erase(p.begin(),p.end());
//x.erase(x.begin(),x.end());

//p.clear();
p.clear();

//for(int i=0; i<p1.size(); i++)
//cout<<p1[i];

cout<<endl;
//p.clear();
//x.clear();





}



	return 0; 
} 
Why i am getting wa

@vichitr

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

can u tell why it is invalid and why we were using 24 hours format time. in question it’s
12 right

@akshay_012

Because its given in the problem that L_i≤R_i (Check the constraints). Lets take example of L=4PM, R=5AM. Do you see that given condition doesn’t hold now.

Where do you see using 24 hours format? Aren’t we using AM/PM?

@vichitr ya but what did u explained above acco. to L= 4pm =16:00 pm then only above condition going to fail is it correct.(this what we check l<=r 16<5 con. failed)
then it will be in 24 hours format

@akshay_012 looks like you need to google buddy! Did you check the link given in the problem statement? If no, check here. Obviously it doesn’t matter whether its 12 hour format or 24 hour format. It was bit hard implementation if given in 12 hour format. That’s it! In 12 hour format also, we represent all times, not only 12 hours of the day! For the given example, in 12 hour format we write it 4:00 PM and in 24 hour format, we write it 16:00.

And for the condition, we need to compare the times, not the numbers! So 4:00 PM \nleq 5:00 AM.

@vichitr ok one last thing let’s say L=10:00 AM AND R=11:00 AM THEN condi. satisfied .
(how becuz 10<11 in number)
then why u said not to compare number and

HOW DID U GET TO KNOW THAT WE HAVE TO COMPARE( AM AND PM NOT NUMBER) FROM THE QUESTION
(I did’t get this thing . got WA )

and last i got it we have to COMPARE AM AND PM <<<----am i correct.

Whatever I have written in the editorial is case based. If you read it carefully, you should get it.

I’m not sure what exactly is your doubt but in the problem, its clearly written that check if the chef’s time P is in the given time intervals. See last line of problem statement – check if L_i≤P≤R_i for each valid i.

No, you have to compare times, not just AM/PM or numbers. But you can break it in some cases where only AM/PM or number comparison should be OK. Just like how I have done in the editorial.

Give it some time and take examples and see! Its not something tricky!

thk dude

#include

#include

using namespace std;

int main()

{

int t;

cin>>t;

cin.ignore();

while(t--)

{

    string mt;

    getline(cin,mt);

    cout<<mt;

    int min;

    if(mt.substr(6,1)=="A")

    {

        if(mt.substr(0,2)=="12")

         min=0+stoi(mt.substr(3,2));

        else

        min=stoi(mt.substr(0,2))*60+stoi(mt.substr(3,2));

    }

    else

    {

        if(mt.substr(0,2)=="12")

         min=720+stoi(mt.substr(3,2));

         else

         min=stoi(mt.substr(0,2))*60+stoi(mt.substr(3,2))+720;

         

    }

    int n;

    cin>>n;

    for(int i=0;i<n;i++)

    {

        string lr;

        int lm,rm;

        getline(cin,lr);

    if(lr.substr(6,1)=="A")

    {

        if(lr.substr(0,2)=="12")

         lm=0+stoi(lr.substr(3,2));

        else

        lm=stoi(lr.substr(0,2))*60+stoi(lr.substr(3,2));

    }

    else

    {

        if(lr.substr(0,2)=="12")

         lm=720+stoi(lr.substr(3,2));

         else

         lm=stoi(lr.substr(0,2))*60+stoi(lr.substr(3,2))+720;

    }

        if(lr.substr(15,1)=="A")

    {

        if(lr.substr(9,2)=="12")

         rm=0+stoi(lr.substr(12,2));

        else

        rm=stoi(lr.substr(9,2))*60+stoi(lr.substr(12,2));

    }

    else

    {

        if(lr.substr(9,2)=="12")

         rm=720+stoi(lr.substr(12,2));

         else

         rm=stoi(lr.substr(9,2))*60+stoi(mt.substr(12,2))+720;

    }

    if(lm<=min && rm>=min)

     cout<<"1";

     else

     cout<<"0";

 }

cout<<endl;

}

return 0;

}
getting error as follows
terminate called after throwing an instance of ‘std::out_of_range’
what(): basic_string::substr: __pos (which is 6) > this->size() (which is 0)
Whats wrong with this code?