Editorialist: Adithya Dsilva




Binary search, Greedy


You are given arrays S and E, each consisting of N elements. S_i and E_i represent the start time and end time of contest i respectively.
You are given array V consisting of X elements, representing the different times at which we can reach the contest venue.
You are given array W consisting of Y elements, representing the different times at which we can leave the contest venue.

To participate in contest i, you must reach the venue on or before time S_i and can leave back home on or after time E_i. The overall time you spent in the contest is thus (time of departure - time of arrival) + 1.

You are to participate in exactly 1 contest. Determine the minimum possible time you spend in a contest.


Claim: If V_q < V_r \le S_i, arriving at time V_r reduces the time spent waiting (in contrast to arriving at time V_q) for contest i to begin.


Given: V_q < V_r \le S_i.

To Prove: S_i-V_r<S_i-V_q.

V_q < V_r \Rightarrow -V_q > -V_r \Rightarrow S_i-V_q>S_i-V_r.

\therefore S_i-V_r<S_i-V_q.

Similar claim can be made for the time of departure.

Claim: If E_i \ge W_q > W_r, departing at time W_q reduces the time spent waiting after the end of contest i.


Left to the reader. Similar proof as above.

Thus, for every contest i, finding the greatest V_r \le S_i and smallest W_q \ge E_i determines the best possible arrival and departure times.
Thus for contest i, (W_q - V_r) + 1 is the minimum time required to be spent. This can be checked for every contest, to find the contest which reduces the overall time to be taken.

However, how do we find the best W_q and V_r? A simple O(N) loop can be done searching for the best value. However, can we do better?

Since we are searching for the largest/smallest number lesser/greater than a particular value, a modified binary searching function can be used.
This function should determine the largest/smallest number in a array, lesser/greater than or equal to a given value.

The builtin functions like lower_bound / upper_bound in C++, Collections.binarySearch in Java etc can be used to determine the answer. (Please refer to the docs, for implementations in other language)

Determining largest number in an array \le given value:


Let the particular value be X.

upper_bound returns the least number greater than X. Let this number be Y.

Claim: In the sorted, unique array, the element right before Y is lesser than or equal to X.

Let the number right before Y in the sorted array be Z. Let us assume Z > X. We know that Z < Y (not \le since the array is unique); Thus X < Z < Y implies Y is not the least value greater than X, which is a contradiction to upper_bound.

Thus proved!

Determining smallest number in an array \ge given value:


This is quite straightforward, and running lower_bound gives the answer!

Thus for contest i, the minimum time required can be found as done below. Remember to sort V and W, as lower_bound/upper_bound requires a sorted array!

int r = upper_bound(V.begin(), V.end(), S[i]) - V.begin() - 1;
//upper_bound gives 1st number > S[i]. -1, to get the
//1st number <= S[i] (works since V is unique)!

int q = lower_bound(W.begin(), W.end(), E[i]) - W.begin();
//lower_bound returns first number >= E[i], which is the value we
//are searching for!

mini = (W[q] - V[r]) + 1;
//Out of bounds case to be handled!

Thus the answer can be found, by determining the minimum time required for each contest, and finding the least amongst them.


sort(V.begin(), V.end());
sort(W.begin(), W.end());

int ans = INT_MAX; //Maximum value of INT
for(int i = 0; i < N; i++){ //0 based indexing
	int r = upper_bound(V.begin(), V.end(), S[i]) - V.begin() - 1;
	//upper_bound gives 1st number > S[i]. -1, to get the
    //1st number <= S[i] (works since V is unique)!
	int q = lower_bound(W.begin(), W.end(), E[i]) - W.begin();
	//lower_bound returns first number >= E[i], which is the value we
    //are searching for!
	if(r != invalid and q != invalid) //Out of bound check
        ans = min(ans, W[q] - V[r] + 1);
cout << ans << endl;


Sorting V and W using builtin functions takes O(X\log X+Y \log Y).

lower_bound takes O(\log X+\log Y) (since we have to compute r, q) for every value in A.
Thus, it takes O(N (\log X+\log Y)) to compute the minimum for every element in A.

The overall complexity thus is : O(X\log X+Y\log Y+N(\log X+\log Y)) \approx O(X\log X+N\log X).

Substituting maximum values gives us O(10^5*\log 10^5 + 10^5*\log 10^5) \approx O(10^6).


Editorialists solution can be found here.



Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!

Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome :star_struck: editorial)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

Also don’t forget to up-vote this post if you liked it ! :smile:


I applied the same logic about finding the largest Vr and smallest Wq . However , I am getting AC on only 3(2 from subtask 1 and 1 from subtask 2) test cases and wrong answer or TLE on others.
I would have understood if I had only got TLE but I dont understand why I am getting a WA. Could someone have a look at the code and point out the error?
If someone could point out some test cases where the code is failing , it would be great.
Thank you

TLE- Because of the linear search. Use binary search (check editorial)
WA- The cases where the contest cannot be participated in are not handled. They return negative values and the most negative value is wrongly selected as the answer.
Check this case- Input:
2 4 1
7 10
3 6
3 2 8 9
Expected Output: 5
Your Output: -2

1 Like

Thank you for your response! I will check accordingly!

My solution to this problem gives me WA on 4 subtasks, could someone help me figure out why that’s the case?

Maybe there’s some problem with your binary search implementation. Check out my solution without using STL lower_bound function - https://www.codechef.com/viewsolution/38125103

Would appreciate someone checking https://www.codechef.com/viewsolution/40191286. All are AC with the exception of Task 14 which is WA. I would like to know what I have done wrong.

Could someone plz tell where I am going wrong. I had used the same logic for finding max start time and min end time using binary search and then updating min but I am getting WA in test case 4.
Link :- Solution: 41732060 | CodeChef