Statistics

Problem Statement for "MergeToSort"

Problem Statement

Given is a sequence A consisting of N positive integers. You would like to transform it into a sequence that is sorted in non-decreasing order.

The only allowed transformation step is taking two consecutive elements and replacing them by their sum.

Find and return the minimum number of steps needed.


In order to keep the input size small, the sequence is constructed pseudorandomly using the pseudocode given below. In the pseudocode, x^y denotes x to the power of y. 

L = length(Aprefix)
for i = 0 to L-1:
    A[i] = Aprefix[i]

state = seed
for i = L to N-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    b = blo + ((state / 1000) modulo (bhi-blo+1))

    state = (state * 1103515245 + 12345) modulo 2^31
    x = 2^(b-1)
    A[i] = x + ((state / 10) modulo x)

Definition

Class:
MergeToSort
Method:
minSteps
Parameters:
int, int[], int, int, int
Returns:
int
Method signature:
int minSteps(int N, int[] Aprefix, int seed, int blo, int bhi)
(be sure your method is public)

Notes

  • It can easily be shown that a solution always exists.
  • The reference solution does not depend on the input being (pseudo)random.
  • The constraints imply that all elements of A will satisfy 1 <= A[i] < 2^25.

Constraints

  • N will be between 1 and 100,000, inclusive.
  • Aprefix will have between 0 and 100 elements, inclusive.
  • Aprefix will have at most N elements.
  • Each element of Aprefix will be between 1 and 2^25 - 1, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.
  • blo and bhi will satisfy 1 <= blo <= bhi <= 25.

