https://www.codechef.com/viewsolution/20393250
this is my solution for CHEFRES
I got only 30 points.can someone please correct the thing i have done wrong.
Without even reading the task line 86 seems suspicious, possible index out of range issue. But how to know for sure? Write a test case generator! I wrote a quick one and indeed I get index out of bounds on line 86.
Simple test case that fails:
1
1 1
89 138
125
Actual solutions to the problem
There are multiple approaches, I’ll cover two of them.
(Edit: just realized there is also the tutorial that actually covered both my approaches here. Oh well, I guess it’s good practice anyway.)
Offline algorithm
(better time complexity)
The problem is actually quite straightforward when thinking about it right. You’ve already sorted the intervals, which is a good start. But wouldn’t it be nice to sort the times as well? If you do that you can loop through all the l,r segments and pick times p while p \geq r and compute the answer for that time (the while is aborted if p belongs to a later segment).
However we can’t just blindly sort the times since we need to print them in order, but we can find the order the elements would have come in if they had been sorted. This order can then be used to go through the queries and store their results in a result array.
Complexity: O(n \log(n) + m \log(m)) per test case, sample solution 20443476.
For reference this is called an offline algorithm, since we don’t do the queries in order and hence couldn’t perform well if we only were given one query at a time.
Alternative online algorithm
(slightly worse time complexity, but online which is always a nice property)
An online algorithm (in which we can handle queries as they come) would be to just binary search in the sorted segments for the last l,r such that p \leq r. Then we can just compute the answer.
Complexity: O(n \log(n) + m \log(n)) per test case, sample solution 20443909
5 Likes
https://www.codechef.com/viewsolution/20443131
Getting TLE in this for larger input.Any suggestions on how to improve it?
See my edited answer. Your solution is quadratic, but it shouldn’t take too much work to make it into the offline algorithm I described.
Nice Explanation.