just_try_again's blog

I need some help with this DP problem
By just_try_again, history, 3 years ago, In English

Hey guys, I've been trying various approaches for this problem which appeared in this contest (ended). I submitted many solutions with different DP states but even my best solution gives me TLE on half of the test cases. My DP states are 'n' and the current number under consideration for the sequence, say 'i'. For each dp[n][i], I consider all cases, from the inclusion of no 'i' to the max number of times that 'i' can be included in the sequence.

I request you to share your approach(es) to this problem, please.

My submission — link

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Check the following constructive DP approach for solving the problem.

link

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey thanks for sharing your approach. Did you submit it in contest?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No. I have just seen the problem from the link in your blog for the first time.

      → Reply