PROBLEM LINK:Practice Setter: Hasan DIFFICULTY: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
EXPLANATIONSince 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. 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_{j1} \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 ComplexityFor binary search solution, Time complexity is $O((M+N)*logN)$. Proving complexity is not hard for this problem, though may be referred in secret box. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution 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".
asked 30 Sep '18, 01:05

@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

@eugalt Thanks for pointing out. Now it works fine https://www.codechef.com/viewsolution/20400880 answered 30 Sep '18, 10:07

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
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/linktotestcasesaftercontests
(30 Sep '18, 11:03)

@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
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)

@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
I submitted your code in practice, and it got AC. This is a known problem. https://discuss.codechef.com/questions/136250/waincontestacinpractice
(30 Sep '18, 21:18)
So why my solution got WA for rest of 70 points during the contest.
(03 Oct '18, 07:53)

why am i getting tle? please help!! link to my solution is: https://www.codechef.com/viewsolution/20407310 answered 30 Sep '18, 20:05
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)

include<iostream>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);
} what is wrong with my code? it's complexity is nlogn (I think so) so why it is giving TLE answered 01 Oct '18, 16:17

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
You're passing on the vector in
(03 Oct '18, 16:33)

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

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

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

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

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