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 Ai > Bi for any valid i.
Count how many different array A can be formed.
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.
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 > Bi, 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, BN)
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(N3).
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 = 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])).