ANURRZ - Editorial

editorial
, , , ,
1

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
2

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.

3

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

4

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

5

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.

6

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!

7

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
8

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])

9

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

10

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 ??

11

that was a typo. fixed!

12

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 ?

13

it should be

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

not

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

for reading u[]

14

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]