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 vector 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 vector 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 i0, i1, ..., in-1 for which all of
the following conditions are satisfied:
There is a track from the starting line to fence i0.
There is a track from fence ik to fence ik+1 for 0 <= k <= n-2.
There is a track from fence in-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:vector , vector , int
Returns:int
Method signature:int maxComplexity(vector fences, vector tracks, int N)
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
0)
{"310",
"300",
"301"}
{"010",
"001",
"000"}
4
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.
1)
{"923"}
{"1"}
100
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.
2)
{"111",
"222",
"333"}
{"743",
"985",
"380"}
1
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.
3)
{"101",
"202",
"303"}
{"659",
"431",
"770"}
5
Returns: -1
There are no tracks leading from the starting line to a fence, so no valid routes can be
constructed.
4)
{"693",
"982",
"236"}
{"603",
"986",
"780"}
10
Returns: 172
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.