Statistics

Problem Statement for "RectangularSum"

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

  1. 2

    3

    8

    Returns: 4

    The following subtable (shown in bold italic) has a sum of 8: 0 1 2 3 4 5

  2. 3

    3

    10

    Returns: -1

  3. 3

    3

    36

    Returns: 9

  4. 25

    25

    16000

    Returns: 32

  5. 1000000

    1000000

    1000000000000

    Returns: 2

  6. 6

    6

    236

    Returns: 8

  7. 1000000

    1000000

    963761198400

    Returns: 1

  8. 100000

    100000

    963761198400

    Returns: 99

  9. 565

    1000000

    248928394289

    Returns: -1

  10. 50000

    50000

    963761198400

    Returns: 390

  11. 50000

    50000

    9637611984

    Returns: 4

  12. 70000

    5904

    963761198400

    Returns: 2340

  13. 50000

    50000

    123123123

    Returns: 1

  14. 12

    17

    4234234223

    Returns: -1

  15. 2

    3

    1

    Returns: 1

  16. 2

    3

    2

    Returns: 1

  17. 2

    3

    3

    Returns: 1

  18. 2

    3

    4

    Returns: 1

  19. 2

    3

    5

    Returns: 1

  20. 2

    3

    6

    Returns: -1

  21. 2

    3

    7

    Returns: 2

  22. 2

    3

    8

    Returns: 4

  23. 2

    3

    9

    Returns: 2

  24. 2

    3

    10

    Returns: -1

  25. 2

    3

    11

    Returns: -1

  26. 2

    3

    12

    Returns: 3

  27. 2

    3

    13

    Returns: -1

  28. 2

    3

    14

    Returns: -1

  29. 2

    3

    15

    Returns: 6

  30. 2

    3

    16

    Returns: -1

  31. 42

    68

    9190

    Returns: 4

  32. 1

    70

    15794

    Returns: -1

  33. 79

    59

    31623

    Returns: -1

  34. 65

    6

    28535

    Returns: -1

  35. 82

    28

    12257

    Returns: 7

  36. 92

    96

    20774

    Returns: 4

  37. 28

    37

    33427

    Returns: -1

  38. 5

    3

    168

    Returns: -1

  39. 93

    83

    25140

    Returns: 4

  40. 17

    19

    20218

    Returns: -1

  41. 48

    27

    16067

    Returns: -1

  42. 39

    70

    22642

    Returns: -1

  43. 68

    100

    23835

    Returns: 5

  44. 95

    4

    24191

    Returns: -1

  45. 23

    34

    18455

    Returns: -1

  46. 65

    42

    10441

    Returns: -1

  47. 54

    69

    29273

    Returns: -1

  48. 45

    63

    35592

    Returns: 16

  49. 38

    60

    11003

    Returns: -1

  50. 42

    30

    2038

    Returns: 2

  51. 17

    36

    22802

    Returns: -1

  52. 43

    89

    33933

    Returns: -1

  53. 41

    43

    21027

    Returns: -1

  54. 49

    47

    26108

    Returns: -1

  55. 91

    30

    27100

    Returns: 10

  56. 51

    7

    31458

    Returns: 196

  57. 94

    49

    24235

    Returns: 10

  58. 24

    85

    21994

    Returns: 28

  59. 57

    41

    7303

    Returns: -1

  60. 77

    32

    28772

    Returns: -1

  61. 63482

    94225

    999663028876

    Returns: 3121

  62. 4074

    60573

    999995109149

    Returns: -1

  63. 71118

    92081

    999999402994

    Returns: -1

  64. 32966

    61984

    999881658478

    Returns: 1403

  65. 29668

    7604

    999831455710

    Returns: -1

  66. 78456

    79774

    999883247749

    Returns: 619

  67. 67152

    41086

    999742344217

    Returns: -1

  68. 98273

    84884

    999959126020

    Returns: 136

  69. 79569

    81337

    999346647970

    Returns: 220

  70. 48181

    73202

    999913453636

    Returns: 428

  71. 952

    69065

    999963370784

    Returns: 16592

  72. 13693

    54138

    999880744094

    Returns: 3169

  73. 80606

    73769

    999862416538

    Returns: 2969

  74. 64698

    60325

    999855671355

    Returns: -1

  75. 799

    98707

    999915838336

    Returns: 19648

  76. 83102

    32548

    999631597030

    Returns: 370

  77. 8963

    3875

    999952096620

    Returns: -1

  78. 69445

    48297

    999711840601

    Returns: -1

  79. 77215

    67107

    999839796788

    Returns: 196

  80. 19594

    83792

    999968948890

    Returns: 1523

  81. 37815

    37760

    999888488605

    Returns: 5113

  82. 18992

    67685

    999889599484

    Returns: 856

  83. 65921

    56739

    999999894053

    Returns: -1

  84. 72985

    65544

    999944478896

    Returns: 304

  85. 78792

    51128

    999782957118

    Returns: -1

  86. 96280

    95850

    999478726436

    Returns: 20101

  87. 54019

    63362

    999509829722

    Returns: 36551

  88. 52669

    92977

    999721429058

    Returns: -1

  89. 3059

    18237

    999773871762

    Returns: -1

  90. 40032

    81727

    999772130904

    Returns: 488

  91. 63482

    94225

    963761198400

    Returns: 165

  92. 98087

    95266

    963761198400

    Returns: 104

  93. 59349

    82488

    963761198400

    Returns: 198

  94. 71964

    84962

    963761198400

    Returns: 160

  95. 32966

    61984

    963761198400

    Returns: 475

  96. 56294

    84435

    963761198400

    Returns: 204

  97. 33469

    11294

    963761198400

    Returns: 2550

  98. 7900

    25336

    963761198400

    Returns: 4830

  99. 67152

    41086

    963761198400

    Returns: 350

  100. 64507

    60768

    963761198400

    Returns: 247

  101. 1251

    60603

    963761198400

    Returns: 12768

  102. 54945

    20814

    963761198400

    Returns: 850

  103. 48181

    73202

    963761198400

    Returns: 275

  104. 65994

    32287

    963761198400

    Returns: 455

  105. 76007

    81365

    963761198400

    Returns: 156

  106. 71043

    16990

    963761198400

    Returns: 800

  107. 80606

    73769

    963761198400

    Returns: 165

  108. 6167

    93917

    963761198400

    Returns: 1664

  109. 36800

    49453

    963761198400

    Returns: 532

  110. 74608

    92094

    963761198400

    Returns: 143

  111. 83102

    32548

    963761198400

    Returns: 357

  112. 7002

    23351

    963761198400

    Returns: 5928

  113. 40251

    27202

    963761198400

    Returns: 884

  114. 60817

    11495

    963761198400

    Returns: 1380

  115. 77215

    67107

    963761198400

    Returns: 187

  116. 30719

    90559

    963761198400

    Returns: 351

  117. 50663

    19910

    963761198400

    Returns: 960

  118. 35637

    2427

    963761198400

    Returns: 11200

  119. 18992

    67685

    963761198400

    Returns: 756

  120. 27865

    2417

    963761198400

    Returns: 14352

  121. 1000000

    1000000

    900000000090

    Returns: 1

  122. 2

    2

    6

    Returns: 4

  123. 80000

    80000

    802241960520

    Returns: 130

  124. 1000

    1000

    401567166000

    Returns: 579462

  125. 98765

    5765

    90816827608

    Returns: 208

  126. 1000

    1000

    321253732800

    Returns: 434700

  127. 999996

    999997

    999999999993

    Returns: 2

  128. 100000

    100000

    1000000000

    Returns: 1

  129. 1000

    2000

    887674788000

    Returns: 516672

  130. 100000

    1000000

    963761198400

    Returns: 10

  131. 1000000

    1

    499999500000

    Returns: 999999

  132. 500000

    500001

    900000000001

    Returns: -1

  133. 100000

    100000

    900000000001

    Returns: -1

  134. 3

    2

    15

    Returns: 6

  135. 1000000

    1000000

    84695000

    Returns: 1

  136. 3

    1001

    4507503

    Returns: 3003

  137. 2

    4

    11

    Returns: 2

  138. 2

    2

    4

    Returns: 2

  139. 1000

    1000

    499999500000

    Returns: 1000000

  140. 5

    1

    10

    Returns: 4

  141. 1

    1000000

    5000050000

    Returns: 6875

  142. 213214

    321432

    900000000010

    Returns: 20

  143. 1

    1

    843291048600

    Returns: -1

  144. 7

    7

    468

    Returns: -1

  145. 1000000

    2

    864071988000

    Returns: 551616

  146. 997920

    997920

    963761198400

    Returns: 1

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: