×

# CHEFRES - EDITORIAL

Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

Simple

# PREREQUISITES:

Maps, Binary search or ordering queries would do fine.

# PROBLEM:

Given $N$ disjoint intervals $[L_i, R_i)$ and $M$ query times $P_i$, we need to print the minimum waiting time from query point to any time belonging to any interval, at or after query time.

# SUPER QUICK EXPLANATION

• Sort intervals as well as query time, maintain two pointers and for every interval, iterate from earliest query time $X$ and answer is $L_i - T_i$ if query time is before interval, otherwise $0$ for every query time such that $R_{i-1} \leq X < R_i$.
• Alternate online solution is for every query $X$, to use binary search to find earliest interval such that $X < R_i$. If query time lies in interval, Wait time is zero, else $L_i-X$.
• Query times at or after $R_n$ will wait forever (if possible without food :D)

# EXPLANATION

Since intervals are disjoint, every query point can belong to at most one interval, which we need to find, in order to find out the waiting time. Suppose we know that for query time $X$, the required interval is $[L, R)$. How to calculate waiting time?

See the secret box.

View Content

This is enough to solve sub task 1, since we can check for every query time, waiting time for all intervals ending after query time and print the minimum of all waiting times, but this results in $O(N*M)$ complexity, which is too slow for sub task 2.

We need to find this interval fast. We know that the interval we are seeking is in fact the earliest interval which ends after query time.

It is ideal to sort the intervals, whenever we need to find such earliest, first, last intervals. Sorting is almost used in every problem which involves intervals.

Anyways, after sorting, if interval j is required interval, we know that either $j==1$ of $R_{j-1} \leq X < R_j$. This can be used as condition for binary search, since all interval before jth interval has $R_i \leq X$ and all intervals after jth interval has $R_i < X$.

Otherwise, we can sort the query points and use two pointers, one for query points and one for interval index. For every interval, assign minimum times to all query points which are before $R_i$, not assigned answer yet.

In case answer is not assigned to query, customer has to survive without food forever.

# Time Complexity

For binary search solution, Time complexity is $O((M+N)*logN)$.
For Offline solution, Time complexity is $O(N*logN +M*logM)$.

Proving complexity is not hard for this problem, though may be referred in secret box.

View Content

# AUTHOR'S AND TESTER'S SOLUTIONS:

Edit: Until above links are not working, You may refer solution here.

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

3.9k2895
accept rate: 22%

For a binary search solution, you may refer any solution in practice using binary search. I found this solution, doing binary search using lower_bound function.

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

(30 Sep '18, 21:40)

 2 Can't see the solutions - shows html with "Access denied" message. answered 30 Sep '18, 04:01 3★eugalt 282●7 accept rate: 4% Solutions will be linked soon. Until that, I am going to post ideone links for my solutions. (30 Sep '18, 10:59)
 1 Python solution (short). answered 30 Sep '18, 07:53 3★eugalt 282●7 accept rate: 4%
 0 Why does this question have line sweep tag?? I didn't participate in the contest. But as soon as I have seen this tag I wanted to upvote. But now I'm reserving it for some other day. Comment on editorial - I upsolved it using offline mode. But was amazed by seeing binary search approach. :) answered 30 Sep '18, 04:58 2.6k●1●5●16 accept rate: 10% 1 I was amazed by seeing offline mode XD.... Idk how that idea came first to some of you.... (30 Sep '18, 09:28) Actually i just saw i referred to it by offline solution only. Didn't realize this until i posted the editorial, that i have not named the offline solution. (30 Sep '18, 11:00)
 0 @eaugenethomas You don't check bounds in the loop while(v[f].first){f++;} - f runs beyond the size of the vector. answered 30 Sep '18, 09:55 3★eugalt 282●7 accept rate: 4%
 0 @eugalt Thanks for pointing out. Now it works fine https://www.codechef.com/viewsolution/20400880 answered 30 Sep '18, 10:07 3●2 accept rate: 0%
 0 can i get the test cases that u have been uploaded for this?? please, i need to check it out where i made my program to do mistake.. thanks in advance.... answered 30 Sep '18, 10:45 1 accept rate: 0% No, Test cases cannot be shared, as per codechef rules. You can see detailed discussion or put forward your views if you wish to, at link below. https://discuss.codechef.com/questions/7509/link-to-test-cases-after-contests (30 Sep '18, 11:03)
 0 @taran_1407 ,I applied binary search but it is showing tle.Could u explain? https://ide.geeksforgeeks.org/XgWvSXyZqX answered 30 Sep '18, 12:10 3★utchinu 0●1 accept rate: 0% You're passing the vector by value in your binary search. That by itself is $O(n)$. Pass it by reference. (03 Oct '18, 17:33) algmyr7★
 0 @taran_1407 , can you please check my code for this problem ,because i dont understand that why i got only 30 point and WA for rest of test cases. link of my solution : https://www.codechef.com/viewsolution/20395523 answered 30 Sep '18, 12:53 0●1 accept rate: 0% I submitted your code in practice, and it got AC. This is a known problem. https://discuss.codechef.com/questions/136250/wa-in-contest-ac-in-practice (30 Sep '18, 21:18) eugalt3★ So why my solution got WA for rest of 70 points during the contest. (03 Oct '18, 07:53)
 0 why am i getting tle? please help!! link to my solution is: https://www.codechef.com/viewsolution/20407310 answered 30 Sep '18, 20:05 1 accept rate: 0% Your solution tries to iterate over range of size up to 1e9, which cannot be completed in one second. Assume 1e7 iteration can be done in one second. (30 Sep '18, 21:36)
 0 Whats offline mode??? answered 01 Oct '18, 03:10 1★zeph1yr 1 accept rate: 0% Offline mode means we read all queries first, answering them in some specific order and printing answers according to their order in input. (01 Oct '18, 03:26)
 0 Can anyone help me I have used Binary search, but it gives me TLE? link: Ideone answered 01 Oct '18, 10:10 1 accept rate: 0%

