Statistics

Problem Statement for "MaximizeSquares"

Problem Statement

Consider an arrangement of N points on the cartesian plane. The "square count" of the points is the total number of distinct squares with sides parallel to the coordinate axes which can be built using 4 different points as vertices. Your task is to return the maximum square count, considering all possible arrangements of N points on the plane.

Definition

Class:
MaximizeSquares
Method:
squareCount
Parameters:
int
Returns:
int
Method signature:
int squareCount(int N)
(be sure your method is public)

Notes

  • Two squares are distinct if at least one of their corners is in a different location.

Constraints

  • N will be between 0 and 1000000, inclusive.

Examples

  1. 4

    Returns: 1

    Clearly, we can only make one square out of 4 points.

  2. 5

    Returns: 1

    No matter where we place a fifth point, we can't get any extra squares.

  3. 6

    Returns: 2

    We can get 2 squares by placing the points in the shape of a rectangle.

  4. 16

    Returns: 14

  5. 1000000

    Returns: 332833500

  6. 11

    Returns: 6

  7. 12

    Returns: 8

  8. 15

    Returns: 11

  9. 8

    Returns: 3

  10. 82

    Returns: 204

  11. 999999

    Returns: 332832501

  12. 4651

    Returns: 102861

  13. 658026

    Returns: 177521545

  14. 0

    Returns: 0

  15. 1

    Returns: 0

  16. 2

    Returns: 0

  17. 3

    Returns: 0

  18. 105

    Returns: 295

  19. 637

    Returns: 4966

  20. 14642

    Returns: 583220

  21. 24

    Returns: 26

  22. 34

    Returns: 46

  23. 998001

    Returns: 331835499

  24. 998002

    Returns: 331835499

  25. 998768

    Returns: 332129260

  26. 115

    Returns: 340

  27. 40200

    Returns: 2666600

  28. 40201

    Returns: 2666600

  29. 40199

    Returns: 2666401

  30. 40259

    Returns: 2668311

  31. 383492

    Returns: 78922024

  32. 526898

    Returns: 127175678

  33. 800695

    Returns: 238331360

  34. 283094

    Returns: 50050581

  35. 274606

    Returns: 47822509

  36. 112973

    Returns: 12590886

  37. 822200

    Returns: 247996823

  38. 765493

    Returns: 222817903

  39. 87508

    Returns: 8574938

  40. 313087

    Returns: 58226521

  41. 681

    Returns: 5535

  42. 2192

    Returns: 32865

  43. 3200

    Returns: 58548

  44. 6493

    Returns: 170718

  45. 7501

    Returns: 212161

  46. 794

    Returns: 6975

  47. 1802

    Returns: 24524

  48. 2810

    Returns: 48230

  49. 8388

    Returns: 251280

  50. 9396

    Returns: 298366

  51. 404

    Returns: 2476

  52. 6409

    Returns: 167516

  53. 6288

    Returns: 162320

  54. 2726

    Returns: 45757

  55. 589

    Returns: 4402

  56. 9312

    Returns: 294880

  57. 320

    Returns: 1723

  58. 3109

    Returns: 55846

  59. 4117

    Returns: 85554

  60. 9191

    Returns: 288245

  61. 7914

    Returns: 230449

  62. 1207

    Returns: 13226

  63. 2215

    Returns: 33526

  64. 5004

    Returns: 114871

  65. 6012

    Returns: 152167

  66. 4734

    Returns: 105649

  67. 2094

    Returns: 30636

  68. 816

    Returns: 7314

  69. 3606

    Returns: 70225

  70. 4613

    Returns: 101828

  71. 3336

    Returns: 62147

  72. 8410

    Returns: 251863

  73. 7133

    Returns: 196980

  74. 2207

    Returns: 33420

  75. 930

    Returns: 8990

  76. 1938

    Returns: 27435

  77. 35110

    Returns: 2172151

  78. 744336

    Returns: 213593257

  79. 687629

    Returns: 189639192

  80. 630923

    Returns: 166658650

  81. 292930

    Returns: 52664766

  82. 952938

    Returns: 309493941

  83. 896231

    Returns: 282264426

  84. 557239

    Returns: 138369848

  85. 218247

    Returns: 33852624

  86. 161540

    Returns: 21550553

  87. 104833

    Returns: 11248938

  88. 48126

    Returns: 3490739

  89. 709134

    Returns: 198642586

  90. 652427

    Returns: 175254347

  91. 79368

    Returns: 7403795

  92. 256728

    Returns: 43201775

  93. 248240

    Returns: 41072475

  94. 909247

    Returns: 288510978

  95. 618474

    Returns: 161783288

  96. 174556

    Returns: 24201557

  97. 835564

    Returns: 254113797

  98. 778857

    Returns: 228710637

  99. 439865

    Returns: 96968735

  100. 383158

    Returns: 78865558

  101. 326451

    Returns: 61977390

  102. 269744

    Returns: 46538012

  103. 930752

    Returns: 298734246

  104. 874045

    Returns: 271877825

  105. 583271

    Returns: 148122019

  106. 526564

    Returns: 127048591

  107. 239566

    Returns: 38956034

  108. 333

    Returns: 1821

  109. 993337

    Returns: 329401630

  110. 999987

    Returns: 332820591

  111. 49320

    Returns: 3623041

  112. 14

    Returns: 9

  113. 19

    Returns: 17

  114. 10

    Returns: 5

  115. 998005

    Returns: 331835505

  116. 999998

    Returns: 332831503

  117. 17

    Returns: 14

  118. 88

    Returns: 225

  119. 29

    Returns: 36

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: