Connection Status:
Competition Arena > DengklekGaneshAndDetention

DengklekGaneshAndDetention

TCO17 Round 2B · 2017-03-31 · by fushar

TCO17 Round 2B · 2017-03-31 · by fushar · Dynamic Programming, Math
Class Name: DengklekGaneshAndDetention
Return Type: double
Method Name: getExpected
Arg Types: (int, int, int, int, int)
Problem Statement

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

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
0)
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.

1)
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.

2)
8
10
3
10
29
Returns: 7.8002283556316
3)
1
0
0
0
1
Returns: 0.0
4)
1000000
0
0
0
1
Returns: 0.0

Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DengklekGaneshAndDetention with a public method double getExpected(int N, int valInit, int valMul, int valAdd, int valMod) · 43 test cases · 2 s / 256 MB per case

Submitting as anonymous