Problem Link
Author: Aleksa Plavsic
Tester: Mark Mikhno
Editorialist: Bhuvnesh Jain
Difficulty
HARD
Prerequisites
Dynamic Programming, Prefix sums
Problem
You are given an array A with N elements. You need to find the number of ways to partition it into smaller parts such that each part is a safe partition i.e. the size of each partition lies between the minimum element and maximum element in the partiton. We need to find the required answer modulo 1000000007.
Explanation
We will use dynamic programming to solve this problem. Let us define dp[i] as the number of partition we can get if we consider the array from [1, i]. The transitions are staright forward and can be seen through this pseudo-code below:
dp[0] = 0
for i in [1, n]:
mx = mn = a[i]
for j in [i, 1]:
mx = max(mx, a[j])
mn = min(mn, a[j])
len = j - i + 1
if (mn <= len and len <= mx):
dp[i] = (dp[i] + dp[j-1]) % mod
print dp[n]
To optimise the above dynamic programming is not straight forward, like no optimisation techniques mentioned here. So, let us consider the 2 conditions of safe partition separately:
- min(S) <= length(S)
- length(S) <= max(S)
For the first condition note that if we append an element to a subarray, the length will increase but the minimum will either remain same or will decrease. This means if this condition is satisfied for a subarray, it will be satisfied even when an element is added to it, i.e. the condition is monotonic. So, for a given index i we can find the first maximum index to the left of it, so which the condition holds true. Mathematically,
If for index j < i, min(A[j...i]) <= (i - j +1), then the first condition is satisfied for all k from 1 to j. Finding the maximum j for each such index i can be done using deques in O(N) by maintaining a growing deque or by using binary search and range minimum query in O(N \log{N}). Below is the pseudo code for both the approaches:
Approach 1
# Complexity: O(N) using deques.
S = deque()
for i in [1..N]:
while !S.empty() and A[i] <= A[S.back()]:
A.pop_back()
S.push_back(i)
# We want to find maximum j for every i, so try to left shift
# the index if possible.
# min(A[j..i]) <= i - j + 1 is same as
# j <= i - min(A[j..i]) + 1
# Also, for every index i, S.front() is valid answer for j, as
# we maintain an increasing order of elements in deque and the
# condition is monotonic.
# Joining with above condition, the answer is will be
# min(S.front, i - A[S.front] + 1)
while S.size() >= 2:
# get first 2 elements.
x = S.front
S.pop_front()
y = S.front
if min(x, i - A[x] + 1) > min(y, i - A[y] + 1):
# We can't left shift for index j.
# So, x is the optimal answer.
S.push_front(x)
break
index_left[i] = min(S.front, i - A[S.front] + 1)
if index_left[i] < 0:
index_left[i] = 0
Approach 2
Build RMQ in O(N logN)
for i in [1..N];
l, r = 1, i-1
while l <= r:
m = (l + r) / 2
if rmq[i][m] <= i - m + 1:
l = m
else:
r = m - 1
if rmq[i][l] <= i - l + 1:
index_left[i] = l
else:
index_left[i] = 0
Now, let us look at second condition. For this, the monotonicity doesn’t apply when we try to append an element to a subarray which already obeys the condition. So, let us try to precompute the subarrays where element at index i will be maximum in such subarray. This is a common problem by the name of stock span. For details, you can refer here. The complexity of this part is O(N).
From now on, let us denote \text{L_max}[i] as the largest j < i such that A[j] > A[i]. Similarly, let us denote \text{R_max}[i] as the smallest j > i such that A[j] >= A[i].
With above information, we know subarrays which obey the first condition and subarrays where given element will be maximum. We just need to try and combine above 2 parts efficiently to come up with a solution to obtain dp[i].
To obtain dp[i], we use the logic of adding all subarrays which satisfy the first condition and then subtract the ones which violate the second condition. For this the idea is to keeping a running prefix sum of dp[i] to calculate the first part efficiently, i.e. sum of all dp[j] where j < i and such subarrays obey the first condition.
For the removal of bad part, we assume the bad part is already removed from dp[i] when we reach index i. This is done by subtracting the contribution of dp[i] for all j > i where A[k...j] obeys first condition but fails to obey second condition and k lies in the range where i is the maximum element. For futher details, I recommend going through the commented code itself where complexity analysis is also done with explanation at each step.
Time Complexity
O(N \log{N})
Space Complexity
O(N)
SOLUTIONS:
Author’s commented solution can be found here.
Tester’s solution can be found here.