ANURRZ - Editorial

PROBLEM LINK:

Practice
Contest

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 Ai > Bi 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 > 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[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])).

SOLUTIONS:

Setter’s solution
Tester’s solution

3 Likes

I suggest the time limit of this question should have been a bit higher. It took me quite a lot of TLEs and fast i/o to get the code (with exact same algo) accepted.

Using % mod is bad practice, use -= mod and you will get it okay in decent time.

Very strict time limit my solution of same worst case complexity could not get accepted.

Yeah,the time limit is quite strict. I was getting TLE during contest because I used a long long matrix for DP. My bad, I guess.

But still, I think it would’ve been better to have just 10 test cases per file instead of 100.

I would like to say that the time limit was pretty strict as well. Especially for Python, it takes my code 1 second to run 1 test case with n = 1000. Doing 100 of those in time was pretty much out of the question. The algorithm is the same as that in the question. Granted, with a few modifications I could probably have brought that time a little lower but getting an AC was impossible. Such strict time limits, in my opinion should be reserved for LONG challenges and not COOK-OFFs, but to each his own. Technically, this question can require O(10 ^ 8) operations. O(t * n * n)

I also have a request, if you guys can, look into adding PyPy as an additional language for submissions. I love to code in python but as it is right now it is a major disadvantage to do so. (if you remember the problem with ONEKING in JAN15)

My exact same code for this problem runs 6 times faster in PyPy than it does in Python.

Python - 3.2 seconds for 3 test cases

PyPy - 0.5 seconds for 3 test cases

Please look into it.

Thanks!

Why test cases are not shown as in codeforces/topcoder when we solve the problem in practice mode ? It will be easier to debug the code if it is shown.

Thanks!

6 Likes

Do we have to visit each index in array A exactly once or it can be any number of times? If exactly once, then should the inner loop of computing dp[i][j] be

for i=1 to N:
   for j=1 to min(B[i],i):
      dp[i][j] = prefix[j-1]

This will effectively mean that dp[i][j] = 0 if j > min(i,B[i])

Why is dp[0][0] = 1? Shouldn’t it be 0?

won’t the recurrence be
dp[i][j]=dp[i-1][1]+dp[i-1][2]… + dp[i-1][j-1];

since x can be between 1 & (j-1).

@darkshadows can u plz clarify ??

that was a typo. fixed!

I didn’t understand why dp[0][0]=0 and
for j=N to 0:
prefix[i] = prefix[i+1] + dp[i][j].
Can anybody explain ?

it should be

for(int i=1; i<=n; i++)

not

for(int i=0; i<n; i++)

for reading u[]

for j=N to 0:
prefix[i] = prefix[i+1] + dp[i][j]
should be
for j=N to 0:
prefix[j] = prefix[j+1] + dp[i][j]

//