expertcoderhk's blog

By expertcoderhk, history, 13 months ago, In English

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

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

| Write comment?
»
13 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    any links for the question you mentioned, would be helpful

    • »
      »
      »
      13 months ago, # ^ |
      Rev. 4   Vote: I like it +11 Vote: I do not like it

      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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
13 months ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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)