adzo261's blog

AtCoder Beginner Contest 118 -D.Match Making
By adzo261, history, 5 years 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

Comments Comments (4)
| Write comment?
»
5 years 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 :)

→ Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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.

→ Reply