Shooting Birds- Editorial

**Problem Link : **

**Difficulty : ** Medium

**Pre-requisites : ** Expectations

**Solution : **
The first instinct in this problem is to formulate a DP, since the answer to a future state depends on the current one in a trivial manner. That basically goes through (more details on the dp later), apart from the fact that N could be as big as 10^18. The simple way to work around this is to observe that there’s another constraint given, ln(N) < 14 (P - 1). This basically implies the following inequality,

N/10^(6*P) < 10^(-6)

As a result, the expected number of birds you shoot down after X=10^6 will be less that 10^(-6), and hence the range N can be ignored! The DP can then be worked backwards from X=10^6.

More on the DP :
Let DP[i] = Expected number of birds you will shoot down from now onwards (that is from time i to time N (range))

Trivially, DP[i] = DP[i + T + R]/(i^P) + DP[i + T] * (1 - 1/(i^P))

Naturally, this DP is evaluated from backwards, and the answer to the question is DP[1].

In context of the above comments, if we need DP[1] within 10^(-6) of it’s correct value, beginning from DP[min (10^6, R)], and going backwards, suffices.

**Setter’s code : **



DP[i] = (1 + DP[i + T + R])/(i^P) + DP[i + T] * (1 - 1/(i^P)) is the correct recurrence.