CNTWAYS - Editorial

PROBLEM LINKS

Practice

Contest

DIFFICULTY

EASY-MEDIUM

PREREQUISITES

Combinatorics, Modular Multiplicative Inverse

PROBLEM

There is a rectangle of N × M units. Another rectangle of A × B units is cut off from the upper right corner. Count the number of ways an ant can reach the bottom right corner starting from the top left corner, if it can only move right or down.

QUICK EXPLANATION

Split the path into 3 subpaths: (0, 0) → (p, B-1) → (p, B) → (N, M). The answer is the sum of (number of ways to go from (0, 0) to (p, B-1)) × (number of ways to go from (p, B) to (N, M)) over all possible values of p.

EXPLANATION

A = B = 0

First, let’s consider a simpler version of the problem where A = B = 0, i.e. the rectangle is intact. This becomes a traditional problem. To reach the bottom right corner, the ant needs to move right N times and move down M times. The order of moves does not matter. In other words, the ant needs to move N+M times, N of which the ant moves right. The number of ways, by combinatorics, is:

(N+M) choose N = C(N+M, N) = (N+M)! / (N! × M!)

Note that (N+M) choose N = (N+M) choose M.

Calculating C(N+M, N)

Since we have to calculate the answer modulo MOD = 1,000,000,007, the above formula have to be rewritten to

C(N+M, M) = ((N+M)! × N!-1 × M!-1) mod MOD

Here, x-1 is the modular multiplicative inverse of x modulo MOD. Since MOD is a prime number, we can calculate it using Fermat’s little theorem: x-1 = xMOD-2 (mod MOD). We can calculate xMOD-2 in O(lg MOD) time using exponentiation by squaring. Because we will use factorials many times in this solution, we can precompute all factorials and their inverses (modulo MOD) for all integers from 0 through 800,000, inclusive.

fact[0] = ifact[0] = 1
for i = 1; i ≤ 800000; i++:
    fact[i] = (i × fact[i-1]) mod MOD
    ifact[i] = (fact[i]MOD-2) mod MOD

Therefore the function C(X, Y) can be calculated in constant time as follows. For convenience, we also introduce function ways(N, M) that returns the number of ways an ant can reach the bottom right corner of an N × M intact rectangle.

function C(X, Y):
    return (fact[X] × ifact[X-Y] × ifact[Y]) mod MOD

function ways(N, M):
    return C(N+M, M)

A, B > 0

Consider this ASCII art picture of a typical input rectangle. Assume that the top left corner is (0, 0) and the bottom right corner is (N, M).

  +---------+
  |         |
  |         | B
  |         |       A
M +         +-------------+
  |                       |
  |                       |
  |                       |
  +-----------------------+
             N

We can split the ant’s journey from the top left corner to the bottom right in 3 phases:

Phase 1. The ant moves from top left corner to point (p, B-1):

  +---------+
  |\        |
  | \       | B
  |  p      |       A
M +         +-------------+
  |                       |
  |                       |
  |                       |
  +-----------------------+
             N

Phase 2. The ant moves down from point (p, B-1) to point (p, B):

  +---------+
  |\        |
  | \       | B
  |  p      |       A
M +  |      +-------------+
  |                       |
  |                       |
  |                       |
  +-----------------------+
             N

Phase 3. Finally, the ant moves from point (p, B) to point (N, M):

  +---------+
  |\        |
  | \       | B
  |  p      |       A
M +  |      +-------------+
  |  \                    |
  |   ------------------\ |
  |                      \|
  +-----------------------+
             N

Note that the phases are actually subproblems of the simpler problem mentioned before. The number of ways to perform Phase 1 is ways(p, B-1). The number of ways to perform Phase 2 is of course 1. Finally, the number of ways to perform Phase 3 is ways(N-p, M-B). Therefore, the number of ways if the ant passes point (p, B-1) and then point (p, B) is:

ways(p, B-1) × ways(N-p, M-B)

It is important to note that we do need an intermediate Phase 2 so that we do not count a path more than once.

To obtain the final answer, iterate over all possible values of p and sum the results. Here is a pseudocode of this solution.

read(N, M, A, B)
res = 0
for p = 0; p ≤ N-A; p++:
    res += ways(p, B-1) × ways(N-p, M-B)
println(res)

SETTER’S SOLUTION

Will be provided soon.

TESTER’S SOLUTION

Can be found here.

16 Likes

The difficulty ratings of these problems are ridiculous. There is no way this problem is ‘easy’. I came so close to solving this problem after spending three days working on it, and for someone to call it easy, i find a little insulting. If you do not have the required knowledge it is very tough. I had no idea about modular multiplicative inverses and how to calculate ‘n choose k’ in a fast efficient way. Learning all this was challenging enough. I think someone needs to rethink the ratings of these problems so I don’t feel so stupid :-).
I hope other people agree. Rant over(as they say)

30 Likes

Do we overcount the paths if we go from (0,0)->(p,B)->(p,B+1)->(N,M)? I think we don’t, but I Still could not get this question correct?Can admins please check what’s wrong with the submission ID : 1600878.It is giving WA.
Any help would be appreciated. Thanks

huhu … i didn’t submit that one 'cause i thought that the 0->(N-A) loop would take too long …
so i tried to reduce the product of binomial coefficient, to simplify it, but it seems it wasn’t
necessary … aaaaarrrgggg …

I got the idea right but didn’t know how to implement it without modular multiplicative inverse.
Thanks for this problem.

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?

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

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?

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?

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

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

nice tutorial!!!

1 Like

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

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

@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

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.

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

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

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

is it possible to that result is negative?

Try this one:

5
1000 1000 500 500