LIGHT - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY

MEDIUM

PREREQUISITES

Binary Search, Greedy Algorithm, Geometry

PROBLEM

You are given several light sources along a road (road is x-axis). 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 EXPLANATION

A 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.

EXPLANATION

If 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 x lies within the line segment. Now, if the line segment from la to x was of positive length, then we know that there is some (or all) of the line segment between la to x which belongs to the region L to R.

If cnt for that segment was 0, then that segment was not lit and we return “Invalid”.

Otherwise we update the cnt and la for the next iteration.

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 SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

2 Likes

This problem should be solvable by doing one sweep (without the binary search) since we just need to follow the upper envelope of the lights and locate the lowest point within the (L, R) segment; but I couldn’t be bothered to do it (it is definitely easier to get wrong than the binary search approach).

Perhaps some of the others who solved it did it in this way though. I guess it could be up to 30 times faster in some cases.

1 Like

The number of points to consider for the sweep will be much more than O(N) in this case. Wouldn’t it?

Possibly; I had thought I had a way to reduce the candidate low-points to O(n) in O(n log n), but maybe it doesn’t work. I’ll have to think about it some more to work out the details. Basic idea is that on an upward slanting segment, only the first intersection point matters, while on a downward slanting segment, only the last one does. However to actually do the sweep we need more than just those points (at first blush).

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.

2 Likes

Cool! This isn’t exactly what I was thinking of – it’s better IMO. Thanks for pointing it out!

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).

@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)

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!

I did the same but unfortunately, WA :frowning:

@kriateive how can I find which segments of the upper curve will intersect with the new appended light line in o(1)?

I have given link to my solution. you may compare. Its AC :slight_smile:

@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?

is this approach enough to pass the time limit

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)

very nice editorial