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

Автор expertcoderhk, история, 13 месяцев назад, По-английски

Given a List of coins, find minimum number of coins that need to be added to list so that all prices from [1,P] can be paid using the coins of list.

Constraints Length of coin list<=100000 Value of coins <=1000 P<=10000

Sample: P=19 Coinlist={1,4,10} solution=2

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

»
13 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

This may be solved with DP, but it does not need to be. There is a greedy solution based on the necessary condition on whether a prefix of the increasingly sorted coin list with sum $$$S$$$ can make up all subset sums in $$$[1,S]$$$.

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

    any links for the question you mentioned, would be helpful

    • »
      »
      »
      13 месяцев назад, # ^ |
      Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится

      I remember solving a task almost equal to the task I explained, but I forgot the link to it. I'll update the comment if I find it out. Anyways the main theorem and the proof is as follows if you were wondering.

      Spoiler

      UPD: the task was "No change" from EIO 2020-21

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

if you have coinst with value 1 and 2 why can't you make all the coins

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

    Number of times a value is present in coin list, that value can be used only that many times

»
13 месяцев назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

let the array be arr (0 indexed) , and the corresponding prefix sum array be pre (in the pseudo code , prefix sum array is considered as 0 indexed) here is the pseudo code

ans = 0
for i in arr : 
        if pre[i] >= p : 
                break
        if pre[i] < arr[i+1] : 
                ans = ans + 1;
                insert pre[i]+1 to the right of i (and update prefix sum array accordingly)