Блог пользователя aopo

Автор aopo, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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