DP problem from LIve Archive - 3144.

[serur]

Hi fellows!

If you have a collection of DP problems, it may interest you to look through this: 3144 Live Archive.
Let me explain my reasoning:

for given m let c[m][n][v] be the number of all sequences of length n with v being its first element.
then we get the following recurrence:

Code: Select all

c[m][n][v] = c[m][n-1][2*v] + c[m][n-1][2*v+1] + ... + c[m][n-1][m]

and the answer is, therefore, c[m][n][1] + c[m][n][2] + ... + c[m][n][m].

(division by degrees of 2 are omitted, of course)

TLE. What do you say?

[david]

There's a much simpler recurrence. Think of the number of sequences of length n having maximum element <= m.

[serur]

Thank you David! I got AC, though with 0.678 CPU.