PrettyPicture | Topcoder Archive

Problem Statement

We want to take a picture of the night sky.

For the purpose of this problem, the night sky is a rectangular array of cells with R rows and C columns. There is at most one star in each cell.

Our camera can take a shot of any rectangular area of the sky. The area in the picture will cover exactly PR consecutive rows and PC consecutive columns of the sky. Calculate and return the maximum number of stars in the picture.

Use the following pseudocode to generate the night sky:


state = seed
for cellr = 0 to R-1:
    for cellc = 0 to C-1:
        state = (state * 1103515245 + 12345) modulo 2^31
        if state &lt; threshold:
            cell with coordinates (cellr, cellc) contains a star
        else:
            cell with coordinates (cellr, cellc) is empty

Definition

Class:: PrettyPicture
Method:: takePicture
Parameters:: int, int, int, int, int, int
Returns:: int
Method signature:: int takePicture(int R, int C, int PR, int PC, int seed, int threshold)
(be sure your method is public)

Notes

The reference solution does not depend on the sky being pseudorandom, it would correctly solve any input of the size allowed by the Constraints.

Constraints

1 <= PR <= R <= 4000
1 <= PC <= C <= 4000
seed will be between 0 and 2^31 - 1, inclusive.
threshold will be between 0 and 2^31 - 1, inclusive.

Examples

```
5
```
```
7
```
```
2
```
```
3
```
```
47
```
```
1000000000
```
```
Returns: 4
```
The generated night sky is shown below ('*' are stars, '.' are empty cells). **.*.*. .**.**. ....... .*.*..* ..*..** One optimal solution is to take a picture of the 2x3 area in the top left corner. Another optimal solution is to take a picture of the area in rows 0-1 and columns 3-5. Both pictures will contain 4 stars. For debugging, the variable "state" is assigned the following values during the generation of the night sky:325621308, 263614405, 1041878298, 160854091, 1346820648, 663962433, 1031250150, 1993983527, 507736276, 118477437, 1569514866, 722640323, 181454400, 1288444281, 1329587902, 1802982175, 1176241772, 1198249013, 1502589130, 1883767355, 1945705816, 1376943793, 39849878, 1806337815, 529446660, 2090816749, 2013630242, 575045043, 1036140400, 2074694377, 126974830, 1906393615, 1784930972, 473642149, 735961210.
```
7
```
```
5
```
```
2
```
```
3
```
```
47
```
```
1000000000
```
```
Returns: 3
```
This time the night sky looks as follows: **.*. *..** .**.. ..... ..*.* ..*.. *..** There are many ways to take a picture with 3 stars but nothing better than that.
```
400
```
```
700
```
```
200
```
```
350
```
```
47474747
```
```
3331
```
```
Returns: 0
```
We can take a picture of a quarter of the night sky. The whole sky is empty, so the maximum number of stars in the picture is 0.
```
400
```
```
700
```
```
200
```
```
350
```
```
47474747
```
```
3332
```
```
Returns: 1
```
This test case has the smallest threshold such that there is at least one star in the night sky. There is exactly one star, and all we have to do is to point our camera onto any 200x350 rectangle that contains the star.
```
30
```
```
40
```
```
10
```
```
10
```
```
987654321
```
```
1234567890
```
```
Returns: 68
```
With threshold = 1234567890 each cell contains a star with probability roughly 57.5%, and thus a picture of some random 10x10 section of the night sky will contain about 57.5 stars on average. The number of stars in the best possible picture is somewhat higher than this average.

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.