Statistics

Problem Statement for "LRSort"

Problem Statement

Given is a sequence A[0..N-1] of nonnegative integers, each between 0 and M-1, inclusive. We are going to sort this sequence

The sorting will consist of N-1 phases, numbered from 0 to N-2. Each phase is either "type 0" or "type 1".

Also given is a sequence T[0..N-2] of zeros and ones: T[i] is the type of phase i.

In a type 0 phase we locate the leftmost minimum in A and then we move it to the beginning of A by repeatedly swapping it with its left neighbor. Once that is done, we will pretend that this element no longer exists during the following phases.

In a type 1 phase we move the rightmost maximum in A to the end in the same way.

Let S[i] be the number of swaps performed during phase i. Let WS[i] = S[i] * 10^i. Return sum(WS) modulo (10^9 + 7).


Please use the following pseudocode to generate the arrays A and T: 


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
    A[i] = state modulo M

for i = 0 to N-2:
    state = (state * 1103515245 + 12345) modulo 2^31
    tmp = (state div 2^20) modulo 100
    if tmp < B:
        T[i] = 1
    else:
        T[i] = 0

Definition

Class:
LRSort
Method:
simulate
Parameters:
int, int[], int, int, int
Returns:
int
Method signature:
int simulate(int N, int[] Aprefix, int M, int seed, int B)
(be sure your method is public)

Notes

  • The reference solution does not depend on the input being pseudorandom, that is only done to keep the input size small.

Constraints

  • N will be between 2 and 500,000, inclusive.
  • Aprefix will have between 0 and min(N,200) elements, inclusive.
  • Each element of Aprefix will be between 0 and M-1, inclusive.
  • M will be between 1 and 10^9, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.
  • B will be between 0 and 100, inclusive.

