STDYTAB - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Mahbubul Hasan and Sunny Aggarwal
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

DIFFICULTY:

Easy

PREREQUISITES:

Combinatorics, DP

PROBLEM:

You have to fill a N x M matrix with non negative numbers such that the sum of numbers at row i (2 \le i \le N) is greater than or equal to the sum of numbers in row i - 1.

SHORT EXPLANATION

Suppose we want to fill one row (which has M elements) such that the sum of the numbers is X. The number of ways to fill this row can be obtained using a standard combinatorics formulae: \binom{X + M - 1}{M - 1}.
We can solve using dp: let solve(i, x) denote the number of ways to fill the matrix such that the matrix is steady and the sum of the i^{th} row is x. We can easily solve this using the recurrance:

solve(i, x) = solve(i + 1, x) * \binom{x + m - 1}{m - 1} + solve(i, x + 1)

EXPLANATION:

Suppose we start at row 1. Say, we fill this row such that the sum is x. Now when we move on to the second row, we must make sure that the sum of the second row is greater than or equal to x. So, besides the row itself, we must also keep track of the minimum sum of the row.

Let solve(i, x) be the number of ways to fill the matrix from i^{th} row to the N^{th} row such that the matrix is steady and the sum of i^{th} row is at least x. There are now two ways to proceed

  1. We make the sum of current row x: We need to calculate in how many ways we can make the sum of the current row x. There are M elements in this rowee. So we need to find the number of ways in which we can choose M numbers such that they sum up to x. This can be calculated using the formula \binom{X + M - 1}{M - 1}. See TODO for an explanation.

  2. We don’t make the sum of current row x: In this case we can make the sum of the row atleast x + 1.

Putting this together we have the following solution

MOD = 1000000000    
Preprocess array C such that C[n][k] = n choose k mod MOD    
Solve(i, x):    
    See if we have already calculated the answer for this input and if so return the value    
    Edge cases:    
    if x > M return 0 // Sum of a row can't be greater than M    
    if i == N + 1 return 1    
    ret = (Solve(i + 1, x) * C[x + m - 1][m - 1] + Solve(i, x + 1)) mod MOD    
Answer is Solve(1, 0)

Time Complexity:

We calculate each state only once. For each state we take a constant amount of time. We know that i can take values till N while x can take values till M. So, the total amount of time taken for solve will be O(NM).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

3 Likes
2

whatever i wrote in this question i might not be able to explain it to myself later. :stuck_out_tongue:

7 Likes
3

I thought I was the only one who was thinking this. :smiley:

2 Likes
4

Rather we can also do it the reverse way by starting with the sum of no.s of nth column to be <=“M”.
just the thing is as n and m increase the C(m+n-1,n-1) becomes too large to calculate…
so we need some smart methods to calculate them…
I haven’t come across such methods where modulo no is not a prime (10^9) and not (10^9+7)…

5

can anyone help me why i’m getting tle. I used matrix exponential to calculate the answer and the time complexity is O(MMlog(N)).The link to the problem is http://www.codechef.com/viewsolution/7215565

6

You could have used nCr = ((n-1)C(r-1) + (n-1)Cr) % M.

7

Its probably because of matrix exponentiation. You have m^3 loops which is much slower than the required n*m algorithm

8

I did this problem in O(n^2) time using 2 2D arrays. I got TLE in one testcase in that approach.

code : TLE in one case

But when I calculated using 1 2D (For nCr) and another 1D for DP I got accepted. Trying to understand just what happened there.

code : Accepted

9

Its just one of the many weird things that come with competitive programming. lol

10

my code also has a complexity of O(mnt)… but it is giving TLE even with fast I/O,can anyone help me ?
here is the code : http://www.codechef.com/viewsolution/7144879

11

I am using memoization to solve this problem. Getting TLE in one of the cases of sub-task 3 ? Please help.
Here is the


[1].


  [1]: http://www.codechef.com/viewsolution/7237876
12

Elegant solution… used 2 2D arrays to build up answer from 1xM to NxM.


answer is sum of elements of last row of dp array.
Got WA in challenge due to faulty code which calculated nCr.
Got AC once I corrected it.

13

Can someone please explain that nCr array computation in detail, or a tutorial reference would be appreciated. I have seen it in many problems as a pre computation stage but didn’t understand the logic.

14

I will just complete the TODO.

Suppose X=2 , M=3 i.e. how many ways to choose 3 non-negative integers to get sum X.
Take X no of objects i.e. xx. So the question is in how many ways we can partition this, then the number of objects between partitions will be my M numbers summing up to X.

Denote partition by | and object by x. If there are n number of x’s to the left of leftmost ‘|’ or right of rightmost ‘|’ or between 2 ‘|’ then there is digit n (leftmost,rightmost or at that place respectively). If ‘|’ is right most or left most then it means rightmost/leftmost digit is 0. If there are consecutive |, then it means there is 0 at that place.

For example : 002 -> ||xx , 011 -> |x|x , 020 -> |xx| , 101 -> x||x , 110 -> x|x| , 200 -> xx||

Note that, there will be M-1 ‘|’ ( because we want M numbers).
Hence, total (X+M-1) places and number of ways to place (M-1) ‘|’ in (X+M-1) places is (X+M−1) C (M−1) .

PS: I first used this DP by the recurrence

f(X, M) = 1 if X = 0

    = 0                                    if X != 0 and M = 0

    = sum f(X - i, M - 1) over i in [0, X] otherwise

When I printed the array and saw the numbers of Pascal’s triangle, then I found the combinatorics formula and then later found the logic of it.

2 Likes
15

For more information on the TODO see here.

16

How you came up with the formula for number of ways to fill a row with M elements that sums to X?

17

how is 002 -> ||xx?

I get that to the right of each ‘|’ there is a 0. But how come we just have 1 digit ‘2’ for ‘xx’ ?

18

can someone explain the base case ‘(i==N+1) return 1’ ??

19

Look, ‘|’ is the partition. It counts number of x’s left/right to it or in between 2 ‘|’.

002 -> ||xx

Left most is ‘|’ hence left most digit is 0 because there are no x’s left of it.

After ‘|’ is another ‘|’, hence no x in between hence 0

After this |, we have 2 x’s hence 2.

Similarly, |xx||xxx would be 0203.

Leftmost is a ‘|’ hence leftmost number is 0. After this before the next ‘|’, we encounter 2 x’s hence 2. Then we have no x’s, before next ‘|’ hence 0. And finally to the right of it there are 3 x’s hence 3 at the rightmost number.

So, for M numbers we would have (M-1) ‘|’. OK?

20

I can’t understand that where does the solution given above takes into the account that the ith row sum will be more or equal to (i-1)th row ? I think it is not clearly mentioned in the code.