PROBLEM LINK:DIFFICULTYMEDIUM PREREQUISITESBinary Search, Greedy Algorithm, Geometry PROBLEMYou are given several light sources along a road (road is xaxis). Each light source casts isosceles triangles with their base over the road. We wish to find the highest height at which we can fly a plane from x = L to x = R such that line segment from (L, h) to (R, h) is completely within the light  that is, within one or more of the isosceles triangles cast by the light sources. QUICK EXPLANATIONA useful technique while solving any problem is to identify that the solution w.r.t. one of the variables is monotonic. In this problem there is some height H, above which we cannot find a segment (L, h) to (R, h) satisfying the constraint. But, below this H, for all h, (L, h) to (R, h) will always be in light. Thus, we can perform a binary search on h to find the largest height which is valid. EXPLANATIONIf the segment from (L, h) to (R, h) is completely within the light triangles, we call h valid. To check if h is valid we can do the following function verify(h) Let A be a list of items, where item is a pair of numbers for each source of light, s if height[s] < h then ignore this source else base = ((Y[s]  h) * tan Z[s]) lx = X[s]  base rx = X[s] + base A.push(lx, 1) A.push(rx, 1) A.push(L, 0) A.push(R, 0) So, for each light source, we find the intersection of the light source with a line at height h. We store these intersection points in a list along with "1" for the points at which a light source is added, and "1" for the points at which a light source is ended. Note that we also add L and R to A, but without any delta (that is their pair value is 0). We know that now the number of light sources illuminating each segment in A are constant. By adding L and R to A, we have ensured that we consider the line segments that start / end at L (or R) separately. The following snippet shows the complete verify procedure. function verify(h) Let A be a list of items, where item is a pair of numbers for each source of light, s if height[s] < h then ignore this source else base = ((Y[s]  h) * tan Z[s]) lx = X[s]  base rx = X[s] + base A.push(lx, 1) A.push(rx, 1) A.push(L, 0) A.push(R, 0) sort A Let cnt = 0 be number of active sources of light for the next segment Let la = infinity be the endpoint of the last seen segment for i = 0 to A.size Let x = A[i].first Let del = A[i].second if x > L and x <= R and x > la and cnt == 0 then return "Invalid" la = x cnt += del return "Valid" We sort A to consider each line segment one by one. This is equivalent to a line sweep algorithm from left to right touching all the intersection points (that we stored in A). For each segment we see if If Otherwise we update the If we find that no such dark segment exists, we return "Valid". Hence we can call verify from within a binary search to find the largest possible h. You need to be careful about precision errors and angle format conversions (degree / radians) for the respective language's math library. SETTERS SOLUTIONCan be found here TESTERS SOLUTIONCan be found here
This question is marked "community wiki".
asked 11 Sep '12, 15:27

Possibly another way is to keep track of the upper curve formed after adding each light iteratively. The method is fast as it can be proved to have only O(n) points (actually 3*n max) on the upper curve. Store the curve in a tree to search for the them in a fast way. I solved using this in the contest and my code is here but it is not well documented. answered 12 Sep '12, 03:13
Cool! This isn't exactly what I was thinking of  it's better IMO. Thanks for pointing it out!
(12 Sep '12, 07:33)
Are you sure the whole algorithm is better than O(n^2)?? The upper curve can change a lot (up to O(n) points) when you add one light. Consider that it could be possible that you add O(n) lights and they intersect the upper curve in O(n) points per light, thus at least O(n^2). [And still at the end you finish with O(n) points).
(12 Sep '12, 13:00)
@roypalacios No the upper curve cannot at any point of time contain more than 3*n points. It may be bit difficult to see but take it this way. Sort all the lights in decreasing angle of spread. now whenever you put a light with less angle in a curve formed by all lights of angle greater than this light you wont be getting more than 3 points. As the order of the lights doesn't matter in generating the upper curve, you would get the same no of points. With this sorted form, you can search the segment above which the light and append this light. The net complexity is O(n logn)
(12 Sep '12, 14:03)
Ahhhh, that is clever!, I was not sorting by angle so I couldn't track the upper curve better than O(n^2). Thank you!
(12 Sep '12, 14:53)
I did the same but unfortunately, WA :(
(12 Sep '12, 22:57)
@kriateive how can I find which segments of the upper curve will intersect with the new appended light line in o(1)?
(13 Sep '12, 08:36)
I have given link to my solution. you may compare. Its AC :)
(13 Sep '12, 09:28)
@kriateive well?it is not easy for me to understeand your code. is it o(1) or o(lgn) to find the intersection points in your code?
(13 Sep '12, 12:14)
O(logn). We have n light sources and searching each time with O(logn) has complexity of O(n logn). Considering the rebuilding of the upper curve, each segment is inserted once and removed once. Hence an amortized analysis leads to just O(n) overall complexity for rebuilding the curve. Hence, Final Complexity is O(n logn)
(16 Sep '12, 12:37)
showing 5 of 9
show all

is this approach enough to pass the time limit