# include<algorithm>

using namespace std;

struct Interval { int start=-1, end=-1; };

bool compareInterval(Interval i1, Interval i2) { return (i1.start < i2.start); }

int main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; Interval ta[n+1]={{-1,-1}}; int ta_len=1; for(int i=1;i<n+1;i++) {="" int="" x,y;="" cin="">>x>>y; ta[i].start=x;ta[i].end=y; ta_len++; } sort(ta, ta+ta_len, compareInterval);

    int ca[m+1]={-1};
int new_ca[m+1]={-1};
int maxv=-1;
int ca_len=1;
for(int i=1;i<m+1;i++)
{
int temp;
cin>>temp;
if (maxv<temp)
maxv=temp;
ca[i]=temp;
new_ca[i]=temp;
ca_len++;
}

sort(new_ca,new_ca+ca_len);

ca_len--;
int sol[maxv+1]={0};
int j=1;
int i=1;
while(i<ta_len)
{
if (ta[i].start <= new_ca[j] && new_ca[j] < ta[i].end)
{
sol[new_ca[j]]=0;
j++;
}
else if(ta[i-1].end <= new_ca[j] && new_ca[j] < ta[i].start)
{
sol[new_ca[j]]=ta[i].start-new_ca[j];
j++;
}
else if(new_ca[j]>=ta[i].end)
i++;
}

if (j<ca_len+1)
{
for(int i=j;i<ca_len+1;i++)
{
sol[new_ca[j]]=-1;
j++;
}
}

for(int i=1;i<=ca_len;i++)
cout<<sol[ca[i]]<<endl;
}


}

what is wrong with my code? it's complexity is nlogn (I think so) so why it is giving TLE

1
accept rate: 0%

 0 why my binary approach solution is giving tle. i think it's complexity is nlogn. Also,please suggest some cases for which my code is giving WA. answered 01 Oct '18, 18:00 2●2 accept rate: 0% You're passing on the vector in int binarysearch(vector > v1,ll l,ll r,ll key) by value, so you copy a vector of pairs for every single call to binary search. Make that a reference int binarysearch(vector > &v1,ll l,ll r,ll key) and you should get decent running times. (03 Oct '18, 16:33) algmyr7★
 0 Can anyone tell me why my BS approach gives TLE but sorting queries approach does not. Both solutions have the same complexity. Both solutions here - BS - https://pastebin.com/PyhCsSj0 Sorting queries - https://pastebin.com/D5QV9TJH answered 01 Oct '18, 18:38 1 accept rate: 0%
 0 Hey. So this question i had solved in java on the contest day, and the submission from that day is here. And today, after fruitlessly racking my brain for where the NZEC could have arised, i submitted the same code, and you know it, it showed full AC. Today's code is here. So what did actually transpire by on the contest day? I am totally perplexed and an answer would be so satisfying. answered 02 Oct '18, 01:00 1 accept rate: 0%
 0 My solution during contest got 30 pts with a WA for second test and the same code in practice got AC(100 pts). This seems to be a bug as this comment is also similar and I am getting weird results in other problems too. answered 03 Oct '18, 03:12 12●1 accept rate: 0%
 0 I am using binary search and also pass my vector by reference, still got tle. Please help me, what could i do to decrease the time? Here is my solution link - https://www.codechef.com/submit/complete/20938161. Please help. answered 17 Oct '18, 15:54 0●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,770
×1,041
×651
×78
×47
×10

question asked: 30 Sep '18, 01:05

question was seen: 2,926 times

last updated: 17 Oct '18, 15:54