baldvaritesh's blog

By baldvaritesh, history, 9 years ago, In English

Hey I can't seem to formulate the DP for [this] ? (http://community.topcoder.com/stat?c=problem_statement&pm=13964&rd=16514&rm=326779&cr=10574855)

I understand that the solution space is reduced to 3^n as compared to 4^n, and that we have to work on individual digits of the sum, but I'm unable to grasp how to take care of the carry and how that would fit in the DP formulation ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Perhaps you could have f(d, c, z) = the largest achievable value for the last d digits of the lucky sum that has carry c (0-1), and z (0-2) summands which must have 0 for the rest of their digits.