Examples

  1. 6

    {70, 60, 50, 40, 30, 20}

    100

    47

    74

    Returns: 12345

    The generated array T should look as follows: T = {1, 1, 0, 1, 0}. Regardless of the phase type, the element we want is always at the opposite end of the currently-unsorted segment of A. Thus, the required numbers of swaps are S = {5, 4, 3, 2, 1}.

  2. 10

    {4, 7}

    10

    47474747

    47

    Returns: 10226283

    The generated array A should look as follows: A = {4, 7, 8, 1, 8, 5, 8, 7, 2, 1} The generated array T should look as follows: T = {0, 0, 1, 0, 1, 1, 1, 1, 1} The calculated array S should look as follows: S = {3, 8, 2, 6, 2, 2, 0, 1, 0} For example, in phase 0 we move the leftmost 1 to the beginning of A (3 swaps), then in phase 1 we move the other 1 to the beginning of the rest of A (8 swaps), then in phase 2 we move the rightmost 8 to the end of A (which now only requires 2 swaps), and so on.

  3. 47000

    {}

    1

    47

    47

    Returns: 0

    The array A is all zeros. Regardless of the array T, there will never be any swaps.

  4. 15

    {}

    147

    777444

    42

    Returns: 466633400

    Remember to calculate the answer modulo 10^9 + 7.

  5. 500000

    {}

    1000007

    4777474

    47

    Returns: 123109382

  6. 446117

    {}

    7

    1475191316

    32

    Returns: 399498011

  7. 467167

    {5395, 193, 839, 5, 2161, 6490, 3944, 5929, 4478, 74, 6682, 2585, 4649, 3503, 1884, 1947, 4286, 4210, 2941, 3622, 1982, 272, 4595, 3065, 5871, 5632, 2895, 4923, 2800, 4569, 4711, 6241, 1605, 1954, 6460, 6886, 5973, 289, 1028, 2735, 802, 2972, 4737, 3142, 4164, 4424, 6659, 2071, 795, 5315, 7142, 7218, 1859, 5727, 6927, 2743, 1790, 3858, 6096, 902, 6333, 3413, 4953, 2892, 5528, 7146, 2345, 7201, 6331, 6635, 1957, 6628, 4548, 2142, 2924, 4363, 4631, 328, 3964, 2557, 4609, 6387, 3239, 2131, 5981, 4254, 6550, 1809, 4967, 933, 5139, 6893, 1696, 3111, 3976, 2073, 4944, 4571, 1222, 3636, 124, 1395, 4480, 5137, 6589, 6237, 678, 611}

    7310

    1141387247

    65

    Returns: 23943909

  8. 481594

    {}

    255986

    1570148161

    97

    Returns: 514925497

  9. 404349

    {}

    802174

    1352884873

    2

    Returns: 455059794

  10. 475618

    {}

    182

    1853868645

    88

    Returns: 643393335

  11. 424119

    {6, 8, 46, 50, 36, 22, 33, 25, 6, 17, 28, 0, 41, 7, 26, 4, 23, 1, 16, 2, 8, 11, 47, 32, 53, 31, 12, 50, 49, 51, 31, 33, 29}

    62

    42895311

    88

    Returns: 443480274

  12. 409679

    {}

    41

    200513682

    79

    Returns: 57129885

  13. 430736

    {}

    4707981

    528916607

    2

    Returns: 212281749

  14. 411611

    {}

    567

    1027003835

    78

    Returns: 963869218

  15. 496208

    {}

    170709

    346617440

    72

    Returns: 276353553

  16. 464389

    {855, 724, 620, 1001, 286, 130, 1040, 239, 944, 929, 36, 890, 1069, 135, 589, 1003, 1028, 233, 502, 721, 678, 341, 947, 46, 201, 940, 943, 566, 1115, 48, 387, 587, 83, 539, 1110, 988, 785, 140, 223, 1066, 977, 1100, 741, 638, 843, 419, 187, 210, 1049, 624, 829, 681, 1103, 737, 222, 190, 872, 738, 102, 716, 115, 802, 548, 520, 431, 593, 428, 952, 613, 911, 902, 650, 112, 318, 982, 1, 56, 865, 936, 1065, 896, 527, 602, 209, 620, 253, 347, 866, 689, 1018, 872, 480, 1030, 1051, 538, 641, 47, 776, 945, 367, 772, 87, 371, 371, 159, 993}

    1130

    1765314531

    7

    Returns: 518879676

  17. 429415

    {}

    22148

    19173630

    79

    Returns: 369372018

  18. 418230

    {}

    9609758

    3240676

    49

    Returns: 656324285

  19. 465447

    {}

    16024318

    526066028

    65

    Returns: 568981667

  20. 452492

    {}

    9

    1769321186

    70

    Returns: 683554107

  21. 413665

    {}

    181148554

    2043547395

    56

    Returns: 193553553

  22. 478162

    {}

    79688403

    1406159933

    55

    Returns: 967168451

  23. 498163

    {}

    104

    320361304

    16

    Returns: 955557548

  24. 493419

    {31815, 51839, 6075, 23406, 1948, 25857, 40940, 5329, 39423, 14695, 33803, 42209, 13813, 33279, 16887, 46744, 50060, 20091, 32772, 39685, 7453, 36841, 4092, 18802, 47162, 11617, 31999, 45584, 15814, 26500, 40017, 31068, 463, 38607, 26186, 39914, 15417, 40980, 36331, 24517, 52504, 51608, 6993, 22141, 4213, 10294, 38658, 6939, 15662, 12007, 5241, 9287, 33749, 11019, 47106, 10840, 5061, 6074, 8254, 38607, 25807, 22827, 7981, 27175, 19324}

    54595

    942936922

    86

    Returns: 260170238

  25. 445471

    {}

    19800477

    437721575

    4

    Returns: 127257521

  26. 426453

    {}

    42645783

    390384469

    40

    Returns: 740863343

  27. 493768

    {}

    3896370

    1827507600

    81

    Returns: 966550956

  28. 457556

    {}

    14960

    97389444

    24

    Returns: 573414632

  29. 442786

    {2, 0, 0, 1, 1, 2, 0, 1, 0, 2, 1, 1, 2, 2, 1, 2, 2, 0, 0, 0, 2, 0, 2, 1, 1, 0, 2, 0, 1, 0, 0, 2, 2, 1, 0, 2, 2, 2, 0, 1, 1, 0, 2, 0, 1, 1, 0, 0, 1, 2, 0, 2, 1, 2, 2, 1, 1, 0, 1, 1, 1, 1, 1, 0, 2, 2, 2, 2, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 2, 0, 1, 2, 2, 2, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 2, 2, 0, 1, 2, 0, 2, 1, 1, 0, 1, 1, 0}

    3

    1781210239

    41

    Returns: 174529876

  30. 470464

    {1273, 199, 895, 13, 143, 201}

    2078

    1646888126

    97

    Returns: 1574268

  31. 460822

    {}

    75

    1698357684

    65

    Returns: 608705118

  32. 445595

    {}

    2

    1336545990

    6

    Returns: 63321245

  33. 479981

    {}

    31569

    1428569044

    92

    Returns: 979316280

  34. 411787

    {}

    471

    421869180

    90

    Returns: 649744845

  35. 449465

    {}

    5541

    127958513

    3

    Returns: 458163620

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: