After reading the Editorial, I am using MergeSort to sort and BinarySearch for finding lowest upper and highest lower bounds, its showing TLE in a number of cases.
At 1st i applied this:
Taking a string of 1000000 and marking Wormhole up and down times with 1 and 2 in the respective places.
Something like this : 0101000000002100000020001
Then for each input contest i was pointing its starting and ending values in the array and moving left till i find the 1st 1 and right until i find the 1st 2, if either one dosent exist then contest cant be attempted, else the ans if the index i find the 1st 2 - index of 1st 1 +1.
This way only 2 cases showed TLE and all other were AC with good timings.(i understand it takes time approximately O(n^2) time)
If you could please suggest a way i could optimise this method anyhow.
And also could you please explain why is my code(BinarySearch and MergeSort) is showing too many TLEs.
link: CodeChef: Practical coding for everyone
So first, you yourself understand why your code is inefficient. O(n^2) will not work under the given constraints. Also, it doesnt really matter how many testcases you get wrong, 'cuz even if you get one wrong that is just wrong answer. Nothing changes that.
Any ways, may I understand how you are utilizing binary search here? The point is to find the minimum time a task can be done in (if it can be done) and then find the minimum time for all the tasks that can be done.
First off, you can sort these two arrays and let go of the string approach. Your string maneuver takes O(1) in theory, but here that might be the thing deterring your AC.
What I did was I sorted both the arrays, (one containing only entry wormholes and other containing only exit wormholes).
After that, to check if a task can be performed, it was a one liner:
if( exam_start_time < smallest_entry_wormhole or exam_end_time > largest_exit_wormhole)
After checking that, we move on to the binary search part.
We need to find the largest element smaller than exam_start_time for all exams. Now, cannot be done by any STL directly, but we can use lower_bound and pointer maneuvers to find it very easily.
Now we need to find the smallest element larger than or equal to exam_end_time. That can be done easily just by lower_bound.
And there, it has been done in just O(nlogn)!
As I said, I dont see how you are using merge sort or binary search. (I dont want read code right now, so you could just explain it to me).
Again, hope it was helful.
*correction :- smaller than or equal to exam_start_time
Yes thank you so much it was so helpful that i got AC.
I left the bounds checking whether a contest can even be attempted to the binary search functions, and you pointed out that it basically is just a linear check after the arrays have been sorted.So, After adjusting for just these 2 changes, it worked. Thankyou.
I am very glad it helped.