### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Minako Kojima

**Editorialist:** Lalit Kundu

### DIFFICULTY:

MEDIUM

### PRE-REQUISITES:

Dynamic Programming

### PROBLEM:

You intially have two arrays **A** and **B** of **N** elements where each element is 0 in array **A**. For each **i = 1 to N**, we can choose any **j** between **i** and **N**(both inclusive) and increase all elements in array **A** from index **i** to **j**(both inclusive) by 1. An array **A** after these operations in discarded if A_{i} > B_{i} for any valid **i**.

Count how many different array **A** can be formed.

### QUICK EXPLANATION:

Keep a state of **dp(i,j)** denoting the number of different arrays of size **i** that can formed and number **j** is present at **i**’th position in such arrays.

### EXPLANATION:

In such kind of problems first thinking should be dynamic programming. Let’s try to find answer for first **i** indexes. Can we relate the answer for **i** directly to answer for **i-1**. No! We need some additional information. Why don’t we keep two states **i** and **j** denoting the number of different arrays of size **i** that can formed and number **j** is present at **i**’th position in such arrays. Basically **dp(i, j)** denotes number of arrays of size **i** such that **j** intervals end at **i**’th position. Note that for **j** > **B _{i}**,

**dp[i][j]**would be zero, because it’s not a valid array. Our answer will be

**dp(N, 1) + dp(N, 2) + … + dp(N, B**

_{N})Now, let’s try to form recurrences. What we should be thinking is for **dp(i, j)** which all are valid **x** such that **dp(i-1, x)** can be added to **dp(i, j)** ie. what valid numbers can come at position **i-1** if **j** is present at index **i**?

Now, an interesting observation is that **x** can be any value greater than equal to **j-1**. It can be thought as: suppose **x** intervals were ending a index **i-1**, then we can choose to extend any number of them to index **i** to get any sum between 1 and **x + 1**(note that one interval starts and ends at **i**). So, we get that **x** can be any number greater than or equal to **j-1**.

So, here is our recurrence:

```
dp(i, j) = dp(i-1, N) + dp(i-1, N-1) + dp(i-1, N-2) ... dp(i-1, j-1)
```

So, if we calculate each state **dp(i, j)** in **O(N)**, our total complexity will be **O(N ^{3})**.

But we can notice that

**dp(i, j)**depends on a continuous sum in one dimensional array of

**dp(i-1)**.

So, if we calculate prefix sum array:

**prefix[j]**stores the sum

**dp(i-1, j) + dp(i-1, j+1) … dp(i-1, N)**. So,

**prefix[j] = prefix[j+1] + dp[i-1][j]**. We can calculate this prefix sum array in

**O(N)**.

See following psuedo code for more clarity:

```
dp[0][0] = 1
//intialise prefix sum for i=0
for j=1 to N:
prefix[j] = 1
for i=1 to N:
for j=1 to B[i]:
dp[i][j] = prefix[j-1]
for j=N to 0:
prefix[i] = prefix[i+1] + dp[i][j]
ans=0
for i=1 to B[N]:
ans += dp[N][i]
print ans
```

Dont’ forget to use modulo operations!.

Complexity: **O(N * MAX(B[i]))**.