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