PROBLEM STATEMENT
A sum rectangle is a rectangle divided into a grid of unit squares.
Each square contains a number, and the numbers in neighboring squares always satisfy the following
property:
The number in any square S that is neither in the bottom row nor in the right column
can be computed as the sum of the following three numbers:
The number in the square directly below S.
The number in the square directly to the right of S.
The number in the other square adjacent to the previous two squares (the one diagonally down and
to the right of S).
An example of a correctly filled sum rectangle:
+----+----+----+----+----+
| 88 | 57 | 33 | 10 | 5 |
+----+----+----+----+----+
| 18 | 13 | 11 | 12 | -7 |
+----+----+----+----+----+
| 1 | 4 | -2 | 1 | 18 |
+----+----+----+----+----+
For example, in the top left corner we have 88 = 18 + 57 + 13.
We have a secret sum rectangle.
You will be given a vector leftColumn containing the leftmost number in each row of our
rectangle, from the top to the bottom.
You will also be given an vector topRow containing the topmost number in each column of our
rectangle, from the left to the right.
Compute and return the number in the bottom right corner. If the input is such that this number
cannot be determined uniquely, return 0 instead.
DEFINITION
Class:SumRectangle
Method:getCorner
Parameters:vector , vector
Returns:int
Method signature:int getCorner(vector leftColumn, vector topRow)
NOTES
-You may assume that the return value will always fit into an int (i.e., a 32-bit signed integer
data type).
CONSTRAINTS
-leftColumn will contain between 1 and 10 elements, inclusive.
-Each element of leftColumn will be between 0 and 100, inclusive.
-topRow will contain between 1 and 10 elements, inclusive.
-Each element of topRow will be between 0 and 100, inclusive.
-Element 0 of leftColumn will be equal to element 0 of topRow.
EXAMPLES
0)
{88,18,1}
{88,57,33,10,5}
Returns: 18
This is the rectangle from the problem statement. The lower right corner is uniquely determined by
the left column and the top row.
1)
{0,0,0,0}
{0,0,0,0}
Returns: 0
The only correct way to fill this rectangle is to place a zero into each square.
2)
{6,1}
{6,2}
Returns: 3
This is the smallest non-trivial case:
+----+----+
| 6 | 2 |
+----+----+
| 1 | ?? |
+----+----+
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.