TopCoder problem "GraphPaths" used in TCI '02 Semifinals 1 (Division I Level Two)



Problem Statement

    You will be given a String[] representing a directed graph. Each element will be formatted as follows:

Node1 Node2 Node3 ...

where NodeJ is a number (0-indexed) representing a node. Element K of the String[] graph will list all of the nodes that node K has a directed edge to. For example:
graph = {"1 2 3",
	 "0 1 2",
	 "0",
	 "1 2"}
Represents a directed graph where:

node 0 has a directed edge to nodes 1, 2, and 3,

node 1 has a directed edge to nodes 0, 1 and 2,

node 2 has a directed edge to node 0, and

node 3 has a directed edge to nodes 1 and 2.

Given a String[] formatted as above representing the directed graph, an int representing the starting node, an int representing the destination node, and an int representing the path length, determine how many unique paths exist from the starting node to the destination node of the specified length. Note, the paths may contain cycles. The length of a path is how many edges it traverses, possibly counting an edge more than once if the path contains a cycle.

If the total number of paths is greater than 2^63-1 (the limit of a long), return -1

 

Definition

    
Class:GraphPaths
Method:howMany
Parameters:String[], int, int, int
Returns:long
Method signature:long howMany(String[] graph, int start, int destination, int length)
(be sure your method is public)
    
 

Notes

-Two paths are unique if they differ at any node. For example: A->B->C->B is unique from A->C->B->B which are both unique from A->B->B->C.
 

Constraints

-graph will contain between 1 and 50 elements inclusive
-Each element of graph will have length between 1 and 50 inclusive
-Each element of graph will be a single-space delimited string of zero or more integers with no leading zeros
-Each element of graph will contain no leading or trailing whitespace
-Each integer in each element of graph will be between 0 and (size of graph - 1) inclusive where size of graph is the number of elements in graph
-Each element of graph will not contain any repeated integers
-start will be between 0 and (size of graph - 1) inclusive
-destination will be between 0 and (size of graph - 1) inclusive
-length will be between 1 and 1,000,000,000 inclusive
 

Examples

0)
    
{"1 2 3",
 "0 1 2",
 "0",
 "1 2"}
0
1
2
Returns: 2
1)
    
{
"1",
"2",
"3",
"4",
"5",
"0 3"
}
0
0
10000001
Returns: 0
Note that all paths from 0 to 0 have length divisible by 3.
2)
    
{
"1 2",
"0",
"0"
}
0
0
126
Returns: -1
The actual answer to this is 2^63, but that is outside of the range for a long, so we return -1.
3)
    
{"0 1 2 3", "0 1 2 3", "0 1 2 3", "0 1 2 3"} 
2
2
63
Returns: -1
4)
    
{"0"}
0
0
1
Returns: 1

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4370&pm=1168

Writer:

brett1479

Testers:

alexcchan , lbackstrom

Problem categories:

Dynamic Programming, Graph Theory