PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Alei Reyes
Tester: Aleksa Plavsic
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Previous and Next greater element, Observations.
PROBLEM:
Given heights H of N hills, we can place reservoirs on any number of hill, to provide water. Water flows from the reservoir in the chosen direction until reaching a hill with height strictly greater than the height of the hill with the reservoir. Find the minimum number of reservoir required to supply water to all N
OBSERVATION
- If first or the last hill has the maximum height, We can just place a reservoir at that hill, oriented toward the other hill, covering all hills using 1 reservoir itself.
- It can be proven that in the optimal placement of reservoir, there doesn’t exist two positions i, j given i < j containing reservoirs such that reservoir at position i is oriented rightwards while reservoir at position j is oriented toward left.
- There exist two consecutive positions i and i+1 such that both have a reservoir, and both are oriented in opposite directions.
EXPLANATION
This problem is just observations, so we shall discuss them first. Handle the case were maximum element occur at either end separately.
Observation: In optimal placement of reservoir, there doesn’t exist two positions i, j given i < j containing reservoirs such that reservoir at position i is oriented rightwards while reservoir at position j is oriented toward left.
Proof: Let’s assume that in optimal placement and orientation of reservoirs, there exist two positions i and j such that i < j, there is reservoir at both positions, the reservoir at position i is oriented toward the right while reservoir at position j is oriented toward left.
The final arrangement will look something like this. …LR…LR… (Notice reservoirs in bold).
Since all heights are distinct, Either H[i] < H[j] or H[i] > H[j]. Also, No hill in range (i, j) have height Greater than max(H[i], H[j]) otherwise water flow cannot reach that hill. Now, If H[i] > H[j], The water flow from reservir shall cover all hills including hill j implying that the reservoir at position j is useless, and can be removed. Similar explanation follows if H[i] < H[j].
This contradicts our assumption that this arrangement was optimal.
Hence, All reservoirs from left up to a certain reservoir at position x are oriented towards left, while all reservoirs after position are oriented right.
Now, the Optimal arrangement looks like …L…L…R…R.
But, If water flow is to reach all hills, there should be no gap between Rightmost left-oriented reservoir and Leftmost right-oriented reservoir otherwise no water can flow toward the hills in the gap between those two reservoirs.
The last observation is, Suppose we have placed a left-oriented reservoir at position x. Then the reservoir immediately to the left which should have a reservoir should be the nearest hill with strictly higher height that hill at position x on the same side.
The reason is, suppose y is the nearest position, y < x such that H[y] > H[x], If we place at any position z < y, water can never reach position y since all resrvoir to left of position x are oriented left. If any position z > y is chosen, water will never reach hill y, since H[z] < H[x] < H[y] holds for all z satisfying y < z < x. So, we place the next reservoir at position y.
Now, we can repeat this procedure os placing reservoir at the nearest position to the left which has strictly higher height than current hill height, till water reach hill 1 too.
The similar procedure can be applied toward right-oriented reservoirs.
Now, we know how to solve the problem if we know the position x, the position of Rightmost Left-oriented reservoir. Fortunately, we can try all positions from start to end if we can count the minimum number of reservoirs required at left and right side of x required to supply water at all hills in O(1). We can do this by calculating in advance, L[i] representing Number of left-oriented reservoirs required to supply water in range [1, i] and R[i] representing minimum number of right-oriented reservoirs to supply water to hills in range [i, N].
This can be calculated by finding Next greater element as well as previous greater element, which can be done using a stack. It’s details you can find here.
Final answer is min(2+L[PGE[i]]+R[NGE[i+1]]) for all i, where PGE means Previous greater element to left of H[i] while NGE[i] means next greater element to right of H[i].
With this, we depart until you open another editorial of mine.
Editorialist’s suggestion: There also exist a divide and conquer type solution, which editorialist initially used to solve the task. It picked hill of maximum height hill to place reservoir, try both orientations and print the minimum of both. It has O(N*logN) complexity, due to calls to Segment tree.
Time Complexity
Time complexity is O(N) since we just iterate over an array and use stack operations.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed.