# SAFPAR - Editorial

Practice

Contest

Author: Aleksa Plavsic

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain

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:

1. min(S) <= length(S)
2. 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.

O(N \log{N})

O(N)

# SOLUTIONS:

Author’s commented solution can be found here.

Tester’s solution can be found here.