TopCoder problem "DiamondMining" used in TCHS09 Round 3 (Division I Level Three)



Problem Statement

    

A diamond mine is a matrix of ones and zeroes with R rows and C columns.

A diamond is a pattern of ones forming the boundary of a 45-degree rotated square. The diamonds of size 1, 2, and 3 are shown below. 

size 1:   size 2:      size 3:
                          1
             1           1 1
   1        1 1         1   1
             1           1 1
                          1

The diamond mine in this problem will be pseudo-randomly generated using the following method:

You are given two ints: seed and threshold. Let x0=seed and for all i>=0 let xi+1 = (xi * 25173 + 13849) modulo 65536.

Process the cells of the matrix in row major order (i.e., first row left to right, second row left to right, etc.). Each time you process a cell, look at the next xi (starting with x1 for the upper left corner). If it is greater than or equal to threshold, the current cell will contain a 1, otherwise it will contain a 0.

Your method shall compute and return the size of the largest diamond that can be found in the mine. If there are no diamonds, return 0.

 

Definition

    
Class:DiamondMining
Method:largestDiamond
Parameters:int, int, int, int
Returns:int
Method signature:int largestDiamond(int R, int C, int seed, int threshold)
(be sure your method is public)
    
 

Notes

-The random generation of the input is only for keeping the input size small. The author's solution does not depend on any properties of the generator, and would work fast enough for any input of allowed dimensions.
 

Constraints

-R will be between 1 and 750, inclusive.
-C will be between 1 and 750, inclusive.
-seed will be between 0 and 65,535, inclusive.
-threshold will be between 0 and 65,536, inclusive.
 

Examples

0)
    
5
5
47
20598
Returns: 3
The generated pseudo-random sequence is 17332, 39133, 37242, 14235, 656, 12265, 20598, 6471, 51372, 44853, 44210, 45363, 37384, 49857, 49710, 19295, 39588, 22157, 60650, 29643, 24192, 38553, 51430, 63095, and 39324.

The resulting diamond mine looks as follows: 
0 1 1 0 0
0 1 0 1 1
1 1 1 1 1
0 1 1 1 1
1 1 1 1 1
1)
    
5
5
47
20599
Returns: 2
The pseudo-random sequence is the same, but the threshold is larger. The only change in the resulting diamond mine is that now the cell in row 2, column 2 contains a 0, and therefore there is no diamond of size 3.
2)
    
4
4
11
65500
Returns: 0
No diamonds at all.
3)
    
3
6
47
15000
Returns: 2
1 1 1 0 0 0
1 0 1 1 1 1
1 1 1 1 1 1
The only diamond of size 2 is located on the left side of the mine.
4)
    
200
300
42
0
Returns: 100
Regardless of the seed, if the threshold is 0, each cell contains a 1. Therefore the size of the largest diamond is only limited by the dimensions of the mine.
5)
    
741
2
16435
65535
Returns: 0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13730&pm=10286

Writer:

misof

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming