yesnomaybe's blog

Atcoder contest abc155 Dp question Problem E

By yesnomaybe, history, 4 years ago, In English

Hi,

Can someone please help me with the following problem? https://atcoder.jp/contests/abc155/tasks/abc155_e

I found this dp solution, am unable to understand what does dp state denote and how transitions are made? https://atcoder.jp/contests/abc155/submissions/10154214

Or any other solution?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Refer this comment

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

    Hi, thanks for the reply. I did check out that comment but I am unable to understand it. Can you please elaborate a bit on what does dp state denote (as in what does carry mean?).

    Can you please shed more light on the solution?

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

      As in what's the intuition/logic behind it? What are we trying to do exactly?

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

        Start considering from the least significant position. Here either you can choose to pay that position's value or increase the amount so that the clerk returns the number of notes for that position as (10-that value) with your next higher significant payment increased by one (i.e you are paying on more note for the next higher position and expecting the desired return for this position).

        This happens for every digit from right to left and we have the options of giving the value or expecting a change by giving some extra money.

        Finally, at the most significant position, you come to know whether at each digit you ask for change there or give the amount in case you want to know the number of notes of each type which is not required though.

        → Reply