TopCoder problem "CountPaths" used in SRM 398 (Division I Level Two)



Problem Statement

    

There is a rectangular table divided into r rows and c columns, for a total of r * c fields. The rows are numbered 1 to r, from bottom to top, and the columns are numbered 1 to c, from left to right. All coordinates in this problem will be given as (row, column).



You are given int[]s fieldrow and fieldcol containing a list of special fields in the table, where (fieldrow[i], fieldcol[i]) are the coordinates of the i-th field. For each number n, where 0 <= n <= the number of elements in fieldrow, you must count the number of different paths from field (1, 1) to field (r, c) that contain exactly n special fields. These paths are called paths of length n.



There are two rules you must follow. First, you are only allowed to make moves that are straight up or to the right. In other words, from each field (row, column), you can only move to field (row+1, column) or field (row, column+1). Second, in each path, all the special fields must appear in the same order that they appear in the input. In other words, if the path contains field a = (fieldrow[idxa], fieldcol[idxa]) and field b = (fieldrow[idxb], fieldcol[idxb]), and a appears before b in the path, then idxa must be less than idxb.



Return a int[] containing exactly k+1 elements, where k is the number of elements in fieldrow. The i-th element (0-indexed) must be the number of different paths of length i modulo 1000007.

 

Definition

    
Class:CountPaths
Method:difPaths
Parameters:int, int, int[], int[]
Returns:int[]
Method signature:int[] difPaths(int r, int c, int[] fieldrow, int[] fieldcol)
(be sure your method is public)
    
 

Constraints

-r and c will each be between 1 and 50, inclusive.
-fieldrow will contain between 0 and 50 elements, inclusive.
-fieldcol and fieldrow will contain same number of elements.
-Each element of fieldrow will be between 1 and r, inclusive.
-Each element of fieldcol will be between 1 and c, inclusive.
-For all i and j, where i < j, the pairs (fieldrow[i], fieldcol[i]) and (fieldrow[j], fieldcol[j]) will be different.
 

Examples

0)
    
3
3
{2, 3}
{2, 2}
Returns: {1, 3, 2 }
Path of length 0:
(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)
Paths of length 1:
(1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3)
(1, 1) -> (1, 2) -> (2, 2) -> (2, 3) -> (3, 3)
(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
Paths of length 2:
(1, 1) -> (2, 1) -> (2, 2) -> (3, 2) -> (3, 3)
(1, 1) -> (1, 2) -> (2, 2) -> (3, 2) -> (3, 3)
1)
    
6
4
{5, 3}
{3, 2}
Returns: {14, 24, 0 }
2)
    
5
5
{1, 2, 3}
{3, 4, 5}
Returns: {42, 14, 10, 4 }
3)
    
35
37
{3, 28, 28, 27, 27, 5, 15, 23, 21, 3, 8, 25, 34, 31, 33, 35, 13, 34}
{12, 34, 3, 9, 34, 3, 18, 17, 26, 5, 23, 14, 20, 7, 3, 20, 19, 23}
Returns: 
{830519, 709835, 755976, 219563, 868547, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
4)
    
50
50
{50, 1}
{50, 1}
Returns: {0, 0, 0 }
There is no path that passes through (50, 50) before (1, 1).

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8158

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12170&pm=8158

Writer:

boba5551

Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming