Connection Status:
Competition Arena > SteeplechaseTrack

SteeplechaseTrack

SRM 462 · 2009-11-12 · by Nickolas

SRM 462 · 2009-11-12 · by Nickolas · Graph Theory
Class Name: SteeplechaseTrack
Return Type: int
Method Name: maxComplexity
Arg Types: (vector<string>, vector<string>, int)
Problem Statement

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 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.

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
5)
{"199", "111"}
{"01", "00"}
2
Returns: 19

1-fence run is better than 2-fence (to test not reinitializing)

6)
{"199", "111", "111"}
{"010", "001", "000"}
3
Returns: 19

same as #5 - one fence still better than 3

7)
{"999","999","999","999","999","999","999","999","999","999",
"999","999","999","999","999","999","999","999","999","999",
"999","999","999","999","999","999","999","999","999","999",
"999","999","999","999","999","999","999","999","999","999",
"999","999","999","999","999","999","999","999","999","999"}
{"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999",
"99999999999999999999999999999999999999999999999999"}
100
Returns: 1809

maxtest - can loop, so 100 jumps and 99 runs between the fences, for a total complexity 9 + 100*9 + 99*9 + 9 = 201*9 = 1809.

Submissions are judged against all 79 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SteeplechaseTrack with a public method int maxComplexity(vector<string> fences, vector<string> tracks, int N) · 79 test cases · 2 s / 256 MB per case

Submitting as anonymous