adzo261's blog

By adzo261, history, 5 weeks ago, In English,

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.

Problem Link

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 with i matches and has j as 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 the i-th available digit and c[i] means the cost of digit i.

Finally, we can greedily output the answer. For i, the number of matches left now, consider a best j with max{f[i][j]}. If there exists some js with the same value, just use the maximum j. 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 :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.