aopo's blog

By aopo, history, 3 years ago, In English

Minimal Payment Can anyone suggest an approach to solve this one? It came in yesterday Atcoder Beginner Contest 231. The editorial is not clear to me and the sample code provided there is giving 404 error. Please someone help me with this!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the official solution is here (from the Japanese version editorial)

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

    Moreover, I didn't understand the editorial. Can you elaborate it a bit?

»
3 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

I loved this problem. The problem can be seen as the coin change problem with negative weights: given the value $$$X$$$ and the coins array $$$A = (a_1, a_2 \ldots a_n)$$$, write $$$X = x_1a_1 + x_2a_2 + ... x_na_n$$$ with the $$$x_i$$$ allowed to be negative, and find the minimum possible value of $$$|x_1| + |x_2| + ... |x_n|$$$. The claim from the editorial is that for the sample testcase where $$$X=87, A=(1,10,100)$$$, in any valid solution, $$$x_1 = 7$$$ or $$$x_1 = -3$$$.

»
3 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Ok well, my submission passes so this is how I did it.

First of all just form X using coins greedily i.e without any change.

You can store the count of each coin you ended up using.

Let's index them as 0 to n — 1. let's indicate their quantity as value[index]. Let's also denote the coin count procured through greedy as count[index].

An observation :- It's optimal to use either the count[index] of each coin which you procured through greedy or complement of it. (Here complement means value[i + 1] / value[i] — count[index] and if you do use complement for an index you will have to add 1 to count[index + 1]).

Any other value of count[index] aside from the two mentioned will not improve our answer.

Now since we have at most two values u can apply a dp kinda solution to solve it but do be careful since if u do use the complement of coin count u have to pass + 1 to the next index.. and my dp states were index, carry where carry means how much is being passed to the next index. (Without proof here but it will not exceed 2 at most)

I couldn't understand the editorial solution but I think it meant this only.

https://atcoder.jp/contests/abc231/submissions/28047816