TopCoder problem "SteeplechaseTrack" used in SRM 462 (Division II Level Three)

Problem Statement

Your company is going to sponsor a steeplechase horse race at your local racecourse. As a sponsor, you can choose the exact route of the race, and you want it to be as hard as possible.

The racecourse contains a startling line, a finish line, and several fences connected with tracks. Horses start at the starting line, run along the tracks, jump over all fences along the way, and end at the finish line.

You are given a String[] fences where the i-th element describes the i-th fence, and contains exactly three digits between '0' and '9', inclusive. The first digit is the complexity of jumping over the fence. The second digit is the complexity of running from the starting line to the fence. If it is '0', that means there is no track between the starting line and the fence. The third digit is the complexity of running from the fence to the finish line. If it is '0', that means there is no track between the fence and the finish line.

You are also given a String[] tracks describing the tracks connecting the fences. The j-th character of the i-th element of tracks is the complexity of running from fence i to fence j. If that character is '0', that means there is no track from fence i to fence j. It is possible for a track to exist between a fence and itself. Note that all tracks are one-way tracks. If there's a track from fence i to fence j, there isn't necessarily a track from fence j to fence i. Also, complexities are not symmetrical, so the complexity of running from fence i to fence j may be different from the complexity of running from fence j to fence i.

A valid route for the race is a sequence of fences with indices i₀, i₁, ..., i_n-1 for which all of the following conditions are satisfied:

There is a track from the starting line to fence i₀.
There is a track from fence i_k to fence i_k+1 for 0 <= k <= n-2.
There is a track from fence i_n-1 to the finish line.

Note that the same fence may be used multiple times within a route. Each time the horse runs along a track or jumps over a fence, the corresponding complexity is added to the total complexity for the route. Return the maximal total complexity for a valid route containing at most N fences. If the same fence appears multiple times within the route, each occurrence counts toward the total number of fences. If it is impossible to hold a race which satisfies the constraints on the given racecourse, return -1 instead.

Definition

Class:	SteeplechaseTrack
Method:	maxComplexity
Parameters:	String[], String[], int
Returns:	int
Method signature:	int maxComplexity(String[] fences, String[] tracks, int N)
(be sure your method is public)

Constraints

fences will contain between 1 and 50 elements, inclusive.

Each element of fences will contain exactly 3 characters.

tracks will contain the same number of elements as fences.

Each element of tracks will contain the same number of characters as the number of elements in fences.

Each character in fences and tracks will be between '0' and '9', inclusive.

Character 0 of each element of fences will not be '0'.

N will be between 1 and 100, inclusive.

Examples

{"310",
 "300",
 "301"}

{"010",
 "001",
 "000"}

Returns: 13

You are allowed to use as many as four fences, but the only valid route for this racecourse is start-0-1-2-finish.

{"923"}

{"1"}

Returns: 1004

This route consists of 100 jumps over the only fence and 99 runs around this fence, for a total complexity 2 + 100*9 + 99*1 + 3 = 1004.

{"111",
 "222",
 "333"}

{"743",
 "985",
 "380"}

Returns: 9

With only one fence allowed, the complexity of a route is the sum of the following complexities: running from the starting line to the fence, jumping over the fence, and running from the fence to the finish line.

{"101",
 "202",
 "303"}

{"659",
 "431",
 "770"}

Returns: -1

There are no tracks leading from the starting line to a fence, so no valid routes can be constructed.

{"693",
 "982",
 "236"}

{"603",
 "986",
 "780"}

Returns: 172

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14147&pm=10594

Writer:

Nickolas

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Graph Theory