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

×

STDYTAB - Editorial

3
2

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

This question is marked "community wiki".

asked 02 Jun '15, 13:13

balajiganapath's gravatar image

6★balajiganapath ♦♦
75542742
accept rate: 77%

edited 20 Jan '16, 12:47

admin's gravatar image

0★admin ♦♦
19.3k348495534


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

link

answered 15 Jun '15, 15:38

ashish1729's gravatar image

3★ashish1729
1535
accept rate: 10%

2

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.

link

answered 17 Jun '15, 15:27

akarshan2701's gravatar image

4★akarshan2701
212
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) akarshan27014★

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

link

answered 15 Jun '15, 16:17

dark_energy's gravatar image

3★dark_energy
11
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 http://www.codechef.com/viewsolution/7215565

link

answered 15 Jun '15, 17:36

raghu_317's gravatar image

5★raghu_317
19815
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

link

answered 15 Jun '15, 20:53

aroup's gravatar image

3★aroup
11
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 : http://www.codechef.com/viewsolution/7144879

link

answered 16 Jun '15, 09:53

aravind95's gravatar image

4★aravind95
1
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.

link

answered 16 Jun '15, 19:37

asan's gravatar image

2★asan
1
accept rate: 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.

link

answered 16 Jun '15, 20:11

rishabh__joshi's gravatar image

3★rishabh__joshi
1
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.

link

answered 17 Jun '15, 12:48

ajit_a's gravatar image

1★ajit_a
41113
accept rate: 0%

edited 17 Jun '15, 12:48

For more information on the TODO see here.

link

answered 17 Jun '15, 22:52

henryhenry's gravatar image

2★henryhenry
1
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?

link

answered 20 Jun '15, 21:05

suheb's gravatar image

1★suheb
11
accept rate: 0%

edited 20 Jun '15, 21:11

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

link

answered 22 Jun '15, 12:56

akhileshydv20's gravatar image

2★akhileshydv20
173
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.

link

answered 23 Jun '15, 00:07

udontknow's gravatar image

1★udontknow
1
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.

link

answered 23 Jun '15, 10:26

arcticblue's gravatar image

4★arcticblue
812
accept rate: 18%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×15,005
×3,393
×1,875
×768
×156
×4

question asked: 02 Jun '15, 13:13

question was seen: 6,989 times

last updated: 20 Jan '16, 12:47