Statistics

Problem Statement for "DiamondMining"

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

  1. 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

  2. 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.

  3. 4

    4

    11

    65500

    Returns: 0

    No diamonds at all.

  4. 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.

  5. 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.

  6. 500

    600

    42

    2000

    Returns: 129

  7. 1

    1

    42

    50000

    Returns: 0

  8. 1

    1

    42

    5900

    Returns: 1

  9. 750

    750

    42

    5000

    Returns: 49

  10. 748

    741

    22741

    0

    Returns: 371

  11. 747

    5

    24324

    0

    Returns: 3

  12. 1

    744

    16756

    0

    Returns: 1

  13. 601

    688

    1207

    0

    Returns: 301

  14. 748

    747

    23219

    1

    Returns: 374

  15. 741

    1

    20926

    1

    Returns: 1

  16. 1

    748

    32044

    1

    Returns: 1

  17. 472

    254

    20638

    1

    Returns: 127

  18. 746

    750

    31769

    2

    Returns: 373

  19. 744

    5

    10857

    2

    Returns: 3

  20. 5

    750

    29825

    2

    Returns: 3

  21. 121

    148

    15596

    2

    Returns: 61

  22. 745

    742

    493

    10

    Returns: 371

  23. 742

    5

    10872

    10

    Returns: 3

  24. 5

    749

    13442

    10

    Returns: 3

  25. 642

    108

    15961

    10

    Returns: 54

  26. 741

    749

    1332

    50

    Returns: 371

  27. 750

    2

    26801

    50

    Returns: 1

  28. 4

    743

    24434

    50

    Returns: 2

  29. 526

    299

    15958

    50

    Returns: 150

  30. 744

    750

    23667

    100

    Returns: 371

  31. 743

    5

    17636

    100

    Returns: 3

  32. 3

    742

    11024

    100

    Returns: 2

  33. 676

    423

    20765

    100

    Returns: 212

  34. 741

    743

    2003

    1000

    Returns: 244

  35. 742

    1

    19801

    1000

    Returns: 1

  36. 1

    745

    19354

    1000

    Returns: 1

  37. 587

    494

    20358

    1000

    Returns: 207

  38. 747

    749

    9222

    2000

    Returns: 117

  39. 748

    3

    27149

    2000

    Returns: 2

  40. 1

    741

    12174

    2000

    Returns: 1

  41. 166

    210

    2203

    2000

    Returns: 72

  42. 750

    748

    10219

    3000

    Returns: 66

  43. 743

    3

    24987

    3000

    Returns: 2

  44. 3

    744

    12341

    3000

    Returns: 2

  45. 252

    384

    32489

    3000

    Returns: 63

  46. 749

    750

    28914

    5000

    Returns: 49

  47. 743

    5

    3067

    5000

    Returns: 3

  48. 5

    744

    6880

    5000

    Returns: 3

  49. 443

    225

    26011

    5000

    Returns: 42

  50. 750

    743

    25151

    10000

    Returns: 20

  51. 750

    1

    18157

    10000

    Returns: 1

  52. 3

    742

    14063

    10000

    Returns: 2

  53. 304

    662

    20808

    10000

    Returns: 21

  54. 750

    746

    6801

    15000

    Returns: 11

  55. 742

    3

    50

    15000

    Returns: 2

  56. 2

    748

    11414

    15000

    Returns: 1

  57. 650

    552

    20614

    15000

    Returns: 11

  58. 747

    747

    1248

    20000

    Returns: 10

  59. 748

    2

    27008

    20000

    Returns: 1

  60. 1

    749

    28766

    20000

    Returns: 1

  61. 246

    579

    24646

    20000

    Returns: 9

  62. 747

    749

    18376

    25000

    Returns: 6

  63. 741

    2

    10802

    25000

    Returns: 1

  64. 4

    746

    5996

    25000

    Returns: 2

  65. 657

    536

    28638

    25000

    Returns: 7

  66. 748

    744

    22440

    30000

    Returns: 5

  67. 748

    4

    8897

    30000

    Returns: 2

  68. 2

    742

    14467

    30000

    Returns: 1

  69. 337

    416

    26853

    30000

    Returns: 6

  70. 743

    747

    12168

    40000

    Returns: 3

  71. 744

    1

    5622

    40000

    Returns: 1

  72. 5

    746

    15818

    40000

    Returns: 2

  73. 679

    161

    28353

    40000

    Returns: 3

  74. 750

    748

    29885

    50000

    Returns: 3

  75. 744

    4

    19419

    50000

    Returns: 2

  76. 3

    745

    19277

    50000

    Returns: 2

  77. 576

    110

    18945

    50000

    Returns: 3

  78. 743

    743

    2382

    65000

    Returns: 1

  79. 748

    2

    629

    65000

    Returns: 1

  80. 5

    743

    7748

    65000

    Returns: 1

  81. 139

    325

    13162

    65000

    Returns: 1

  82. 749

    748

    20756

    65535

    Returns: 1

  83. 741

    2

    16435

    65535

    Returns: 0

  84. 3

    748

    2326

    65535

    Returns: 0

  85. 228

    500

    29395

    65535

    Returns: 1

  86. 747

    745

    11684

    65536

    Returns: 0

  87. 746

    4

    23588

    65536

    Returns: 0

  88. 3

    746

    28699

    65536

    Returns: 0

  89. 183

    399

    1456

    65536

    Returns: 0

  90. 735

    723

    25441

    3421

    Returns: 62

  91. 712

    747

    31234

    1234

    Returns: 155

  92. 734

    750

    24324

    432

    Returns: 353

  93. 1

    1

    0

    50000

    Returns: 0

  94. 750

    750

    37777

    12345

    Returns: 13

  95. 733

    749

    63987

    8067

    Returns: 25

  96. 750

    750

    0

    65535

    Returns: 1

  97. 750

    750

    10

    1000

    Returns: 259

  98. 750

    750

    47

    1000

    Returns: 259

  99. 750

    750

    5436

    0

    Returns: 375

  100. 750

    750

    1

    100

    Returns: 374

  101. 750

    750

    124

    30000

    Returns: 6

  102. 750

    750

    2354

    1000

    Returns: 259

  103. 750

    750

    47

    32000

    Returns: 6

  104. 741

    742

    16435

    10000

    Returns: 18

  105. 750

    750

    278

    1000

    Returns: 259

  106. 750

    750

    1

    0

    Returns: 375

  107. 749

    749

    1091

    1823

    Returns: 128

  108. 730

    730

    1221

    2000

    Returns: 128

  109. 750

    750

    11

    103

    Returns: 371

  110. 741

    742

    16435

    5000

    Returns: 39

  111. 750

    750

    42

    40000

    Returns: 4

  112. 750

    749

    12345

    30

    Returns: 375

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.
This problem was used for: