ClosetNarcissist's blog

Minimizing Coins Optimizations?
By ClosetNarcissist, 10 months ago, In English

In the recent CF round 931 for problem B I realized that I could not solve it normally using DP since n was too high. I knew that some coin systems can be solved greedily but it was not the case for this one. During the contest, I solved it like this: https://mirror.codeforces.com/contest/1934/submission/249165174

But later I saw that some people just pre-calculated the answer upto 30 or something and then used some mod tricks to get the answer. I thought they picked 30 since it was the LCM and so I tried to test my hypothesis by solving the CSES Minimizing Coin problem and it actually worked. I thought this was some optimization on the problem that I did not know about before. This was my solution: https://cses.fi/paste/dbb9ee26f083862b8352b1/

However, I soon realized that my method does not work for coin systems like {3, 6, 10, 15}, as my code would give impossible for the value 32, which is obviously wrong as it should really be 4. After that, I thought there had to be some conditions that had to be met for me to use this "lcm" trick (if this is even real or just something that coincidentally worked). But I could not think of any and I could not find any relevant articles, so I want to ask you guys to make me understand.

Thanks in advance. Btw before writing this blog, I thought I'd solve the original CF problem using the "lcm" trick but it did not give the correct answers lol.

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can make dp for n<=100. If n>85 you make n-=85;n=n%15;n+=85;

→ Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Probably you can use lcm to exclude unoptimal combinations, like if l=lcm(coin1,coin2) < x, always make l from bigger coins

Tried this idea in cses gives around 2x speed up.

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

    The cses test cases are kinda weak tho. Like i was able to hack my own "lcm" solution pretty easily

    Hmmm, the problem with making l using the bigger coins is that all coin combinations does not converge at the lcm and so values are possible which the "lcm" method cannot account for.

    Although for some reason i feel like it will work if i take 2*lcm using bigger coins greedily and then do the dp. I can't prove this tho, can be wrong.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      But my optimisation doesn't break anything, it just limits the number of times small coins are used.

      Replacing the entire solution with lcm probably can work too, but I guess it should be done carefully optimising step by step to not skip some possibilities by accident.

      Btw, problem B you mentioned is solvable by Dijkstra without any any memory except bfs queue: https://mirror.codeforces.com/contest/1934/submission/249985628 . On CSES with memory it's 0.09s worst case. So probably combining this with lcm can give good results.

      → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

[Unverified, please try to counter with a case]The lcm trick will not work in general if the denominations of coins cant make every sum from 1. I tried a lot of different things. Understand that for any limited set of coins, the greedy solution starts working after a certain limit of money. My solution is this: write all the upper bounds of all the coin denominations (obviously excluding the highest one), add them all up. In the example 1 3 6 10 15, the limits are 1: 2, 3: 1, 6: 2, 10: 2, and the sum is 37. it is obvious than any money above 37 will require the use of 15 hence greedy solution starts working. You can notice other restrictions in this set and finally you can conclude that the non-greedy limit is 23. But you dont need it, you just need a number, which is greater than or equal to this non greedy limit. You can badly calculate just about any bound and it will work. However, I still can't disprove that if the set does make every number, then the non-greedy limit will be less than the lcm or not. That's all that I have to share.

→ Reply