RaceCircuit
SRM 798 · 2021-01-22 · by misof
Problem Statement
Time limit is 3 seconds.
Chessland is located on a rectangular board divided into R times C unit squares, with R*C even. Squares have coordinates (row, column) with rows numbered from 0 top to bottom and columns numbered from 0 left to right.
Chessland wants its own Formula 1 circuit. The circuit will consist of road segments. Each road segment must connect two squares that share a side. The circuit must visit each square of the board exactly once.
For each pair of such squares you are given whether it's possible to build the road segment, and if yes, what it costs.
Additionally, corners are harder to build than straight road segments. For each square you are given the extra cost you have to pay if the circuit changes direction within that square.
You are given:
- The dimensions R and C.
- The
int[] costRight where the value costRight[r*C+c] is the cost of building a road between the square (r, c) and the square (r, c+1), or -1 if this is impossible. - The
int[] costDown where the value costDown[r*C+c] is the cost of building a road between the square (r, c) and the square (r+1, c), or -1 if this is impossible. - The
int[] costCorner where the value costCorner[r*C+c] is the cost of building a corner of the circuit on the square (r, c).
Return -1 if no solution exists, or the cost of the cheapest solution if solutions exist.
Constraints
- R will be between 2 and 12, inclusive.
- C will be between 2 and 12, inclusive.
- R * C will be even.
- costRight, costDown and costCorner will have R * C elements each.
- Each element of costRight and costDown will be between -1 and 999, inclusive.
- Each element of costCorner will be between 0 and 999, inclusive.
- Elements of costRight and costDown that correspond to road segments leaving the kingdom will be -1.
2
2
{10, -1,
40, -1}
{20, 30,
-1, -1}
{5, 4,
9, 7}
Returns: 125
The smallest possible example. The costs to build roads and corners are shown below: [5] --10-- [4] | | | | 20 30 | | | | [9] --40-- [7] There is only one way how to build the circuit. The road segments cost 10+30+40+20 = 100 and the extra cost for its corners is 5+4+9+7 = 25.
2
2
{10, -1,
40, -1}
{20, 30,
-1, -1}
{5, 2,
9, 7}
Returns: 123
2
2
{0, -1,
0, -1}
{-1, 0,
-1, -1}
{5, 4,
9, 7}
Returns: -1
A trivial example with no solution.
3
4
{1, 2, 1, -1,
2, 1, 2, -1,
1, 1, 1, -1}
{ 1, 1, 1, 1,
1, 2, 2, 1,
-1, -1, -1, -1}
{100, 100, 100, 100,
100, 100, 100, 100,
100, 100, 100, 100}
Returns: 812
Building the corners costs the same everywhere. There are only two possible circuits and both have the same number of corners, so we just need the cheapest road segments. Luckily for us, the road segments with cost 1 form exactly one of the two possible circuits. *---* *---* | | | | * *---* * | | *---*---*---* We pay 800 for the corners and 12 for the road segments.
3
4
{1, 2, 1, -1,
2, 1, 2, -1,
1, 1, 1, -1}
{ 1, 1, 1, 1,
1, 2, 2, 1,
-1, -1, -1, -1}
{100, 100, 100, 100,
100, 100, 100, 100,
100, 50, 50, 100}
Returns: 715
Here the road costs are negligible in comparison to the corner costs. The optimal solution is to build the other possible circuit with corners at (2,1) and (2,2).
3
4
{1, 2, 1, -1,
2, 1, 2, -1,
1, 1, 1, -1}
{ 1, 1, 1, 1,
1, 2, 2, 1,
-1, -1, -1, -1}
{100, 100, 100, 100,
100, 100, 100, 100,
50, 100, 100, 50}
Returns: 712
Here the two cheap watchtowers cannot be opposite each other on any valid circular road, so we go with the cheapest road, one cheap and one expensive watchtower.
Submissions are judged against all 115 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RaceCircuit with a public method int construct(int R, int C, vector<int> costRight, vector<int> costDown, vector<int> costCorner) · 115 test cases · 2 s / 256 MB per case