Can someone please help me in solving D. of today's Atcoder beginner contest.

Editorials are not available in English and I am not able to approach this problem on my own.

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

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | mnbvmar | 3363 |

4 | Petr | 3330 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3300 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Vn_nV | 3182 |

10 | dotorya | 3156 |

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

1 | Radewoosh | 190 |

2 | Errichto | 184 |

3 | rng_58 | 161 |

3 | PikMike | 161 |

5 | Petr | 156 |

6 | Ashishgup | 153 |

6 | Vovuh | 153 |

8 | neal | 151 |

8 | 300iq | 151 |

8 | majk | 151 |

8 | Um_nik | 151 |

Can someone please help me in solving D. of today's Atcoder beginner contest.

Editorials are not available in English and I am not able to approach this problem on my own.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/25/2019 03:30:43 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Here is my solution which is different from the official one. (My English is very poor, sorry)

Let

`dp[i][j]`

be the maximum number of digits of the answer, which is made withimatches and hasjas the first(highest) digit.Thus we can easily get

`dp[i + c[A[k]]][A[k]] = max(dp[i + c[A[k]]][A[k]], dp[i][A[j]] + 1)`

, where`A[i]`

means thei-th available digit and`c[i]`

means the cost of digiti.Finally, we can greedily output the answer. For

i, the number of matches left now, consider a bestjwithmax{f[i][j]}. If there exists somejs with the same value, just use the maximumj. This strategy is correct, because when we compare two numbers, we first consider their total length, and then from high digits to low digits.Here is my solution for a better understanding :)

Thanks, I got it. And, your English is good. :-)

how u store so large numbers and why u dont use recursive approach

You don't need to actually store the whole number, instead, you split it in into digits.

As for the way to achieve the algorithm, you can use recursive approach if you like. It doesn't matter.

The main insight for these type of questions where you must output a big integer that is maximum is to first maximize length. If there are multiple answers of the same length, break ties by choosing the lexicographically larger number.

I maintained two arrays. F(i) represents the maximum length possible with exact cost i A(i, d) represents the length of the number with total cost i and last digit d.

Here is my code and explanation.