RectangularSum | Topcoder Archive

Problem Statement

Consider the following table:

The table has height rows and width columns. Rows and columns are each numbered sequentially, starting from 0. For each i, j: the cell in row i, column j contains the number (i*width+j). For example, the table with height=2 and width=3 looks as follows:

0 1 2
3 4 5

A subtable of this table is any table that can be obtained from the original table by selecting a rectangle of cells and erasing everything outside the rectangle.

You are given the ints height and width, and a long S. If there is no subtable in which the elements sum to S, return -1. Otherwise, return the smallest possible area of such a subtable.

Definition

Class:: RectangularSum
Method:: minimalArea
Parameters:: int, int, long
Returns:: long
Method signature:: long minimalArea(int height, int width, long S)
(be sure your method is public)

Constraints

height will be between 1 and 1,000,000 (10^6), inclusive.
width will be between 1 and 1,000,000 (10^6), inclusive.
S will be between 1 and 1,000,000,000,000 (10^12), inclusive.

Examples

```
2
```
```
3
```
```
8
```
```
Returns: 4
```
The following subtable (shown in bold italic) has a sum of 8: 0 1 2 3 4 5
```
3
```
```
3
```
```
10
```
```
Returns: -1
```
```
3
```
```
3
```
```
36
```
```
Returns: 9
```
```
25
```
```
25
```
```
16000
```
```
Returns: 32
```
```
1000000
```
```
1000000
```
```
1000000000000
```
```
Returns: 2
```

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)2024, Topcoder, Inc. All rights reserved.