Connection Status:
Competition Arena > SumRectangle

SumRectangle

TCO10 Qual 3 · 2010-04-11 · by misof

TCO10 Qual 3 · 2010-04-11 · by misof · Simple Math, Simple Search, Iteration
Class Name: SumRectangle
Return Type: int
Method Name: getCorner
Arg Types: (vector<int>, vector<int>)
Problem Statement

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.

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

3)
{47}
{47}
Returns: 47
4)
{47,42}
{47}
Returns: 42

Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SumRectangle with a public method int getCorner(vector<int> leftColumn, vector<int> topRow) · 50 test cases · 2 s / 256 MB per case

Submitting as anonymous