PROBLEM LINK:
Author: Alei Reyes
Primary Tester: Hussain Kara Fallah
Secondary Tester: Kacper Walentynowicz
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Medium
PREREQUISITES:
Basic Geometry , Convex Hull
PROBLEM:
Given N towers on the X axis. Each tower can be imagined a straight vertical segment. Given the position of each tower on the axis and its height (segment length). Towers are given in ascending order of positions, and no 2 towers share the same height.
You have to determine for each tower the rightmost tower with shorter height such that drawing a segment between their tops doesn’t intersect any other tower. Intersection with towers exactly at its top is ok. (this case is covered in the sample please check the image in problem description).
N ≤ 500000
EXPLANATION:
This problem is similar to finding the upper convex hull of a set of points, but forcing each tower to be able to shoot only shorter towers made it a little bit tricky.
An important observation here. Consider the ith tower and let’s find the smallest j (j>i) such that Hj > Hi. (The closest tower to the ith which is taller than it). It’s obvious that we can’t draw a segment from the ith to any other shorter tower after the jth one without intersecting with it. (Proof is easy).
Let’s process the towers one by one from the rightmost one to the leftmost one. We will stack our towers into piles, each one having towers sorted in decreasing order of height from left to right.
Suppose we are processing a certain tower and the last added tower was higher, so the answer of our current tower would be -1 and we will make a new pile and insert it into.
Since each pile will have towers sorted in height from left to right, If we consider having towers forming only one pile, then the segments representing answers of towers in this pile must form the upper convex hull of it. (Check these examples of a pile):
Now back to our problem, let’s consider this case. Points A,B,C must be added into the same pile.
Currently, ans(A) = -1 , ans(B) = A , ans© = B
If our tower was higher than the last added one (and we had only one pile), we should process the pile, and evaluate our current tower with the last added two towers to ensure that we are maintaining the convex hull of this pile, and this can be done easily by checking the cross product of 2 vectors and behaving according to the sign.
Let’s insert point D, as you can see the vectors (D->C,C->B) make a counter clockwise turn, so we must pop point C from our pile to maintain convexity.
The trick here is when we have a tower to process and we have more than one pile (with the highest tower of each shorter than the processed tower), then we should drop the nearest pile as long as we have more than one. After that, we will be left with only one pile and we insert our tower there. Because the head of each pile will have no tower to the left higher than it, otherwise we would insert it in the same pile (or maybe drop the whole pile). So since our current tower is higher than the shot one and the shot one has no higher tower to the left. We can shoot it without intersecting with any other tower.
After processing points {A,B,C,D,E,F} we had two piles {A,B,C,D},{E,F}. When we came to process point G, you can see that we can shoot the head of each pile. The purpose of dropping piles can be shown in this sample. Because point E cannot be shot from point G.
We insert point G into the pile of D and drop {E,F}
This solution runs in O(N), each tower is inserted once, and may be popped once and for all.