PROBLEM LINK:Author: Pavel Sheftelevich 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 EXPLANATIONSuppose 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
Putting this together we have the following solution
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".
asked 02 Jun '15, 13:13

whatever i wrote in this question i might not be able to explain it to myself later. :P answered 15 Jun '15, 15:38

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+n1,n1) 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

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

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 code : Accepted answered 15 Jun '15, 20:53
Its just one of the many weird things that come with competitive programming. lol
(15 Jun '15, 21:16)

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

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

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

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

can someone explain the base case '(i==N+1) return 1' ?? answered 22 Jun '15, 12:56

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 (i1)th row ? I think it is not clearly mentioned in the code. answered 23 Jun '15, 00:07

@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
