We provide counterexemples for both data sets (i.e. both incorrect programs) and we also provide correct algorithm for solving the problem of little John.
First, let us see how the algorithm implemented in the easy data set works. Function payClassic takes the price V and finds the coin with highest value not higher than V. It decides to use this coins for paying, subtracts its value from V and tries to pay the rest in the same way. Counterexample can be for example following input:
0 3 1 0 0 0 0 0 0 0 6
John has to pay 6 TD and he has 3 coins of value 2 TD and 1 coin of value 5 TD. Clearly it is possible to pay the amount using 3 coins of value 2 TD. Function payClassic first uses 5 TD coin. Now it is necessary to pay 1 TD. But it is not possible to pay 1 TD using 2 TD coins. Thus the function output -1.
The algorithms in the difficult data set tries to patch this problem somehow. It computes several different solutions and finds best of these solutions. First, it computes the solution given by payClassic. All considered solutions are such that they contain several coins of the same value and the rest of the price is payed by payClassic. However the set of solutions considered in this algorithm does not always contain the best solution.
For counterexample given above this algorithm works correctly. Solution consists of 3 coins of the same value and therefore it is among solutions computed in this algorithm. Let us consider following input:
0 3 1 0 3 1 0 0 0 0 66
The only solution for this input contains 3 coins of value 2 TD and 3 coins of value 20 TD. Function payClassic uses first 50 TD coin, then 5 TD coin and then 3 coins of value 2 TD. There remains 5 TD to pay but there are only three 20 TD coins. The algorithm in difficult data set tries to use several coins of the same value first. The partial solution produced by payClassic contains all coins except 20 TD coins. Therefore all computes solutions in which 20 TD coins is not used are the same. When the program tries to use 20 TD coins first, it pays 60 TD and it has to pay 6 TD using 5 TD coin and 3 2 TD coins. This is done by payClassic function which does not find a solution. Therefore this input is counterexample for algorithm given in C2.
John's problem can be solved correctly by dynamic programming. Suppose that John has N coins. We will compute for each i=0,1,2,..,N and for each j=0,1,2,...,V the smallest number of coins need for paying price j if we can use only first i of John's coins. More precisely we compute whether it is possible at all to pay j using only the first i coins and only if it is possible we compute the smallest number of coins needed.
If we know these values for some i, we can easily obtain values for i+1. If we want to pay value j using first i+1 coins, we can either use the (i+1)-th coin or not. If we do not use this coin, the best solution is the same as using only the first i coins. Now let us suppose that we use the (i+1)-th coin and that the value of this coin is k. Then the rest of the price is payed by the best solution for the first i coins and price j-k. If a[i][j] is the best solution for first i coins and prize j, we have
The formula given above is simplified because it does not take into account possibility that for some values of i and j the problem does not have any solution. Moreover the formula is valid only for j>=k. However when we handle these two exceptions, we get the correct algorithms. Its time complexity is O(NV) that can be further improved to O(V log N) if we process all the coins of the same value at the same time (this improvement is not implemented in the given program).