ZeroBoard
SRM 812 · 2021-08-31 · by misof
Problem Statement
Given is a rectangular board with R rows by C columns. Rows and columns are both numbered starting from zero. Each cell of the board contains a non-negative integer. Initially, the cell in row r, column c contains the integer data[r*C+c].
You are allowed to modify the board in a sequence of steps. In each step you can select two horizontally or vertically adjacent cells and increment both of them by the same integer amount. After each step all values on the board must remain non-negative.
Your goal is to set all numbers in the given board to zeros.
Each turn can be described by four integers {r, c, d, a}. Here:
- (r,c) are the coordinates of the top left cell you want to modify
- d is the direction to the next cell: d=0 means the second cell is (r+1,c) and d=1 means it is (r,c+1)
- a is the (possibly negative) amount added to both cells
If the goal cannot be achieved, return {-1}.
If the goal can be achieved, for the constraints used in this problem there is always a sequence of at most 500 steps that does so, and in each step the absolute value of a is at most 10^6.
Find and report any such sequence.
Return a
Constraints
- R will be positive.
- C will be positive.
- R*C will be between 2 and 200, inclusive.
- data will have exactly R*C elements.
- Each element of data will be between 0 and 1000, inclusive.
3
4
{0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0}
Returns: { }
This board is all zeros, no actions needed.
3
4
{1, 2, 1, 0,
0, 4, 6, 0,
0, 0, 2, 0}
Returns: {0, 0, 1, -1, 0, 1, 0, -1, 1, 1, 1, -3, 0, 2, 0, -1, 1, 2, 0, -2 }
As shown by the sample answer, this board can be solved by just decreasing the values of suitably chosen pairs of cells. The series of operations performed is as follows: {0, 0, 1, -1}: add -1 to the first two cells in the top row {0, 1, 0, -1}: add -1 to the first two cells in the second column from the left {1, 1, 1, -3}: add -3 to the two cells in the center of the middle row {0, 2, 0, -1}: add -1 to the top two cells in the only column with non-zero cells {1, 2, 0, -2}: add -2 to the bottom two cells in the same column
1
2
{4, 7}
Returns: {-1 }
Clearly there is no way to turn both these cells to zeros at the same time.
2
2
{1, 2,
0, 1}
Returns: {1, 0, 1, 1, 0, 0, 0, -1, 0, 1, 0, -2 }
This example output illustrates a solution that also actually increases the values of two cells in one of the steps: we first increment the second row to {1, 2}, which then means that in each column we have two equal values. Also note that you are not required to find the solution with the smallest number of steps. (Ours has three steps, the shortest possible solution would have only two.)
1
2
{0, 0}
Returns: { }
Submissions are judged against all 143 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ZeroBoard with a public method vector<int> solve(int R, int C, vector<int> data) · 143 test cases · 2 s / 256 MB per case