Statistics

Problem Statement for "SortingInIterations"

Problem Statement

John is going to sort a sequence of numbers using a special algorithm. First all numbers a[0], a[1], a[2], ..., a[n-1] are written on a blackboard. During the first iteration, John checks all numbers in the order of increasing indices (so, he checks a[0] first, followed by a[1], a[2],..., and ends the first iteration with a[n - 1]). At any moment, he can erase the number he is looking at from the blackboard and write it into his notebook. When looking at number a[i], John erases it from the board and writes into his notebook if and only if it is equal to the smallest unerased number on the blackboard. All other iterations are similar to the first one, but, of course, John checks only the numbers which were not erased from the blackboard. The process is over when all numbers are erased from the board and written into John's notebook in non-descending order.

For example, if John is given a sequence of {3, 5, 1, 4, 2}, the process will go as follows. During the first iteration, John will erase 1 and 2 from the board, writing them to the notebook and changing the sequence to {3, 5, 4}. During the second iteration, 3 and 4 will be written into his notebook, so only 5 will be on the board during the third iteration.

You will be given four ints: a0, X, Y, M, n. The sequence John will need to sort can be generated using the following algorithm:

  • a[0] = a0;
  • a[i] = (a[i - 1] * X + Y) mod M, for 0 &lt i &lt n (where mod is a remainder operation.).
You will be given two more ints start and finish. Return the sum of all numbers John will erase from the board during all iterations with indices (1-based) between start and finish, inclusive. If John will need less than finish iterations to sort the sequence, return -1.

Definition

Class:
SortingInIterations
Method:
sum
Parameters:
int, int, int, int, int, int, int
Returns:
long
Method signature:
long sum(int a0, int X, int Y, int M, int n, int start, int finish)
(be sure your method is public)

Constraints

  • a0 will be between 0 and M-1, inclusive.
  • X will be between 0 and 4*10^5, inclusive.
  • Y will be between 0 and 4*10^5, inclusive.
  • M will be between 1 and 4*10^5, inclusive.
  • n will be between 1 and 4*10^5, inclusive.
  • start will be between 1 and 4*10^5, inclusive.
  • finish will be between start and 4*10^5, inclusive.

