PROBLEM LINK:
Author: Bogdan Ciobanu
Tester: Jingbo Shang
Editorialist: Hanlin Ren
DIFFICULTY:
Hard
PREREQUISITES:
dynamic programming, persistent convex hull/convex hull on tree
PROBLEM:
Given a histogram array h[1\sim N], find the largest staircase in the histogram, that has at most K height changes. The staircase may start and end at any point, and must be non-increasing or non-decreasing. You may decrease the height of some histogram so it forms a staircase.
Formally, you should find 1\le l\le r\le N and array a[l\sim r], such that :
- Either a[i]\le a[i+1] for any l\le i < r, or a[i]\ge a[i+1] for any l\le i < r;
- For any l\le i\le r, a[i]\le h[i];
- The number of i(l\le i < r)'s that a[i]\ne a[i+1] is at most K,
and maximize a[l]+a[l+1]+\dots+a[r]=\sum_{i=l}^ra[i].
SOME CONVENTIONS
I donât want to repeat them in Quick Explanation and detailed Explanation, so Iâll list them here.
- Weâll only consider leftwards(non-decreasing) staircases, since rightward ones can be obtained by reversing the array.
- Let f_i be the first index to the left of i that has height < h_i. That is, f_i is the greatest w such that w < i and h_w < h_i. If such w doesnât exist then f_i=0.
- Also let g_i be the smallest index w such that w > i and h_w < h_i. If such w doesnât exist then g_i=N+1.
QUICK EXPLANATION:
Dynamic Programming. Let dp[x][u] be the maximum area of some staircase that ends at h_u(i.e., a[*\sim u]) and has x changes in height. Then
where v is among \{f_u,f_{f_u},f_{f_{f_u}},\dots\}. The answer is \max_u(dp[K][u]+h_u(g_u-u-1).
Let u's father be f_u, then all numbers form a tree rooted at 0. When solving dp[x][u], we need to iterate u's all ancestors. We can maintain a persistent convex hull that supports insertion to store these ancestors. The time complexity improves to O(NK\log N).
EXPLANATION:
subtask 1
In this subtask, K=0 so we donât allow any changes of height. The solution is to enumerate the height of staircase: it must be the height of some histogram. Suppose the height is h_x and the staircase contains x.
Letâs enumerate x, and we greedily extend the staircase as far as possible. We can extend the staircase to [f_x+1,g_x-1]. This is a staircase with height h_x and width g_x-f_x-1. See the image below.
Thus, our algorithm is: first we compute f and g. Then we enumerate x and compute h_x(g_x-f_x-1). The maximum number among these numbers will be the answer. The algorithm for computing f and g will be given later. The overall complexity is O(N).
Subtask 2
This problem can be solved by dynamic programming. Let dp[x][u] be the maximum area of some staircase that ends at h_u(h denotes the histogram) and has x changes in height; also we require that the last rectangle must have height h_u. To compute dp[x][u], we can enumerate the second last rectangleâs height, say, h_v. To maximize the area of staircase, the last rectangle(which is the highest) should extend as far as possible, so it can have width u-f_u, as shown in rectangle (b) below; the second last rectangle has additional width f_u-v(rectangle (a) below), plus the part in dp[x-1][v]. Thus we can write the dp formula:
where 1\le v < u and h_v is the minimum among h_v,h_{v+1},\dots,h_u. Starting cases are dp[0][u]=h_u\cdot (u-f_u).
We can easily compute dp in O(N^2K) time. After that, letâs enumerate the height of last staircase, say h_i, then our staircase can extend to g_i-1. So, to obtain the final answer, we compute the maximum number among all \left(dp[K][u]+h_u(g_u-u-1)\right)'s, where u is enumerated from 1 to N.
The bottleneck is to compute dp, which costs O(N^2K).
Subtask 3
A tree structure
Recall the constraints for v: 1\le v< u and h_v is the minimum among h_v,h_{v+1},\dots,h_u. This constraint essentially means that v=h_{h_{\dots u}}. In other words, if we link and edge u\to h_u for every u, then weâll get a tree, and when we enumerate v, we enumerate all u's ancestors: h_u,h_{h_u},\dots. This problem becomes a dp problem on tree.
Persistent convex hull
We can write the dp formula as:
where C_u=h_u\cdot (u-f_u),K[v]=h_v and B[v]=dp[x-1][v]-h_vv. That means, when computing dp[x][u], we actually do the following things:
- For every ancestor v of u, add a line y=K[v]x+B[v];
- Then find the maximum K[v]f_u+B[v] among all lines.
We can build the upper hull of these lines. In the image below, our upper hull is the thick red polyline. We only maintain the polyline, so some lines that can never be maximum are thrown(such as the blue line). When we need to find the maximum, we draw a line perpendicular to x axis(the dashed red line), and calculate its intersection with the polyline.
However the hull is different for different u. What should we do? Here comes the Persistent convex hull trick. Iâll talk about the version here. This trick works when youâre dealing with a tree and childâs K(slope) is always not smaller than parentâs K.
We use a stack(itâs actually a vector, youâll see why later) to store the lines in the polyline. The top element has the largest slope, and the slope goes smaller downwards. In the example below, the stack(before inserting line 10) contains lines \{1,3,4,7,9\} from bottom to top. Then line 10 comes and we need to update the stack.
To update the stack, we find the segment that intersects with line 10. Itâs line 4 in this case. Since line 10 has the biggest slope, it must be the last element of polyline. So we pop all elements before 4, and push 10. Now the stack becomes \{1,3,4,10\} from bottom to top. This demonstrates how to insert a new line into our data structure.
However there is a problem: we need to recover the stack. We canât pop all elements since an element can be popped several times, and the complexity may become O(N^2). When inserting a new line, we need to do binary search to find the segment it intersects. We record whom the new line replaced for restoring. We also need to maintain an extra variable len denoting the length of stack, so popping lots of elements is O(1): just modify the length. To recover the stack, we replace the new line by what it replaced before, and recover the length.
Consider the example above. Before inserting line 10, len=5 and stack=\{1,3,4,7,9\}. After inserting line 10, len=4 and stack=\{1,3,4,10,9\}(note the element 9: itâs actually not in the stack!). When we want to restore the stack, just set len=5 and replace 10 by 7.
This also explains why we would use a vector rather than a stack.(Of course you can use an array 
With the simple âpersistent convex hullâ, we can solve this problem in O(NK\log N):
dfs(x,u)
Compute dp[x][u]
insert line (K[u],B[u]) into the stack
for v is u's son:
dfs(x,v)
restore the stack
//main
for x = 1..k do:
dfs(x,root)
The codeforces comment above is a good explanation about this method. You can also see authorâs solution for better understanding.
Computing f and g
The last problem is, how to compute f and g? Since they are similar, we only talk about the algorithm for f.
Suppose we already know f_1,f_2,\dots,f_{i-1}, and weâre going to compute f_i. Let w=f_i, then h_w must be the minimum among h[w\sim i]. That means, h[w] is the minimum among h[w\sim (i-1)], so w is an ancestor of i-1(possibly w=i-1). Letâs find the lowest ancestor of i-1 whose h is less than h_i. Then this ancestor is f_i. Pseudocode:
for i = 1..N do
f[i] = i-1
while h[f[i]] >= h[i] and f[i] >= 1
f[i] = f[f[i]]
How efficient is this algorithm? A careful analysis actually tells us that this algorithm is O(N): let L_u be the number of time the statement f[i] = f[f[i]] is executed when i=u, then L_i=dep_{i-1}-dep_i+1, where dep_i is the depth of i in the tree. The time complexity for the algorithm is O(N)+\sum_{i=1}^NL_i=O(N)+dep_0-dep_N+N=O(N).
ALTERNATIVE SOLUTION:
If your solution is different with ours, feel free to leave a comment.
AUTHORâS AND TESTERâS SOLUTIONS:
Authorâs solution can be found here.
Testerâs solution can be found here. (Note: this is a brute force).
Editorialistâs solution can be found here.
RELATED PROBLEMS:
-
CEOI 2009 Harbingers for âpersistent convex hullâ trick.