Eu pensei bastante e até cheguei a uma solução para o problema, porém, antes de implementar eu fiquei curioso e dei uma olhada na resposta do primeiro colocado. Era tão simples que eu fiqui abismado e fui pesquisar para saber como ele tinha chegado àquela solução. Depois de muita pesquisa eu cheguei um site de um brasileiro que também não conseguiu entender a solução (http://diogobohm.net/2013/09/27/code-jam-2010-africa-problem-c/), mas, por fim, consegui achar uma conversa no fórum do TopCoder que falava de um algoritmo greedy, dizendo que seria a solulção, e indicaram um artigo bem completo sobre o assunto: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg. Também disseram que tinha um problema semelhante no TopCoder: http://community.topcoder.com/stat?c=problem_statement&pm=2420&rd=5850&rm=151070&cr=272072.
Eu li boa parte do artigo, mas parei na parte que ele sugeriu resolver um problema de uma competição anterior do TopCoder. Foi quando eu instalei o ambiente do TopCoder para poder participar das competições e também para tentar fazer os problemas anteriores.