a bit of uva: UVa 11264 - Coin Collector (Greedy Algorithm)

Problem:
UVa 11264 - Coin Collector

Summary:
Given a set of coins, find the maximum number of different coins that one can obtain from a single withdrawal. A withdrawal of sum S will be determined following this algorithm:
1. Let C be the maximum coin such that \(S \geq C\)
2. Give C to the withdrawer, set S = S - C, and repeat 1 until S = 0

The huge search space of the problem suggests that there exist a greedy solution, and indeed one exist. The following code describes the algorithm:

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;

ll arr[1005];
int N;

int main(){
 int TC;
 scanf("%d",&TC);
 while(TC--){
  scanf("%d",&N);
  for(int i=0;i<N;++i){
   scanf("%lld",&arr[i]);
  }
  ll trail=0;
  int k=0;
  for(int i=0;i<N;++i){
   if(trail < arr[i]){
    trail += arr[i];
    ++k;
   } else {
    trail -= arr[i-1];
    trail += arr[i];
   }
  }
  printf("%d\n", k);
 }
 return 0;
}

My idea was that the problem can be reduced to choosing a set of coins \(P = {c_1, c_2,\ldots, c_k}\) such that for any \(i = 1,2,\ldots,k\), the following invariant is maintained: \(\sum_{n=1}^{i-1} c_n < c_i \). The rest of the story is to ensure that following the withdrawal rules above, we will indeed end up with \(|P| = k\) coins, and that the set P is indeed optimal.

Just a reflection: problems that require a clever greedy solution actually push more burden to the programmer to make observations and prove the correctness of the algorithm, and once the greedy solution has been constructed, the program just need to do very little work. It's very interesting, since in most other cases, the inverse is true: we do little thinking while the program handle the heavy-lifting.