Statistics

Problem Statement for "ConstantSegment"

Problem Statement

N robots are waiting in a line at a robot repair facility. The robots are numbered from 0 to N-1 in the order in which they are waiting.

Each of the robots has one of M possible problems. The problems are numbered from 0 to M-1. The problem of robot i is P[i].


If two or more consecutive robots have the same problem, the workers at the repair facility are happy because they can use the same equipment and thus there are no unnecessary overheads.

At some point during the repairs you would like to have at least K consecutive robots that all have the same problem. In order to reach this goal, you can send an arbitrary subset of robots home. (The robots that remain waiting will still wait in the same relative order.)

Find out whether your goal is reachable. If it isn't, return -1. If it is, return the smallest number of robots that need to be sent home.


In order to keep the input size small, only a prefix of the array P is given, the rest is generated pseudorandomly. Please use the code or pseudocode below to generate P. 

Pseudocode:

P = an empty array of length N

L = length(Pprefix)
for i = 0 to L-1:
    P[i] = Pprefix[i]

state = seed
for i = L to N-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    P[i] = (state div 16) modulo M

------------------------------------------------------

Java:

int[] P = new int[N];

int L = Pprefix.length;
for (int i=0; i<L; ++i) P[i] = Pprefix[i];

long state = seed;
for (int i=L; i<N; ++i) {
    state = (state * 1103515245 + 12345) % (1L << 31);
    P[i] = (int)((state / 16) % M);
}

------------------------------------------------------

C++:

vector<int> P(N);

int L = Pprefix.size();
for (int i=0; i<L; ++i) P[i] = Pprefix[i];

long long state = seed;
for (int i=L; i<N; ++i) {
    state = (state * 1103515245 + 12345) % (1LL << 31);
    P[i] = (state / 16) % M;
}

Definition

Class:
ConstantSegment
Method:
sendSomeHome
Parameters:
int, int, int, int[], int
Returns:
int
Method signature:
int sendSomeHome(int N, int K, int M, int[] Pprefix, int seed)
(be sure your method is public)

Notes

  • The reference solution does not depend on the input being pseudorandom, it would correctly solve any input of the given size.

Constraints

  • N will be between 1 and 200,000, inclusive.
  • K will be between 1 and N, inclusive.
  • M will be between 1 and 10^6, inclusive.
  • Pprefix will have between 0 and min(N, 200) elements, inclusive.
  • Each element of Pprefix will be between 0 and M-1, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.

