-2

I have encountered the minimum coin change problem on CodeChef and CodeForces. On both sites I have submitted my implementation using DP. This implementation given TLE error on both sites.
Unfortunately, I cannot find any other implementation of this problem.
I am linking the problems - CodeChef - https://www.codechef.com/problems/FLOW005
CodeForces - https://codeforces.com/problemset/problem/996/A
Here is my code(CodeChef implementation) -

int main() {
    int T{};
    std::cin >> T;
    for (int i = 1; i <= T; ++i) {
        int N{};
        std::cin >> N;
        std::vector <int> arr(N + 1);
        for (int i = 0; i < N + 1; ++i) {
            arr[i] = minCoins(i, arr);
        }
        std::cout << arr[N] << std::endl;
    }

    return 0;
}

The minCoins Function -

int minCoins(int x, std::vector <int> arr) {
    if (x == 0)
        return 0;
    else if (x == 1 || x == 2 || x == 5 || x == 10 || x == 50 || x == 100)
        return 1;
    int min{ 1 + arr[x - 1]};
    if (x > 100)
        min = std::min(min, l + arr[x - 100]);
    if (x > 50)
        min = std::min(min, 1 + arr[x - 50]);
    if (x > 10)
        min = std::min(min, 1 + arr[x - 10]);
    if (x > 5)
        min = std::min(min, 1 + arr[x - 5]);
    if (x > 2)
        min = std::min(min, 1 + arr[x - 2]);
    if (x > 1)
        min = std::min(min, 1 + arr[x - 1]);
    return min;
}

There is no problem of integer overflow as I chose int data type after reading the constraints. Also, if anyone would like to suggest how I can remove the if ladder and replace it with something simpler, I would appreciate the help. Also, thank you for taking the time to read my question :)

Nishant Joshi
  • 13
  • 5
  • Dynamic programming overkill. Change is greedy, and currency systems are designed this way. Always choose the largest coin you can and you'll always choose the minimum number of coins. – sweenish Nov 18 '20 at 17:40
  • I can see why Greedy would take way less time, but I have learned that greedy does not always give the optimal solution and in this case the minimum coins required for the change – Nishant Joshi Nov 18 '20 at 17:44
  • You are incorrect. – sweenish Nov 18 '20 at 17:48
  • 2
    It's possible to come up with values of coins for which the greedy algorithm gives incorrect results. If your denominations are `16, 15, 5, 1`, a greedy algorithm will make `20` cents using five coins when it could get away with using only two. However, in the actual US currency system, the greedy algorithm is always correct. In particular each denomination is at least twice as large as the next-largest denomination--I don't know if that's a necessary condition for the greedy algorithm to always be correct, but it's sufficient. – Nathan Pierson Nov 18 '20 at 17:55
  • Actually I'm incorrect above, the doubling thing there is neither necessary nor sufficient, but there's some discussion [here](https://stackoverflow.com/questions/13557979/why-does-the-greedy-coin-change-algorithm-not-work-for-some-coin-sets) about how exactly to characterize when the greedy algorithm is guaranteed to be correct. 100, 50, 25, 10, 5, 2, 1 is a set of denominations where it does work. – Nathan Pierson Nov 18 '20 at 18:02
  • What do you hope to learn from these contest/challenge/competitive coding/hacking sites? If it's to learn C++, you won't learn anything there. Like in this case, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program either runs slow, or fails to handle an obscure edge case. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Nov 18 '20 at 18:02
  • @NathanPierson Of course it's possible to devise a broken currency system. Again, not what was I saying. It also doesn't apply to the problems linked (and not described) in the question. – sweenish Nov 18 '20 at 18:07
  • @sweenish I just wanted to be very explicit about what the asker was and was not correct about when they stated that the greedy algorithm doesn't always give the optimal solution. – Nathan Pierson Nov 18 '20 at 18:11
  • I can respect that. – sweenish Nov 18 '20 at 18:13

2 Answers2

2
#include <iostream>

int main() {
  int tests;
  std::cin >> tests;

  int value;
  while (tests--) {
    int coinCount = 0;
    std::cin >> value;
    while (value > 0) {
      if (value >= 100) {
        coinCount += (value / 100);
        value %= 100;
      } else if (value >= 50) {
        coinCount += (value / 50);
        value %= 50;
      } else if (value >= 10) {
        coinCount += (value / 10);
        value %= 10;
      } else if (value >= 5) {
        coinCount += (value / 5);
        value %= 5;
      } else if (value >= 2) {
        coinCount += (value / 2);
        value %= 2;
      } else if (value >= 1) {
        coinCount += (value / 1);
        value = 0;
      }
    }
    std::cout << coinCount << '\n';
  }
}

Tested on CodeChef and passed with execution time of 0.00. The currency systems shown in the problems are designed in such a way that the greedy choice is the correct choice. This holds true for very nearly if not all existing currency systems.

If you require proof, http://www.cs.toronto.edu/~denisp/csc373/docs/greedy-coin-change.pdf

sweenish
  • 4,793
  • 3
  • 12
  • 23
  • I implemented a greedy solution similar to your answer and it worked just fine. I think I lacked the understanding of why and when greedy approach breaks in coin change problem so as soon as I see this problem, I think DP. Thank you for your answer. – Nishant Joshi Nov 19 '20 at 03:22
0

My Simple Solution:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    vector <int>v{100, 20, 10, 5, 1};
    // vector <int>v{1, 5, 10, 20,  100};
    int n;
    while (cin >> n)
    {
        int mSum(0);
        for (int i:v)
        {
            if (n >= i)
            {
                mSum += n / i;
                n %= i;
            }
        }
        cout << mSum << endl;
    }
    return 0;
}
Fahad
  • 1
  • 2