×

# STDYTAB - Editorial

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

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


## 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:

This question is marked "community wiki".

75542742
accept rate: 77%

19.0k348495531

 7 whatever i wrote in this question i might not be able to explain it to myself later. :P answered 15 Jun '15, 15:38 153●5 accept rate: 10% 2 I thought I was the only one who was thinking this. :-D (15 Jun '15, 15:41) apptica6★
 1 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. answered 17 Jun '15, 15:27 11●2 accept rate: 0% 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' ? (20 Jun '15, 22:56) 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? (22 Jun '15, 17:36)
 0 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)... answered 15 Jun '15, 16:17 1●1 accept rate: 0% You could have used nCr = ((n-1)C(r-1) + (n-1)Cr) % M. (15 Jun '15, 17:38)
 0 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 answered 15 Jun '15, 17:36 198●1●5 accept rate: 0% Its probably because of matrix exponentiation. You have m^3 loops which is much slower than the required n*m algorithm (15 Jun '15, 18:14)
 0 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 answered 15 Jun '15, 20:53 3★aroup 1●1 accept rate: 0% Its just one of the many weird things that come with competitive programming. lol (15 Jun '15, 21:16)
 0 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 answered 16 Jun '15, 09:53 1 accept rate: 0%
 0 I am using memoization to solve this problem. Getting TLE in one of the cases of sub-task 3 ? Please help. Here is the Code. answered 16 Jun '15, 19:37 2★asan 1 accept rate: 0%
 0 Elegant solution.. used 2 2D arrays to build up answer from 1xM to NxM. http://ideone.com/vDBnr0 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. answered 16 Jun '15, 20:11 1 accept rate: 0%
 0 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. answered 17 Jun '15, 12:48 1★ajit_a 41●1●1●3 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,365
×3,155
×1,754
×756
×156
×4

question asked: 02 Jun '15, 13:13

question was seen: 6,863 times

last updated: 20 Jan '16, 12:47