CountPaths

SRM 398 · 2008-04-15 · by boba5551

SRM 398 · 2008-04-15 · by boba5551 · Dynamic Programming

Show categories

Class Name: CountPaths

Return Type: int[]

Method Name: difPaths

Arg Types: (int, int, vector<int>, vector<int>)

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.

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

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)

6
4
{3, 5}
{2, 3}
Returns: {14, 24, 18 }

6
4
{5, 3}
{3, 2}
Returns: {14, 24, 0 }

30
30
{1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28, 28, 29, 29, 30, 30}
{1, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 17, 17, 17, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 26, 26, 27, 27, 28}
Returns: {0, 980196, 492851, 420437, 242629, 75394, 25153, 54279, 263790, 360516, 177345, 686437, 258400, 451652, 248564, 573042, 12035, 194248, 726779, 353374, 901839, 620764, 524091, 981772, 709090, 280008, 568983, 170599, 253917, 439999, 606924, 716612, 242394, 153622, 418219, 323651, 336646, 410897, 424702, 786576, 24281, 562034, 94208, 0, 0, 0, 0, 0, 0, 0, 0 }

5
5
{1, 2, 3}
{3, 4, 5}
Returns: {42, 14, 10, 4 }

36)

50
50
{50, 1}
{50, 1}
Returns: {0, 0, 0 }

There is no path that passes through (50, 50) before (1, 1).

Submissions are judged against all 57 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CountPaths with a public method vector<int> difPaths(int r, int c, vector<int> fieldrow, vector<int> fieldcol) · 57 test cases · 2 s / 256 MB per case