CHEFRES - EDITORIAL

binary-search
chefres
easy
line-sweep
ltime64
taran_1407

#1

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:


#2

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


#3

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:


#4

Python solution (short).


#5

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


#6

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


#7

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…


#8

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


#9

@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


#10

why am i getting tle? please help!!

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


#11

Whats offline mode???


#12

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


#13

#include
#include
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*.start=x;ta*.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*=temp;
		new_ca*=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*.start <= new_ca[j] && new_ca[j] < ta*.end)
		{
			sol[new_ca[j]]=0;
			j++;
		}
		else if(ta[i-1].end <= new_ca[j] && new_ca[j] < ta*.start)
		{
			sol[new_ca[j]]=ta*.start-new_ca[j];
			j++;
		}
		else if(new_ca[j]>=ta*.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*]<<endl;
}

}

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


#14

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.


#15

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


#16

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.


#17

My [solution][1] during contest got 30 pts with a WA for second test and the same


[2] in practice got AC(100 pts). 
This seems to be a bug as [this comment][3] is also similar and I am getting weird results in other problems too. 

  [1]: https://www.codechef.com/viewsolution/20374448
  [2]: https://www.codechef.com/viewsolution/20442402
  [3]: https://discuss.codechef.com/questions/136251/chefres-editorial/136345

#18

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.


#19

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


#20

Solutions will be linked soon.

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