CHEFRES - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

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

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

  •   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.

Click to view

If X belong to [L, R), Food is delivered immediately and thus, waiting time is zero.

Otherwise, we will have to wait for Interval to begin, that is, wait from time X up to time L, resulting in waiting time L-X.

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.

Click to view

In binary search solution, sorting cost O(N*logN) and each query take O(logN) time, thus total time O((M+N)*logN)

For offline solution, sorting dominates time complexity. After sorting, rest part takes only O(M+N) time.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’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. :slight_smile:

1 Like

Can’t see the solutions - shows html with “Access denied” message.

2 Likes

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. :slight_smile:

Python solution (short).

1 Like

I was amazed by seeing offline mode XD…
Idk how that idea came first to some of you…

1 Like

@eaugenethomas You don’t check bounds in the loop while(v[f].first){f++;} - f runs beyond the size of the vector.

@eugalt Thanks for pointing out.
Now it works fine
https://www.codechef.com/viewsolution/20400880

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…

Solutions will be linked soon.

Until that, I am going to post ideone links for my solutions.

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.

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.

@taran_1407 ,I applied binary search but it is showing tle.Could u explain?
https://ide.geeksforgeeks.org/XgWvSXyZqX

@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

why am i getting tle? please help!!

link to my solution is: https://www.codechef.com/viewsolution/20407310

I submitted your code in practice, and it got AC. This is a known problem.

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.

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

Whats offline mode???

Offline mode means we read all queries first, answering them in some specific order and printing answers according to their order in input.

Can anyone help me I have used Binary search, but it gives me TLE?
link: Ideone

//