2021 December - HILO

#1

I’m reading the official editorial for the December 2021 problem HILO.

I get almost all of the solution, except when they state that we use the case when j = x, k = N - x and b = 0(when Bessie last said “LO”) as our final solution state. Specifically, why do we have to end at b = 0, or when Bessie last said “LO”? Isn’t our final state something like \frac{dp[x][x - N][0] + dp[x][x - N][1]}{2} instead?

#2

dp[x][N-x][0] is the expected number of HILOs if you prepend a LO to the front of S (which doesn’t affect the answer). dp[x][N-x][1] is the expected number of HILOs if you prepend a HI to the front of S.

1 Like
#3

Ah, i see. Thanks for the fast reply!