by zkw, Jul 17, 2016, 4:13 PM
First, here is a trivial DP solution with
. Let

be the minimum worst-case cost to guess a number
, then we have

Enumerate

and we are done. To optimize the computation, let

then

Therefore,

Notice that

when
. So we can compute

in amortized

time. Then we need the sliding minimum of

with

fixed and
. This can be done using an increasing deque, and it takes amortized

time to get the desired minimum. We need to compute

values of
, and each takes

time, so in all
.
Program (in C++)
This post has been edited 10 times. Last edited by zkw, Jul 21, 2016, 9:46 AM