DP problem from LIve Archive - 3144.

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

DP problem from LIve Archive - 3144.

Post by serur » Sun Aug 20, 2006 8:02 pm

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?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sun Aug 20, 2006 8:36 pm

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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Mon Aug 21, 2006 2:22 pm

Thank you David! I got AC, though with 0.678 CPU.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Post Reply

Return to “ACM ICPC Archive Board”