STDYTAB - Editorial

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

7 Likes

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

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 CodeChef: Practical coding for everyone

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

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 : CodeChef: Practical coding for everyone

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

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.

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.

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.

3 Likes

For more information on the TODO see here.

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

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

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.

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

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

2 Likes

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

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

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

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’ ?

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?