CNTWAYS - Editorial

editorial
, , , ,
6

Why ant can not go to (0,0)->(p,b)->(n,m); directly. so from this way count will be ways(p, B) × ways(N-p, M-B).

what is problem in this?

7

I was doing the same way but had no idea of Modular Multiplicative inverse and so i quit :/…

8

In definition of C(X,Y) it should be return (fact[X] × ifact[X-Y] × ifact[Y]) mod MOD instead of return (fact[X+Y] × ifact[X-Y] × ifact[Y]) mod MOD. Isn’t it?

9

What is wrong if I calculate :
a = number of ways from (0, 0) -> (N, M);
b = number of ways from (A, 0) -> (A, B);

Ans = a - b + 1?

10

Can any 1 help me ? I’m getting wrong answer and i have checked for no. of test cases!
Solution

11

Why can we get away with calculating factorials and their inverses for integers only upto 800000? I thought it would require calculating factorials upto 10^9 + 7.

2 Likes
12

nice tutorial!!!

1 Like
13

I m getting TLE by this approach…
can ny1 check my code CodeChef: Practical coding for everyone

14

Is this possible that MOD is not a prime number ? then how can we solve this?

15

@fushar can you please tell me whats wrong with my code. Its completely based on your editorial. Please can someone help me?
http://www.codechef.com/viewsolution/5970315

16

Can somebody pls explain to me in detail why we need to first go from 0,0 to p,b-1 and not directly to p,b
i did not get the explanation given fr this.

17

The difficulty rating is based on the following scheme:

Since this problem is 5th by the difficulty according to AC rate we could call it EASY. But you are right it is better to call it EASY-MEDIUM.

3 Likes
18

If I understood you well (b=(0,0)->(A,B)), simply because this formula is not working

M=3 N=4 A=2 B=2
 1  1  1
 1  2  3
 1  3  6  6  6
 1  4 10 16 22

a=#( (0,0)->(M,N) )=35
 1  1  1  1  1
 1  2  3  4  5
 1  3  6 10 15
 1  4 10 20 35

b=#( (0,0)->(A,B) ) = 2
1 1
1 2

22 != 35 - 2 + 1

19

You count way (0,0)->(p,b-1)->(p,b)->(n,m) twice - once for original (p,b) is (p,b-1) and again for (p,b).

20

is it possible to that result is negative?

Try this one:

5
1000 1000 500 500
21

Consider a path of the form (0,0) -> (p,b) -> (p, b+1) -> (n,m)
This is present in (0,0) -> (p,b) -> (n,m) and also (0,0) -> (p+1,b) -> (n,m)
So it will be counted in p as well as p+1.
Thus it leads to over counting.

22

result should be positive

23

got it right! just had to do result%MOD in every iteration of loop.
http://www.codechef.com/viewsolution/1628252

24

In calculating inverse for integer(suppose for example 800000) we need to calculate A^(MOD-2). In the power function there is a step in which we have to calculate A * A(which equals 6.4*10^11 for above example). So, we can calculate only up to inverse such that A * A is in range for data type.

25

You are correct. It is fixed.