Examples

  1. 4

    {20, 10, 35, 38}

    0

    1

    1

    Returns: 1

    The optimal solution is to merge the first two elements, producing the sorted sequence {30, 35, 38}.

  2. 5

    {10, 10, 10, 10}

    47

    15

    25

    Returns: 0

    The sequence {10, 10, 10, 10, 26361440} is already in non-decreasing order, no changes are needed.

  3. 15

    {420, 470}

    420047

    9

    10

    Returns: 7

    A = {420, 470, 547, 689, 892, 890, 822, 931, 488, 607, 354, 943, 315, 914, 321}

  4. 100000

    {}

    436734

    1

    25

    Returns: 99717

  5. 100000

    {}

    252

    1

    1

    Returns: 0

  6. 12

    {348, 297, 357, 240, 196, 327, 262, 265, 380, 85, 279, 402}

    0

    1

    1

    Returns: 8

  7. 1

    {105}

    0

    1

    1

    Returns: 0

  8. 9

    {981, 989, 983, 966, 976, 984, 979, 973, 973}

    0

    1

    1

    Returns: 4

  9. 17

    {481, 429, 376, 511, 463, 458, 521, 455, 510, 515, 418, 429, 377, 400, 453, 393, 460}

    0

    1

    1

    Returns: 11

  10. 19

    {457, 417, 451, 478, 448, 513, 421, 499, 483, 466, 454, 459, 484, 403, 516, 472, 494, 459, 449}

    0

    1

    1

    Returns: 11

  11. 20

    {329, 505, 614, 376, 269, 571, 132, 291, 201, 193, 389, 640, 604, 563, 491, 150, 388, 600, 439, 139}

    0

    1

    1

    Returns: 12

  12. 19

    {239, 244, 228, 228, 247, 229, 225, 223, 225, 239, 242, 223, 234, 245, 217, 224, 243, 221, 240}

    0

    1

    1

    Returns: 12

  13. 1

    {78}

    0

    1

    1

    Returns: 0

  14. 6

    {737, 649, 575, 724, 721, 731}

    0

    1

    1

    Returns: 3

  15. 16

    {537, 537, 466, 474, 487, 484, 534, 508, 470, 495, 472, 513, 480, 467, 476, 503}

    0

    1

    1

    Returns: 9

  16. 2

    {719, 684}

    0

    1

    1

    Returns: 1

  17. 20

    {888, 790, 892, 900, 821, 910, 898, 772, 896, 877, 839, 894, 765, 781, 857, 858, 842, 829, 896, 877}

    0

    1

    1

    Returns: 13

  18. 20

    {131, 80, 125, 124, 68, 121, 138, 132, 74, 102, 128, 130, 80, 97, 111, 108, 87, 125, 68, 141}

    0

    1

    1

    Returns: 13

  19. 4

    {588, 541, 634, 610}

    0

    1

    1

    Returns: 2

  20. 1

    {670}

    0

    1

    1

    Returns: 0

  21. 10

    {311, 597, 536, 434, 112, 781, 153, 575, 768, 646}

    0

    1

    1

    Returns: 5

  22. 20

    {536, 539, 512, 526, 508, 515, 538, 532, 546, 546, 502, 535, 529, 494, 551, 549, 495, 521, 540, 508}

    0

    1

    1

    Returns: 13

  23. 13

    {892, 709, 452, 436, 777, 710, 392, 699, 937, 398, 742, 615, 601}

    0

    1

    1

    Returns: 8

  24. 7

    {274, 253, 271, 271, 255, 222, 234}

    0

    1

    1

    Returns: 4

  25. 19

    {15, 217, 444, 235, 267, 225, 315, 418, 441, 132, 151, 53, 156, 64, 478, 87, 217, 173, 255}

    0

    1

    1

    Returns: 12

  26. 14

    {756, 824, 766, 510, 561, 809, 264, 864, 930, 629, 849, 844, 954, 850}

    0

    1

    1

    Returns: 8

  27. 20

    {788, 758, 564, 822, 832, 666, 890, 494, 565, 786, 565, 792, 512, 721, 683, 503, 587, 709, 563, 779}

    0

    1

    1

    Returns: 14

  28. 13

    {147, 79, 578, 403, 5, 398, 516, 471, 387, 130, 528, 415, 109}

    0

    1

    1

    Returns: 8

  29. 3

    {641, 712, 484}

    0

    1

    1

    Returns: 1

  30. 20

    {861, 690, 667, 629, 790, 275, 584, 717, 697, 515, 622, 381, 503, 586, 256, 315, 909, 679, 521, 845}

    0

    1

    1

    Returns: 13

  31. 17

    {461, 282, 350, 266}

    963098471

    3

    20

    Returns: 10

  32. 30

    {475, 347, 581, 655, 607, 372, 472, 526, 274, 503, 247, 362, 584, 306, 465, 572, 339}

    30401546

    16

    20

    Returns: 19

  33. 36

    {721, 530, 730, 693, 601, 820, 813, 464, 582, 442, 490, 712, 464, 532, 842, 853, 503, 450, 482}

    710429624

    6

    24

    Returns: 27

  34. 17

    {120, 117, 102}

    942936922

    10

    18

    Returns: 11

  35. 29

    {749, 414, 197, 129, 299, 665, 231, 431, 186, 419, 772, 532}

    1512485082

    18

    19

    Returns: 20

  36. 21

    {517, 492, 491, 522, 488, 529, 498, 438, 460, 477, 442, 512, 490, 448, 492, 510, 451}

    253456038

    11

    14

    Returns: 11

  37. 18

    {854, 978, 911, 927, 996, 939, 928, 984, 939, 837, 865}

    2119888712

    1

    21

    Returns: 12

  38. 31

    {837, 313, 938, 442, 220, 194, 910, 765, 451, 191, 803}

    1100292491

    1

    22

    Returns: 24

  39. 22

    {765, 417, 575, 576, 333, 404, 655, 827, 232, 505, 814, 882}

    1815175106

    4

    14

    Returns: 15

  40. 21

    {610, 487, 379, 726, 645, 725, 708, 607, 473, 494, 563, 385, 368, 557}

    1575552978

    14

    25

    Returns: 13

  41. 26

    {264, 316, 125, 124, 333, 227, 123, 174, 195, 207, 307, 332, 192, 242, 94, 149, 97}

    1600605750

    7

    18

    Returns: 17

  42. 36

    {952, 960, 964, 941, 982, 980, 976, 965, 959, 973, 961, 939, 945, 940, 958, 942}

    14434277

    7

    17

    Returns: 26

  43. 15

    {869, 593}

    820206654

    15

    25

    Returns: 10

  44. 20

    {975, 935, 688}

    280319007

    2

    12

    Returns: 16

  45. 13

    {655, 622, 694, 672, 675, 668, 709, 708, 658, 708}

    1604168383

    9

    14

    Returns: 7

  46. 5

    {580, 477, 538, 402}

    822004006

    19

    22

    Returns: 2

  47. 19

    {273, 232, 445, 447, 442}

    547953963

    19

    24

    Returns: 12

  48. 20

    {786, 786, 763, 773, 780}

    633779308

    9

    21

    Returns: 11

  49. 4

    {288, 172, 113}

    546676137

    4

    5

    Returns: 2

  50. 36

    {912, 947, 952, 928, 945, 937, 953, 949, 878, 896, 951, 944, 949, 893, 904, 890, 894, 911, 953, 936}

    1328065760

    15

    20

    Returns: 23

  51. 27

    {887, 927, 818, 775, 881, 896, 897, 876, 859, 867, 914, 849, 850, 872}

    1154162604

    2

    20

    Returns: 18

  52. 16

    {414, 415, 477, 406, 449}

    633475780

    22

    22

    Returns: 8

  53. 21

    {287}

    2065566509

    2

    14

    Returns: 15

  54. 31

    {272, 184, 194, 204, 236, 166, 178, 267, 237, 271, 174}

    1055259076

    8

    10

    Returns: 21

  55. 23

    {780, 756, 732, 780, 759, 727, 731, 735, 785, 742, 782, 780, 754, 782, 739}

    1633727531

    2

    12

    Returns: 16

  56. 92817

    {}

    731368979

    16

    20

    Returns: 92233

  57. 93167

    {}

    230505136

    13

    24

    Returns: 92774

  58. 97682

    {}

    320615195

    11

    18

    Returns: 97178

  59. 94241

    {}

    894454129

    4

    5

    Returns: 93561

  60. 94484

    {}

    476696165

    13

    20

    Returns: 94007

  61. 94187

    {}

    513778974

    12

    18

    Returns: 93681

  62. 96157

    {}

    966306144

    12

    21

    Returns: 95728

  63. 94766

    {}

    1377899115

    9

    20

    Returns: 94365

  64. 99333

    {}

    891024322

    2

    25

    Returns: 99044

  65. 94853

    {}

    1396738263

    15

    25

    Returns: 94428

  66. 91871

    {}

    786294352

    5

    19

    Returns: 91526

  67. 94266

    {}

    406616854

    9

    11

    Returns: 93635

  68. 94826

    {}

    1162002437

    2

    7

    Returns: 94276

  69. 93556

    {}

    2114618606

    7

    22

    Returns: 93221

  70. 98113

    {}

    99993258

    3

    13

    Returns: 97687

  71. 99712

    {}

    1800951242

    4

    5

    Returns: 99000

  72. 94931

    {}

    815144405

    8

    14

    Returns: 94414

  73. 91411

    {}

    959964665

    7

    21

    Returns: 91065

  74. 98979

    {}

    1800803545

    3

    18

    Returns: 98614

  75. 95063

    {}

    510006733

    11

    12

    Returns: 94401

  76. 91492

    {}

    1952515208

    11

    23

    Returns: 91127

  77. 93471

    {}

    372122540

    4

    25

    Returns: 93176

  78. 98778

    {}

    2079845253

    11

    22

    Returns: 98381

  79. 93586

    {}

    1324603655

    2

    11

    Returns: 93156

  80. 96209

    {}

    254970774

    9

    25

    Returns: 95865

  81. 100000

    {}

    47

    25

    25

    Returns: 99315

  82. 100000

    {20, 10, 35, 38 }

    0

    1

    25

    Returns: 99707

  83. 100000

    {420, 470 }

    420047

    9

    10

    Returns: 99316

  84. 10000

    { }

    254235

    1

    25

    Returns: 9913

  85. 100000

    { }

    4312421

    1

    25

    Returns: 99713

  86. 100000

    { }

    254235

    1

    25

    Returns: 99716

  87. 100000

    {1, 2, 3, 1332 }

    6455645

    1

    25

    Returns: 99721

  88. 90

    {420, 470 }

    420047

    9

    10

    Returns: 72

  89. 100000

    {2, 3 }

    214123

    5

    20

    Returns: 99652

  90. 100000

    {1, 2, 3324 }

    5465123

    1

    25

    Returns: 99717

  91. 4

    {5, 1, 6, 6 }

    1

    1

    1

    Returns: 1

  92. 100000

    { }

    843828734

    5

    25

    Returns: 99698

  93. 1000

    {2724, 7431, 6185, 7177, 7792, 5835, 5835, 3350, 9579, 7655, 5437, 9492, 1656, 3607, 3261, 1147, 8687, 1931, 8458, 8254, 8123, 8176, 2065, 3240, 4614, 6039, 4096, 8952, 948, 7605, 8177, 4502, 4466, 4730, 1556, 4912, 7918, 4956, 5720, 4848, 5333, 3951, 6897, 7144, 8940, 2339, 9861, 458, 1085, 3949, 5089, 9071, 3047, 8399, 6975, 5296, 7786, 2134, 8838, 7290, 4966, 634, 6872, 2737, 1593, 4724, 7137, 3137, 121, 3699, 2348, 8955, 9071, 142, 2342, 9948, 4522, 369, 8716, 3998, 5486, 5087, 728, 2652, 1721, 7957, 759, 132, 3665, 2160, 7859, 2627, 5014, 4947, 4385, 1287, 2730, 9659, 8880, 7039 }

    0

    1

    7

    Returns: 982

  94. 5

    {9, 1, 5, 3, 10 }

    0

    1

    1

    Returns: 2

  95. 100000

    { }

    12345

    25

    25

    Returns: 99305

  96. 100000

    {2, 3 }

    52324

    5

    20

    Returns: 99645

  97. 5

    {1, 2, 1, 4, 4 }

    0

    1

    1

    Returns: 1

  98. 100000

    {2295830, 27071558, 14064113, 8750495, 20756095, 32438782, 22067899, 32545635, 15655341, 6482674, 17142795, 23224801, 15631154, 18574796, 30984789, 27779730, 31712444, 9712045, 6526509, 15751644, 19006158, 19721927, 22998855, 12722524, 19150210, 14395198, 30881746, 14267351, 30596513, 10157982, 3522365, 12078185, 19269905, 11653207, 12108977, 21298177, 7050570, 10884451, 16893462, 12237338, 6723871, 28572429, 19347261, 12433517, 13112866, 2171725, 4143510, 32903092, 28259691, 20315942, 6783585, 15790487, 10057737, 24720012, 12665798, 7437821, 11132554, 14887783, 1235471, 28963631, 1801453, 8327363, 29697545, 24939383, 9144470, 33376399, 25778087, 26770536, 14898687, 3526596, 17812311, 1138788, 10391651, 27523763, 29754092, 16001376, 18824331, 31282034, 13761191, 24239368, 29655551, 8515340, 2672436, 22365756, 14566580, 23252945, 18162345, 15088288, 1092027, 24596916, 30898172, 25496591, 10081066, 1434233, 20712042, 10114751, 19445622, 29890630, 30849941, 31068747 }

    846504639

    24

    25

    Returns: 99310

  99. 5

    {2, 3, 8, 1, 10 }

    0

    1

    1

    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: