TopCoder problem "FallingBall" used in SRM 289 (Division I Level One , Division II Level Two)

Problem Statement


In a popular game, a ball is dropped from the top of a triangle of cells containing n rows. The ball keeps falling down row by row until it reaches the bottom of the triangle. In each row, the ball can fall either left or right. The first row contains one cell, the second contains two, and so on. The game looks like the following picture (where a cell is the space between two consecutive points in a row):

The rows are numbered from top to bottom starting from zero, and the cells in each row are numbered from left to right starting from zero. Note that row i will have i+1 cells numbered 0 to i, and if the ball is on cell k of row i, it will either fall left to cell k of row i+1, or right to cell k+1 of row i+1.

Given a String[] cells, containing a list of cells, and an int n, the number of rows in the triangle, return the number of paths in which the ball passes through all of the given cells. Each element of cells will be formatted "<row> <cell>" (quotes for clarity), where <row> is the cell's row, and <cell> is the cell's position within that row.



Parameters:String[], int
Method signature:int howMany(String[] cells, int n)
(be sure your method is public)


-cells will have between 1 and 50 elements, inclusive.
-n will be between 1 and 30, inclusive.
-Each element of cells will be formatted "<row> <cell>", where <row> and <cell> are each integers, with no extra leading zeros.
-Each <row> in cells will be between 0 and n-1, inclusive.
-In each element of cells, <cell> will be between 0 and <row>, inclusive.


{"3 2","5 2"}
Returns: 6
This example is shown in the picture above. There are 3 ways to reach the cell (3,2), then only one way to reach the second cell (5,2), and two more ways of reaching the bottom. That gives a total of 6 ways of passing through the cells.
{"0 0","0 0"}
Returns: 536870912
All the possible paths pass through the cell (0,0).
{"0 0","29 0"}
Returns: 1
There is only one way to reach the bottom-right cell.
{"10 0","10 1"}
Returns: 0
Two different cells in the same row can never be touched in the same path.

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories:

Simple Math