PasswordXGrid
TCO12 Round 1C · 2012-03-27 · by cgy4ever
TCO12 Round 1C · 2012-03-27 · by cgy4ever · Graph Theory, Math
Problem Statement
Problem Statement
Ms. Ciel loves rabbits. She has a large special cage for her rabbits. The cage is protected by a special lock: a board containing a grid.
The board contains an N times M grid. We can assign integer coordinates to the vertices of the grid. (Vertices are the points where horizontal and vertical grid lines intersect.) The top left corner of the grid will get the coordinates (0,0) and the bottom right corner coordinates (N,M). Each line segment between two adjacent vertices is labeled by an integer from 0 to 9, inclusive. You are given twoString[] s horizontal and vertical containing these labels in the format defined below.
To unlock this board, you must put your finger on the point (0, 0), and move to the point (N, M). In each step you can only go down or right. I.e., if you are currently at the point (i,j), your next step may take you either to (i,j+1), or to (i+1,j). By moving your finger you picked one of the paths from the top left to the bottom right corner. The path consists of N+M line segments, and each of those line segments has an integer label. The cost of a path is the sum of those labels. Let S be the smallest value among the costs of all valid paths from the top left to the bottom right corner. Inside the board there is a counter that computes the sum of all numbers that are on the line segments you used in your path. The lock will open if and only if you picked a path with cost exactly S, i.e., a path with the smallest possible cost.
Finding the way to unlock a given board is a shortest path problem. You could surely solve it, but Ciel is just a young fox. She does not know any complicated algorithms such as Dijkstra, Bellman-Ford, or Floyd-Warshall. Thus unlocking the board is too hard for her. She wants you to modify her board to a state in which it can be unlocked by any path from the top left to the bottom right corner. In other words, on the resulting board all valid paths must have exactly the same cost T. The only allowed operation is to increase some of the labels. (The new labels must again be integers, but they are allowed to exceed 9.) Compute and return the smallest possible value of T.
The board contains an N times M grid. We can assign integer coordinates to the vertices of the grid. (Vertices are the points where horizontal and vertical grid lines intersect.) The top left corner of the grid will get the coordinates (0,0) and the bottom right corner coordinates (N,M). Each line segment between two adjacent vertices is labeled by an integer from 0 to 9, inclusive. You are given two
- For all i, j such that 0 <= i <= N and 0 <= j <= M-1, there is a line segment between the points (i,j) and (i,j+1). This line segment has the label horizontal[i][j].
- For all i, j such that 0 <= i <= N-1 and 0 <= j <= M, there is a line segment between the points (i,j) and (i+1,j). This line segment has the label vertical[i][j].
To unlock this board, you must put your finger on the point (0, 0), and move to the point (N, M). In each step you can only go down or right. I.e., if you are currently at the point (i,j), your next step may take you either to (i,j+1), or to (i+1,j). By moving your finger you picked one of the paths from the top left to the bottom right corner. The path consists of N+M line segments, and each of those line segments has an integer label. The cost of a path is the sum of those labels. Let S be the smallest value among the costs of all valid paths from the top left to the bottom right corner. Inside the board there is a counter that computes the sum of all numbers that are on the line segments you used in your path. The lock will open if and only if you picked a path with cost exactly S, i.e., a path with the smallest possible cost.
Finding the way to unlock a given board is a shortest path problem. You could surely solve it, but Ciel is just a young fox. She does not know any complicated algorithms such as Dijkstra, Bellman-Ford, or Floyd-Warshall. Thus unlocking the board is too hard for her. She wants you to modify her board to a state in which it can be unlocked by any path from the top left to the bottom right corner. In other words, on the resulting board all valid paths must have exactly the same cost T. The only allowed operation is to increase some of the labels. (The new labels must again be integers, but they are allowed to exceed 9.) Compute and return the smallest possible value of T.
Notes
- Note that Ciel can always achieve her goal: for example, she can increase every number to X, where X is the maximal number over all numbers on the board.
Constraints
- N and M will be between 1 and 40, inclusive.
- horizontal will contain N+1 elements.
- Each element of horizontal will contain M characters.
- vertical will contain N elements.
- Each element of vertical will contain M+1 characters.
- Each character in each element of horizontal and vertical will be a digit: '0'-'9'.
Examples
0)
{"1","4"}
{"32"}
Returns: 7
We have two possible paths. One of them has the cost 1+2 = 3, the other one 3+4 = 7. As the costs are not equal, we have to modify some of the labels. One possible solution is to increase the label 1 to 5. Then both paths have the same cost: 7.
1)
{"47", "59"}
{"361"}
Returns: 19
This is how the grid looks like: +--4--+--7--+ | | | 3 6 1 | | | +--5--+--9--+ One possible solution is to increase 3 to 5 and 7 to 14.
2)
{"36", "23", "49"}
{"890", "176"}
Returns: 28
3)
{"8888585","5888585"}
{"58585858"}
Returns: 58
4)
{"7777777","7777777","7777777","7777777"}
{"44444444","44444444","44444444"}
Returns: 61
Submissions are judged against all 130 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PasswordXGrid with a public method int minSum(vector<string> horizontal, vector<string> vertical) · 130 test cases · 2 s / 256 MB per case