PREREQUISTITES
Basic Math and Geometry, Binary Search
PROBLEM
There are N line segments and i'th segment connects points (a_i,0) and (0, a_i). You are also given Q queries and in each query given a point (x_i, y_i). For each query find the number of line segments present under this point and if the point already lies upon a line segment then print -1.
EXPLANATION
Equation of i'th line is x + y - a_i = 0, so for a point P(x_p, y_p) there are 3 possible scenarios,
if x_p+y_p-a_i < 0, then P is under this line.
if x_p+y_p-a_i = 0, then P is upon this line.
if x_p+y_p-a_i > 0, then P is above this line.
So we can use binary search over the answer, let’s see how.
Now if you currently checking i'th segment and find that P is lying above the line then you have to break more line segment to allow Chef to reach (0, 0), so you can continue the searching upon upper half of the binary search. Otherwise, if P lie under the line then you are going to break more segments which is not possible as you can’t break segments which are above you, so you can continue the searching upon the lower half of the binary search. Lastly, if you find that P lies on a line in any step of binary search then you simply find that it’s not possible to reach (0, 0).
The time complexity is \mathcal{O}(Q\log{}N).
SOLUTIONS
C++ solution can be found here
Java solution can be found here
Python solution can be found here
Both are same but why does the vector one give WA?
@souradeep1999 please look into this. There is no difference in both solutions. It would be nice if someone can help me figure out the issue ( no matter how trivial it is )
It will give TLE.
Because its time complexity o(n**q);
Use Binary search instead for getting time complexity O(logn*q);
Here is my code with binary Search : CodeChef: Practical coding for everyone
Hope this helps. Thanks !!!
can anyone tell that what is the time complexity of find() function in vector? is it not O(logn)?
Because when i used the find function of vector I got TLE but when I used find function of set it got accepted.