http://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 )

Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 168 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 155 |

10 | McDic | 153 |

http://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 )

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/20/2020 09:13:40 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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!

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

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

@diego_v1 very helpful :)

Yes I do think so too :)

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! :)