TopCoder problem "SumRectangle" used in TCO10 Qual 3 (Division I Level One)



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 int[] leftColumn containing the leftmost number in each row of our rectangle, from the top to the bottom. You will also be given an int[] 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:int[], int[]
Returns:int
Method signature:int getCorner(int[] leftColumn, int[] topRow)
(be sure your method is public)
    
 

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 | ?? |
+----+----+

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10948

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14278&pm=10948

Writer:

misof

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Simple Math, Simple Search, Iteration