Examples

  1. 4

    2

    0

    7

    10

    1

    1

    Returns: 5

    The sequence is 4 1 2 4 1 2 4 1 2 4. The bolded elements will be erased during the first iteration.

  2. 1

    0

    0

    5

    5

    1

    2

    Returns: 1

    The sequence is 1, 0, 0, 0, 0. We need two iterations to erase all numbers.

  3. 7

    6

    9

    10

    10

    2

    3

    Returns: 20

  4. 0

    1

    1

    100000

    100000

    1

    1

    Returns: 4999950000

    Be careful with overflows.

  5. 399999

    1

    399999

    400000

    400000

    1

    400000

    Returns: 79999800000

  6. 2

    1

    400000

    3

    3

    1

    3

    Returns: -1

  7. 0

    1

    399999

    400000

    400000

    1

    399999

    Returns: 79999800000

  8. 1111

    1821

    0

    394712

    400000

    1

    16103

    Returns: 78971897392

  9. 1111

    1821

    0

    394712

    400000

    1

    16104

    Returns: -1

  10. 1

    7

    0

    10

    10

    1

    10

    Returns: -1

    John needs only four iterations.

  11. 0

    0

    0

    1

    1

    1

    1

    Returns: 0

  12. 0

    1

    1

    2

    3

    1

    2

    Returns: 1

  13. 2

    1

    2

    3

    1

    1

    1

    Returns: 2

  14. 3

    2

    2

    4

    7

    1

    1

    Returns: 10

  15. 0

    4

    1

    5

    1

    1

    1

    Returns: 0

  16. 4

    1

    3

    6

    3

    1

    2

    Returns: 9

  17. 5

    5

    0

    7

    5

    1

    3

    Returns: 20

  18. 4

    1

    6

    8

    11

    1

    2

    Returns: 6

  19. 8

    4

    1

    9

    1

    1

    1

    Returns: 8

  20. 9

    9

    0

    10

    19

    2

    2

    Returns: 81

  21. 4

    8

    4

    11

    21

    2

    4

    Returns: 27

  22. 5

    4

    7

    12

    9

    1

    2

    Returns: 35

  23. 2

    3

    12

    13

    15

    1

    2

    Returns: 20

  24. 0

    0

    5

    14

    1

    1

    1

    Returns: 0

  25. 8

    6

    13

    15

    1

    1

    1

    Returns: 8

  26. 2

    3

    3

    16

    21

    3

    4

    Returns: 35

  27. 3

    16

    9

    17

    19

    1

    2

    Returns: 84

  28. 9

    8

    4

    18

    29

    1

    3

    Returns: 65

  29. 12

    5

    3

    19

    33

    2

    7

    Returns: 280

  30. 16

    2

    18

    20

    39

    1

    4

    Returns: 476

  31. 17

    17

    9

    21

    3

    1

    2

    Returns: 35

  32. 2

    11

    4

    22

    15

    1

    1

    Returns: 58

  33. 8

    3

    21

    23

    45

    6

    7

    Returns: 127

  34. 22

    8

    3

    24

    43

    1

    3

    Returns: 652

  35. 19

    2

    21

    25

    17

    3

    4

    Returns: 153

  36. 0

    8

    8

    26

    5

    2

    3

    Returns: 40

  37. 9

    9

    14

    27

    25

    1

    1

    Returns: 115

  38. 26

    0

    18

    28

    15

    1

    2

    Returns: 278

  39. 16

    1

    10

    29

    21

    1

    4

    Returns: 290

  40. 17

    17

    6

    30

    55

    2

    2

    Returns: 186

  41. 16

    2

    4

    31

    57

    2

    4

    Returns: 307

  42. 20

    12

    9

    32

    13

    2

    3

    Returns: 66

  43. 27

    18

    5

    33

    31

    5

    6

    Returns: 105

  44. 21

    6

    2

    34

    21

    2

    8

    Returns: 223

  45. 12

    31

    5

    35

    55

    2

    6

    Returns: 860

  46. 23

    12

    14

    36

    29

    2

    2

    Returns: 23

  47. 10

    29

    4

    37

    61

    5

    6

    Returns: 204

  48. 30

    33

    16

    38

    71

    3

    8

    Returns: 276

  49. 18

    31

    11

    39

    9

    1

    3

    Returns: 81

  50. 8

    22

    10

    40

    7

    1

    4

    Returns: 136

  51. 35

    38

    6

    41

    75

    4

    5

    Returns: 456

  52. 4

    16

    23

    42

    25

    1

    3

    Returns: 460

  53. 40

    4

    14

    43

    5

    1

    1

    Returns: 18

  54. 43

    7

    6

    44

    67

    1

    1

    Returns: 2881

  55. 27

    18

    9

    45

    79

    1

    3

    Returns: 756

  56. 15

    28

    8

    46

    39

    5

    10

    Returns: 305

  57. 35

    27

    9

    47

    11

    4

    5

    Returns: 125

  58. 4

    47

    24

    48

    13

    1

    1

    Returns: 28

  59. 48

    44

    16

    49

    7

    1

    5

    Returns: 197

  60. 46

    38

    34

    50

    33

    5

    11

    Returns: 602

  61. 0

    1

    3

    4

    2

    1

    1

    Returns: 3

  62. 99

    25

    43

    128

    83

    18

    29

    Returns: 1622

  63. 373

    69

    845

    972

    530

    3

    6

    Returns: 282696

  64. 3269

    618

    428

    4096

    1868

    3

    6

    Returns: 4390991

  65. 113

    328

    10183

    12500

    7280

    127

    594

    Returns: 3576220

  66. 30262

    311

    9523

    31104

    13537

    846

    1676

    Returns: 80790161

  67. 45584

    4458

    41823

    67228

    45546

    12

    35

    Returns: 181959021

  68. 29200

    82145

    61186

    131072

    14786

    1633

    1684

    Returns: 2685148

  69. 90665

    185646

    26758

    236196

    165890

    2

    4

    Returns: 403861

  70. 164004

    7593

    131074

    400000

    125378

    530

    6641

    Returns: 18327888732

  71. 34350

    378871

    42025

    399918

    399947

    21538

    82765

    Returns: 66737757896

  72. 330576

    259323

    386796

    399948

    399952

    6519

    14362

    Returns: 49002314808

  73. 9854

    88084

    293687

    399983

    399932

    34644

    110571

    Returns: 22033068663

  74. 120806

    247558

    46890

    399903

    399915

    3

    5

    Returns: 52777314742

  75. 201329

    206570

    258757

    399982

    399935

    9072

    10192

    Returns: 14372722031

  76. 393052

    336095

    228088

    399943

    399917

    271

    1318

    Returns: 18086972990

  77. 93519

    53181

    258529

    399969

    399952

    217

    1173

    Returns: 19545631635

  78. 239905

    206943

    18590

    399901

    399945

    27672

    112952

    Returns: 46477317751

  79. 64037

    74677

    367827

    399915

    399951

    10040

    11753

    Returns: 9899490665

  80. 367080

    387806

    78801

    399901

    399940

    5767

    57166

    Returns: 36957050290

  81. 53734

    109483

    23370

    142356

    399990

    3097

    5973

    Returns: 5387586990

  82. 215420

    100023

    74241

    255104

    399995

    3002

    6311

    Returns: 25265929051

  83. 164203

    140551

    13308

    333432

    399976

    126

    200

    Returns: 37583406767

  84. 15431

    9685

    50150

    78900

    399978

    21

    755

    Returns: 14571208766

  85. 38065

    318847

    262539

    335904

    399988

    342

    906

    Returns: 35239142179

  86. 17321

    4017

    193624

    389798

    399985

    64

    29862

    Returns: 71567389737

  87. 264164

    89145

    213147

    293066

    399978

    173

    1359

    Returns: 46764056682

  88. 174702

    131049

    185124

    258766

    400000

    18753

    25241

    Returns: 15710241558

  89. 114947

    92023

    104795

    253379

    399980

    71692

    91872

    Returns: 14897626614

  90. 30650

    22487

    27855

    68795

    399996

    1063

    1755

    Returns: 5027565685

  91. 9163

    109094

    169973

    384724

    399984

    3779

    14176

    Returns: 41019787654

  92. 167468

    371466

    64737

    376891

    400000

    30376

    55257

    Returns: 48208623885

  93. 10055

    6539

    2932

    13031

    399977

    273

    5942

    Returns: 2280507058

  94. 71188

    124090

    21789

    167849

    399997

    12

    4575

    Returns: 27275087084

  95. 110536

    55944

    111882

    114031

    399997

    10237

    51195

    Returns: 20511712283

  96. 165133

    244450

    136395

    253738

    399998

    180

    1078

    Returns: 41588436487

  97. 23816

    3165

    510

    28750

    399997

    11

    22

    Returns: 4575743966

  98. 87833

    22847

    10436

    119226

    399977

    36

    121

    Returns: 14009633737

  99. 116952

    8792

    111257

    231300

    399991

    417

    1164

    Returns: 33226235298

  100. 52623

    247440

    255725

    260363

    399981

    111243

    156784

    Returns: 25332699741

  101. 4043

    164978

    35992

    171399

    399996

    1

    3029

    Returns: 34324519467

  102. 206102

    222124

    251359

    325138

    399978

    1

    50399

    Returns: -1

  103. 2387

    69945

    53541

    114656

    399994

    1

    53172

    Returns: -1

  104. 25001

    259998

    186650

    362312

    399986

    1

    42682

    Returns: 72470042477

  105. 2615

    8348

    6990

    9727

    399992

    1

    477

    Returns: -1

  106. 189745

    160113

    41452

    250821

    399989

    1

    71

    Returns: -1

  107. 31866

    13215

    22159

    32283

    399995

    1

    1678

    Returns: -1

  108. 74178

    28273

    84720

    106441

    399993

    1

    25724

    Returns: 21342248128

  109. 43789

    221360

    3989

    233642

    399994

    1

    2067

    Returns: 46273411174

  110. 146506

    261554

    72561

    357433

    399986

    1

    41879

    Returns: 71264535579

  111. 13528

    274373

    166912

    399981

    400000

    1

    14540

    Returns: 79648731281

  112. 296690

    59858

    98937

    399959

    400000

    1

    27521

    Returns: 80008014783

  113. 94158

    218925

    272788

    399921

    400000

    1

    60493

    Returns: -1

  114. 164671

    273094

    120825

    399908

    400000

    1

    280

    Returns: 82766772232

  115. 299920

    155444

    63344

    399933

    400000

    1

    1797

    Returns: 81952604782

  116. 261258

    16425

    310134

    399994

    400000

    1

    27550

    Returns: 79997975158

  117. 311021

    76384

    204827

    399935

    400000

    1

    37999

    Returns: -1

  118. 250607

    127702

    349986

    399928

    400000

    1

    46869

    Returns: -1

  119. 262079

    176283

    369407

    399922

    400000

    1

    87483

    Returns: 80067531370

  120. 301261

    220712

    157246

    399905

    400000

    1

    400000

    Returns: -1

  121. 1

    1

    399999

    400000

    400000

    1

    399999

    Returns: 79999800000

  122. 399999

    1

    399999

    400000

    400000

    3

    400000

    Returns: 79999799999

  123. 399980

    400000

    400000

    399990

    100000

    1

    2

    Returns: 17223340

  124. 123456

    123456

    333333

    400000

    400000

    3

    2000

    Returns: 33005146750

  125. 4444

    299999

    399999

    400000

    400000

    2

    3

    Returns: 10000245555

  126. 1

    2

    3

    399999

    400000

    1

    100000

    Returns: -1

  127. 234567

    322544

    234234

    398237

    400000

    100

    200

    Returns: 142991

  128. 39999

    99999

    49999

    99999

    99999

    1

    1

    Returns: 4999840001

  129. 12345

    14345

    23456

    300000

    400000

    3

    15

    Returns: -1

  130. 399999

    398765

    387654

    400000

    400000

    1

    10

    Returns: 1835210022

  131. 399999

    399999

    123345

    400000

    400000

    1

    200

    Returns: -1

  132. 1

    1

    1

    100000

    400000

    1

    60000

    Returns: 12799680002

  133. 399997

    399991

    399989

    399999

    400000

    10

    15

    Returns: 3398730

  134. 16

    624

    1383

    549

    1346

    473

    476

    Returns: -1

  135. 111

    831

    419

    705

    1162

    66

    111

    Returns: 268570

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: