TopCoder problem "BikeRiding" used in SRM 345 (Division II Level Three)



Problem Statement

    

Your friend likes riding his bike on the hills outside your town. He asked you to help him count the number of routes he can take. There are several locations on the hills, some of them directly connected by paths (you can take each path only in one given direction). He would like to start at one of the locations given in startPoints and end at location endPoint. Return the number of distinct routes that he can use to do that. If the number is larger than n or infinite, return -1.

The definition of a route is as follows:

  • A legal route is a sequence of locations starting with one from startPoints and ending with endPoint. Each location on the route other than the last one has a path leading to the next consecutive location.
  • Two routes are distinct if they each have a different sequence of locations.
  • A route can have any length.
  • Any location (including endPoint) may be present multiple times on the route.

You are given all locations and connections between them in the String[] paths. The j-th character of the i-th element of paths is '1' (one) if there is a direct one-way path from location i to location j, and '0' (zero) otherwise.

 

Definition

    
Class:BikeRiding
Method:countRoutes
Parameters:String[], int[], int, int
Returns:int
Method signature:int countRoutes(String[] paths, int[] startPoints, int endPoint, int n)
(be sure your method is public)
    
 

Constraints

-paths will contain between 2 and 50 elements, inclusive (let k be this number).
-Each element of paths will contain exactly k characters.
-Each element of paths will contain only '0' (zero) and '1' (one) characters.
-endPoint and each element of startPoints will be between 0 and k-1.
-Each element in startPoints will be distinct.
-None of the elements in startPoints will be equal to endPoint
-n will be between 2 and 10^9, inclusive.
 

Examples

0)
    
{"011" ,"001", "000"}
{0,1}
2
5
Returns: 3
There is one possible route from location 1, and two from location 0.
1)
    
{"01000",
 "00100",
 "00010",
 "01001",
 "00000"}
{0}
4
10
Returns: -1
The number of routes is infinite.
2)
    
{"000111000000000","000111000000000","000111000000000",
 "000000111000000","000000111000000","000000111000000",
 "000000000111000","000000000111000","000000000111000",
 "000000000000111","000000000000111","000000000000111",
 "000000000000001","000000000000001","000000000000000"}
{0,1,2}
14
1000
Returns: 243
3)
    
{"010", "100", "001"}
{0}
2
10
Returns: 0
There is no possible route.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10669&pm=6763

Writer:

rusolis

Testers:

PabloGilberto , brett1479 , Olexiy , ged

Problem categories:

Dynamic Programming, Graph Theory