WEASELSC - Editorial

PROBLEM LINK:

Practice

Contest

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

dp[x][u]=\max_vh_u\cdot (u-f_u)+h_v\cdot (f_u-v)+dp[x-1][v],

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.

demo

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:

dp[x][u]=\max_vh_u\cdot (u-f_u)+h_v\cdot (f_u-v)+dp[x-1][v],

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

Image

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:

dp[x][u]=C_u+\max_vK[v]f_u+B[v],

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:

  1. For every ancestor v of u, add a line y=K[v]x+B[v];
  2. 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.

upper hull

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.

inserting new lines

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 :slight_smile:

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:

4 Likes

I was trying to solve this problem for subtask 1(k=0) only .can any tell me what wrong with my approach.
my approach.

if all the elements are non-zero then the answer would minimum_number*size_of_the_array

else
check all the position of zero and make subsequence b/w zero_position
eg-8 0 10 12
subsequence -{8} && {10,12}

and then compare the area of the susbsequence array to find out the max area.

code link

The thing is, you can ignore the elements which are 0, and even reduce height to 0 and ignore it. Check out comments of problem.

Eg-

1 1 1 1 50 has maximum ans 50, not 1. You can make all the 4 1s as “0” and ignore them, leaving with only 1 block of area 50.

Even I tried for subtask 1. I used segment tree to update the weight of the vertices. have a look at my code here

1 Like

got it.thanks

My AC solution used common convex hull trick without any persistence (I used the same dp as author).

We will calculate dp from left to right. Let’s maintain stack of indexes that if some indexes i < j are in the stack their heights are linked by this condition: h[i] < h[j]. As you can see, we have there increasing stack, that for index u contains only those indexes v that could update dp[x][u] - actually it is stack with all ‘parents’ in author’s tree.

It is easy to see that this stack can be updated simply:

while (h[stack.peek()] \ge h[u]) stack.pop()

For each index it will be pushed one time into the stack and popped from it one time, so total complexity for this part is O(N).

So now we can take f_u as stack.peek() in O(1) without any tree (yes, you can say, that I simply used my own stack instead of recursion). But what is more important - we don’t need persistent convex hull trick anymore.

For subtask 2 (N \le 3000) we simply can iterate over all vertices in stack in O(N^2K) complexity.

For subtask 3 we just replace stack of indexes with stack of lines in convex hull trick:

  • when we insert new line, we make the same actions as usual - pop lines while they are dominated by inserted line
  • we can see that k_i coefficient for line in stack, associated with index i is actually h[i]. So for every index u we need just pop lines while their k \ge h[u].

About calculating left and right limits for index u: you can see that top element in stack is actually left limit of h[u], so right limit can be found the same way with reverse iteration.

There are link to main part of my solution (i removed huge template): Code on pastebin

2 Likes
//