Examples

  1. 10

    3

    10

    {1, 4, 3, 3, 3, 3, 2, 0, 3, 9}

    0

    Returns: 0

    You want to have at least three consecutive robots with the same problem. This is already happening: there are four consecutive robots with problem of type 3.

  2. 10

    5

    10

    {1, 4, 3, 3, 3, 3, 2, 0, 3, 9}

    0

    Returns: 2

    In order to have at least five consecutive robots with the same problem, you should send home robots #6 (problem of type 2) and #7 (problem of type 0).

  3. 10

    6

    10

    {1, 4, 3, 3, 3, 3, 2, 0, 3, 9}

    0

    Returns: -1

    In this test case it is not possible to have six or more consecutive robots with the same problem.

  4. 10

    2

    47

    {1, 4, 5, 2, 1, 2, 3, 7, 8, 3}

    4747

    Returns: 1

    The optimal solution here is to send just one robot home: robot #4 (problem type 1). This creates two consecutive robots with the same problem (type 2).

  5. 20

    3

    10

    {0, 1, 2, 3, 4}

    123456789

    Returns: 9

    The array P you should have generated is {0, 1, 2, 3, 4, 0, 5, 7, 1, 3, 5, 4, 0, 6, 3, 7, 2, 4, 6, 5}. If you wrote your own code to generate P, please watch out for integer overflow when calculating new values of the variable "state".

  6. 1

    1

    47

    {12}

    12

    Returns: 0

  7. 200000

    199000

    1

    {}

    47

    Returns: 0

  8. 200000

    99000

    2

    {}

    47

    Returns: 98994

  9. 200000

    50000

    2

    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    23623632

    Returns: 49794

  10. 200000

    2

    1000000

    {}

    684

    Returns: 7

  11. 200000

    3

    987654

    {}

    4634

    Returns: 1353

  12. 200000

    300

    500

    {}

    346

    Returns: 113196

  13. 200000

    23456

    5

    {}

    4363

    Returns: 91858

  14. 200000

    40078

    5

    {}

    47

    Returns: 159919

  15. 200000

    40079

    5

    {}

    47

    Returns: -1

  16. 195764

    18142

    7

    {}

    1948501517

    Returns: 107610

  17. 199351

    99

    1551

    {}

    1685411311

    Returns: 104280

  18. 190670

    4

    8579

    {}

    2690834

    Returns: 445

  19. 194322

    3

    33366

    {}

    1836955051

    Returns: 66

  20. 193769

    453

    219

    {}

    1039591800

    Returns: 85122

  21. 190544

    2

    229157

    {}

    1468508435

    Returns: 1

  22. 199138

    1

    364895

    {}

    151521850

    Returns: 0

  23. 192056

    93

    1224

    {}

    1647457924

    Returns: 64856

  24. 198328

    1

    197351

    {}

    974776318

    Returns: 0

  25. 195486

    1525

    124

    {}

    473072173

    Returns: 175806

  26. 196826

    57

    3220

    {}

    1026423979

    Returns: 110498

  27. 199097

    273

    438

    {}

    172270288

    Returns: 95291

  28. 197928

    67

    916

    {}

    948917258

    Returns: 31603

  29. 199934

    12448

    11

    {}

    2084771948

    Returns: 122355

  30. 194147

    2

    170184

    {}

    65241470

    Returns: 0

  31. 192790

    1

    152771

    {}

    1141387247

    Returns: 0

  32. 198376

    2

    255986

    {}

    1570148161

    Returns: 0

  33. 190543

    363

    497

    {}

    1352884873

    Returns: 149501

  34. 190364

    1

    389556

    {}

    1485905588

    Returns: 0

  35. 197071

    3849

    43

    {}

    853308887

    Returns: 155601

  36. 192095

    18666

    10

    {}

    1477705088

    Returns: 166026

  37. 198640

    18

    4981

    {}

    1906624755

    Returns: 23365

  38. 190007

    1101

    14

    {}

    1585910533

    Returns: 13050

  39. 190339

    144

    277

    {}

    778158833

    Returns: 26103

  40. 198383

    4

    45950

    {}

    1948158689

    Returns: 290

  41. 199234

    1

    267380

    {}

    752144434

    Returns: 0

  42. 192466

    1

    219766

    {}

    1007175254

    Returns: 0

  43. 191003

    2

    5104

    {}

    380485713

    Returns: 0

  44. 194959

    31342

    3

    {}

    649419618

    Returns: 61867

  45. 199010

    1

    405358

    {}

    2109919775

    Returns: 0

  46. 195615

    1

    144751

    {}

    1775873863

    Returns: 0

  47. 196842

    37

    3288

    {}

    2101334812

    Returns: 53140

  48. 199792

    8322

    18

    {}

    502796335

    Returns: 137163

  49. 197557

    7

    16969

    {}

    284290351

    Returns: 7638

  50. 194712

    2

    40247

    {}

    1512640368

    Returns: 0

  51. 195424

    93

    61

    {}

    421704849

    Returns: 3523

  52. 197527

    6

    25453

    {}

    102151484

    Returns: 6473

  53. 199178

    84

    100

    {}

    1130699910

    Returns: 5363

  54. 198884

    1

    57914

    {}

    468300517

    Returns: 0

  55. 198533

    2

    512396

    {}

    1338728498

    Returns: 2

  56. 196751

    421

    75

    {}

    1309953612

    Returns: 25957

  57. 196636

    109

    1761

    {}

    467288229

    Returns: 126896

  58. 191526

    1

    14098

    {}

    1502298833

    Returns: 0

  59. 199549

    35116

    3

    {}

    1092362325

    Returns: 69601

  60. 193450

    239

    726

    {}

    1286402574

    Returns: 138622

  61. 197294

    7

    26786

    {}

    235240045

    Returns: 12236

  62. 192544

    1

    513644

    {}

    118213281

    Returns: 0

  63. 196926

    5

    30732

    {}

    1106908031

    Returns: 3312

  64. 194816

    4059

    12

    {}

    729061624

    Returns: 43220

  65. 196931

    55

    2042

    {}

    1007203776

    Returns: 59879

  66. 20

    3

    10

    {0, 1, 2, 3, 4 }

    123456789

    Returns: 9

  67. 200000

    1000

    100

    { }

    123456

    Returns: 89561

  68. 20000

    10

    10

    {0, 1, 2, 3, 4 }

    12345789

    Returns: 17

  69. 5

    4

    100

    {5, 5, 5, 5, 5 }

    100

    Returns: 0

  70. 10

    5

    1000000

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

    123456789

    Returns: 3

  71. 20

    3

    100

    {1, 2, 2, 2, 1, 3, 3, 3, 1, 4, 4, 4, 1, 5, 5, 5, 1, 6, 6, 6 }

    0

    Returns: 0

  72. 200000

    2

    1000000

    {8, 50, 74, 59, 31, 73, 45, 79, 24, 10, 41, 66, 93, 43, 88, 4, 28, 30, 41, 13, 4, 70, 10, 58, 61, 34, 100, 79, 17, 36, 98, 27, 13, 68, 11, 34, 80, 50, 80, 22, 68, 73, 94, 37, 86, 46, 29, 92, 95, 58, 2, 54, 9, 45, 69, 91, 25, 97, 31, 4, 23, 67, 50, 25, 2, 54, 78, 9, 29, 34, 99, 82, 36, 14, 66, 15, 64, 37, 26, 70, 16, 95, 30, 2, 18, 96, 6, 5, 52, 99, 89, 24, 6, 83, 53, 67, 17, 38, 39, 45, 2, 98, 72, 29, 38, 59, 78, 98, 95, 5, 10, 32, 46, 76, 36, 99, 43, 100, 69, 13, 61, 58, 95, 9, 96, 69, 14, 31, 7, 63, 43, 66, 83, 53, 68, 22, 96, 13, 72, 2, 91, 32, 39, 58, 17, 91, 41, 80, 36, 7, 73, 99, 96, 20, 55, 24, 90, 61, 6, 27, 24, 7, 14, 71, 39, 95, 21, 45, 67, 35, 27, 95, 64, 39, 45, 91, 51, 60, 24, 48, 86, 18, 73, 40, 48, 86, 97, 86, 24, 21, 45, 69, 36, 16, 26, 35, 43, 12, 80, 53 }

    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: