Statistics

Problem Statement for "DengklekGaneshAndDetention"

Problem Statement

Dengklek and Ganesh often arrive late for school. Feeling irritated, the principal finally decided to give both of them an unusual after-school detention: toggling classroom lamps!

There are N classrooms at the school, conveniently numbered 0 through N − 1. Each classroom has a lamp. The initial state of the lamps is given by an int[] lamps with N elements. The lamp in classroom i is initially on if lamps[i] is 1, otherwise it is initially off. The principal has also secretly prepared a possibly unfair coin in each classroom. You are given an int[] probs with N elements. The coin in classroom i will land heads if flipped with probability probs[i] percent, and will land tails with probability (100 − probs[i]) percent.

Dengklek is told to visit the classrooms in order, from classroom 0 to N − 1. In each classroom i:
  • If the lamp in the current classroom is off, Dengklek must do nothing.
  • Otherwise, Dengklek must flip the coin in the current classroom i:
    • If it lands heads up, Dengklek must call Ganesh and ask him to toggle all lamps in classrooms 0 through i − 1, inclusive.
    • If it lands tails up, Dengklek must call Ganesh and ask him to toggle all lamps in classrooms i + 1 through N − 1, inclusive.

Every time Ganesh toggles a lamp from off to on, Ganesh is told to shout, "We will not come late for school again!".

The principal is now curious about the expected number of times Ganesh will shout. Return this expected number.

Due to a technical restriction, the int[]s lamps and probs will be generated using a pseudorandom number generator. You are given ints valInit, valMul, valAdd, and valMod. Compute lamps and probs using the following pseudocode: 

let val = array of N integers
val[0] = valInit
for i in 1 .. N-1:
    val[i] = (val[i-1] * valMul + valAdd) mod valMod

for i in 0 .. N-1:
    lamps[i] = val[i] mod 2
    probs[i] = val[i] mod 101

Definition

Class:
DengklekGaneshAndDetention
Method:
getExpected
Parameters:
int, int, int, int, int
Returns:
double
Method signature:
double getExpected(int N, int valInit, int valMul, int valAdd, int valMod)
(be sure your method is public)

Notes

  • The returned value must have an absolute or relative error less than 10^-6.
  • The author's solution does not depend on any properties of the pseudorandom number generator.

Constraints

  • N will be between 1 and 1,000,000, inclusive.
  • valMod will be between 1 and 1,000,000,000, inclusive.
  • valInit will be between 0 and valMod − 1, inclusive.
  • valMul will be between 0 and valMod − 1, inclusive.
  • valAdd will be between 0 and valMod − 1, inclusive.

Examples

  1. 3

    0

    1

    25

    100

    Returns: 1.375

    Using the above pseudorandom number generation, we have: lamps = {0, 1, 0} probs = {0, 25, 50} The following events will happen: Dengklek visits classroom 0. The lamp is off, so Dengklek does nothing. Dengklek visits classroom 1. The lamp is on, so Dengklek flips the coin: With probability 25%, the coin lands heads, and Ganesh first toggles the lamp in classroom 0 and shouts once. Dengklek visits classroom 2. The lamp is off, so Dengklek does nothing. With probability 75%, the coin lands tails, and Ganesh toggles the lamp in classroom 2, then shouts once. Dengklek visits classroom 2. The lamp is on, so Dengklek flips the coin: With probability 50%, the coin lands heads, and Ganesh toggles the lamps in classrooms 0 and 1, then shouts once. With probability 50%, the coin lands tails. Therefore, the expected number of shouts is 25% × 1 + 75% × 50% × 2 + 75% × 50% × 1 = 1.375.

  2. 3

    20

    2

    10

    57

    Returns: 1.06

    This time, we have: lamps = {0, 0, 1} probs = {20, 50, 53} Nothing will happen in classrooms 0 and 1. In classroom 2, with probability 53% Ganesh toggles the lamps in classrooms 0 and 1. While he does so, he shouts twice. Therefore, the expected number of shouts is 53% × 2 = 1.06.

  3. 8

    10

    3

    10

    29

    Returns: 7.8002283556316

  4. 1

    0

    0

    0

    1

    Returns: 0.0

  5. 1000000

    0

    0

    0

    1

    Returns: 0.0

  6. 1

    51

    1

    0

    100

    Returns: 0.0

  7. 1

    52

    1

    0

    100

    Returns: 0.0

  8. 1

    100

    1

    0

    101

    Returns: 0.0

  9. 1

    99

    1

    0

    101

    Returns: 0.0

  10. 1000000

    51

    1

    0

    100

    Returns: 0.3658823172464012

  11. 1000000

    52

    1

    0

    100

    Returns: 0.0

  12. 1000000

    100

    1

    0

    101

    Returns: 0.0

  13. 1000000

    99

    1

    0

    101

    Returns: 4875.874371859176

  14. 1000000

    123

    456

    789

    999999937

    Returns: 1.2503984641116129E11

  15. 1000000

    12

    34

    567

    1000000000

    Returns: 2.8032838018057813

  16. 10

    2

    3

    5

    99992681

    Returns: 18.02648386721292

  17. 10

    3

    5

    7

    99994691

    Returns: 19.514928894669822

  18. 10

    5

    7

    11

    99994319

    Returns: 20.850742869596026

  19. 100

    555

    666

    777

    99995281

    Returns: 1227.7359958668146

  20. 1000

    1

    2

    3

    99993331

    Returns: 119405.10315498855

  21. 10000

    11

    22

    33

    99993001

    Returns: 1.2381669013549682E7

  22. 10000

    100

    200

    300

    99994571

    Returns: 1.2456026446307363E7

  23. 100000

    100

    200

    300

    99994571

    Returns: 1.24809707752572E9

  24. 886039

    992161029

    201578563

    1113743

    999999937

    Returns: 9.827955863795612E10

  25. 805196

    743659229

    716504542

    928277595

    999999937

    Returns: 8.113222662871077E10

  26. 6282

    189835121

    439571807

    194291102

    999999937

    Returns: 4990154.46945346

  27. 998266

    358081069

    887740234

    72819490

    999999929

    Returns: 1.2458800687803264E11

  28. 445592

    94849352

    849544475

    960803998

    999999929

    Returns: 2.483920699703289E10

  29. 674012

    81881537

    735123974

    525090850

    999999929

    Returns: 5.675901489090109E10

  30. 30773

    507842031

    849894374

    760819060

    999997457

    Returns: 1.1766505753230605E8

  31. 820968

    776629771

    777021349

    200921492

    999997457

    Returns: 8.428130292928278E10

  32. 857721

    676634348

    237205356

    896015668

    999997457

    Returns: 9.196567216959982E10

  33. 93738

    416

    1008

    915

    1009

    Returns: 1.1528933258157477E9

  34. 969422

    66

    954

    824

    1009

    Returns: 1.1582385631625069E11

  35. 81750

    390

    9

    361

    1009

    Returns: 9.127366599507942E8

  36. 521884

    4863

    2882

    70575

    102121

    Returns: 3.366294763384757E10

  37. 354578

    38604

    59182

    21633

    102121

    Returns: 1.5672804331501186E10

  38. 311724

    69258

    29494

    10174

    102121

    Returns: 1.2144126670592999E10

  39. 1000000

    0

    0

    0

    999999999

    Returns: 0.0

  40. 1000000

    0

    0

    99

    999999999

    Returns: 4925.623115577769

  41. 1000000

    0

    0

    51

    99999

    Returns: 1.0551646526971377

  42. 1000000

    776629771

    777021349

    200921492

    999997457

    Returns: 1.2499154760132462E11

  43. 987654

    98765

    98765431

    9876543

    987654319

    Returns: 1.218923004204765E11

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: