You are not logged in. Please login at to post your questions!


STDYTAB - Editorial




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




Combinatorics, DP


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$.


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


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 solution
Tester's solution

This question is marked "community wiki".

asked 02 Jun '15, 13:13

balajiganapath's gravatar image

6★balajiganapath ♦♦
accept rate: 77%

edited 20 Jan '16, 12:47

admin's gravatar image

0★admin ♦♦

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


answered 15 Jun '15, 15:38

ashish1729's gravatar image

accept rate: 10%


I thought I was the only one who was thinking this. :-D

(15 Jun '15, 15:41) apptica5★

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

akarshan2701's gravatar image

accept rate: 0%

edited 22 Jun '15, 17:47

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) cool_techie2★

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) akarshan27013★

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

dark_energy's gravatar image

accept rate: 0%

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

(15 Jun '15, 17:38) tapasjain016★

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


answered 15 Jun '15, 17:36

raghu_317's gravatar image

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) eknoor2924★

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

aroup's gravatar image

accept rate: 0%

edited 15 Jun '15, 20:54

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

(15 Jun '15, 21:16) eknoor2924★

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 :


answered 16 Jun '15, 09:53

aravind95's gravatar image

accept rate: 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

asan's gravatar image

accept rate: 0%

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.


answered 16 Jun '15, 20:11

rishabh__joshi's gravatar image

accept rate: 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

ajit_a's gravatar image

accept rate: 0%

edited 17 Jun '15, 12:48

For more information on the TODO see here.


answered 17 Jun '15, 22:52

henryhenry's gravatar image

accept rate: 0%

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


answered 20 Jun '15, 21:05

suheb's gravatar image

accept rate: 0%

edited 20 Jun '15, 21:11

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


answered 22 Jun '15, 12:56

akhileshydv20's gravatar image

accept rate: 0%

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.


answered 23 Jun '15, 00:07

udontknow's gravatar image

accept rate: 0%

@akhileshydv20 The if statement if ( i == N + 1) return 1; means if all the rows have now been done then this is a valid array so return 1 as it's one possible solution. The reason it's N + 1 is because there are N rows and the pseudo code starts at 1.


answered 23 Jun '15, 10:26

arcticblue's gravatar image

accept rate: 18%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 02 Jun '15, 13:13

question was seen: 7,182 times

last updated: 20 Jan '16, 12:47