selfcompiler's blog

DP problem

By selfcompiler, 12 years ago, In English

http://mirror.codeforces.com/problemset/problem/31/E can any one explain how to solve this problem i am very weak in dp ? how to think plz explain it fully (sorry for my poor english )

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

»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Homer has a C(2n,n) different ways to get his digits,since n<=18 you can try all possible ways and choose the best.

dp in not necessary in this problem.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Hello, As far as I know C(36, 18) is almost 90*10^8 so if you try all possible ways it'll take around 90 seconds!

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

      Oops, I don't know how I calculated it as C(18,9) I feel stupid!!

      → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

You know that both players will take n digits, so if Homer takes digit D and it's the Kth digit he takes, the ACTUAL value of that digit will be 10^(n — K) * D.

For example, for the number 9911, Homer takes digits 9 and 1. The actual value of that 9 he takes is 90, because he takes it first. If he took, let's say, digits 852, the actual value of the first 8 would be 800, the 5 would be 50 and the 2 would be 2.

With that knowledge, we can go through the digits from left to right and make a DP solution.

Let F(d,h) be the best state when Homer takes h digits and the last digit we processed is the digit in position d. We have two cases, either Homer took the digit d, or he didn't.

So F(d,h) = max(F(d-1, h-1) + 10^(n — h) * x, F(d-1, h) + 10^(n — d — h) * x), where x is the digit at position d.

We have to keep track of which of these two cases we came from for each state to be able to reconstruct the movements in the end and print them out.

Here's my submission: 2956565

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    @diego_v1 very helpful :)

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 8   Vote: I like it 0 Vote: I do not like it

    Just a little correction for those who don't like looking at codes and have just read your explanation:

    The 2 values that you compare are F(d-1, h-1)+10^(n-h)*x and F(d-1,h)+10^(n-_**(d-h)**_). <- The brackets in bold were missing. It's not such big a problem if you actually think when you are writing the code and you are not just copying this formula. Anyways, great explanation with all the examples and stuff! :)

    → Reply