MIUP 2012 Problema C - Um algoritmo ganancioso

A Maratona Inter-Universitaria de Programação (MIUP) 2013 é já no próximo sábado.
A minha última participação foi em 2009 (equipa LuscoFusco) e não tenho seguido com muita atenção as últimas edições da prova. Dada a proximidade da MIUP deste ano, estão disponíveis para treino os problemas de alguns concursos, incluindo os da MIUP 2012. Eu decidi ir resolver os problemas for fun.

Penso que os problemas são equilibrados, com um nível de dificuldade adequado e incluindo alguns problemas com casos particulares para distinguir as equipas com mais atenção ao detalhe. A única critica negativa que faço é ao problema D onde penso que não é claro no enunciado que os carros a colocar num ferry têm de ser consecutivos no input (e isso faz toda a diferença na solução).

O problema que gostei mais foi o problema C - Humanitarian Logistics. Sucintamente, temos N caixas de alimentos, cada uma com um tempo de validade T_i (em dias) e um valor V_i. Em cada dia, podemos escolher uma das caixas cuja validade não tenha expirado para distribuir pela população. O objectivo é minimizar o desperdício, isto é, o valor das caixas cuja validade expira antes de serem entregues, e imprimir os índices (de ordem no input) das caixas que serão entregues por ordem crescente de índice.

Os limites são 1 ≤ N ≤ 100,000;  1 ≤ T_i ≤ N;   1 ≤ V_i ≤ 100,000. Como resolver o problema de forma eficiente?

A restrição fundamental do problema é que só podemos escolher uma caixa em cada dia.
Um ponto também importante é que a validade das caixas começa a contar ao mesmo tempo para todas, desde o dia zero. Assim, se nós decidimos distribuir uma caixa, faz sentido que o façamos o mais próximo da data de validade possível, de modo a podermos distribuir outras caixas antes desta.

Mas que caixas é que devemos escolher para distribuir? Como já referi, só podemos escolher uma caixa por dia. Como o objectivo é minimizar o desperdício, nós devemos distribuir as caixas com maior valor possível. Sendo assim, podemos seguir o seguinte algoritmo:

1. Ordenar as caixas por ordem decrescente de valor. Em caso de valores iguais, ordem de ocorrência no input
2. Percorrer as caixas por ordem decrescente de valor:
1. Seleccionar o tempo mais tarde possível dentro da validade para a distribuir.
2. Se for possível distribuir a caixa, adicionar o seu índice a um vector que contém a resposta.
3. Ordenar os índices das caixas que vamos distribuir e imprimir os índices.

Para cada caixa, estamos a seleccionar o tempo mais tarde possível, independentemente das caixas que vamos escolher a seguir. Deste modo, dizemos que este é um algoritmo ganancioso (greedy).

É difícil provar que um algoritmo ganancioso está correcto. A experiência e a intuição valem ouro, mas em caso de dúvida (ou wrong answer), podemos comparar o nosso greedy com uma solução mais lenta mas que temos a certeza que dá a resposta certa (tipicamente um brute force que testa todas as soluções possíveis).

A ordenação dos passos 1 e 3 pode ser feita em O(N log N) com as funções standard já referidas noutros posts.
Intuitivamente, podíamos usar um array com N posições e marcar as caixas que são distribuídas em cada dia. Este array podia ser usado para procurar o dia mais tardio para distribuir cada caixa. O problema é que esta procura linear teria um tempo de execução de O(N) para cada caixa, fazendo com que a solução tivesse um tempo de execução O(N²). Como vimos em posts anteriores, O(N²) é demasiado lento com este limite de 100,000.

Existem vários métodos para efectuar esta pesquisa de uma forma mais eficiente. Uma boa alternativa é usar as bibliotecas standard. O set da STL do C++ permite pesquisas num conjunto ordenado de valores em O(log N).
Podemos criar um set com os tempos 1..N disponíveis para distribuir caixas. Para cada caixa, queremos o tempo mais tardio possível para a distribuir. Para isto, podemos procurar pelo primeiro tempo superior à data de validade da caixa e verificar se existe algum tempo disponível antes deste. Se existir um tempo disponível, basta eliminar esse tempo do set para deixar de estar disponível.

Para cada caixa efectuamos uma pesquisa e eventualmente uma eliminação. Ambas correm em O(log N). Deste modo o passo 2 é feito em O(N log N), logo a solução tem um tempo total de execução de O(N log N) que é suficientemente eficiente para um limite de N ≤ 100,000.

Ver as funções upper_bound(), begin(), insert() e erase() dos sets e o uso de iteradores para avançar/recuar numa colecção de elementos. O uso do sort e do set permite uma solução curta e elegante - outra vantagem de conhecer as bibliotecas standard. A minha resolução em C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include <stdio.h> #include <set> #include <vector> #include <algorithm> using namespace std; struct Caixa { int id, valor, t_validade; bool operator < (const Caixa& c) const { if (valor != c.valor) return valor > c.valor; // ordena por ordem decrescente de valor return id < c.id; // e crescente de id se o valor for igual } } caixas[100002]; int main() { int i, N; set<int> tempos; set<int>::iterator it; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d %d", &caixas[i].t_validade, &caixas[i].valor); caixas[i].id = i+1; tempos.insert(i+1); } sort(caixas, caixas+N); // ordena por valor e id. ver acima vector<int> res; for (i = 0; i < N ; i++) { it = tempos.upper_bound(caixas[i].t_validade); if (it == tempos.begin()) // não há tempo anterior disponível continue; --it; // elimina o tempo anterior tempos.erase(it); // dos tempos disponíveis res.push_back(caixas[i].id); // adiciona a caixa ao resultado } sort(res.begin(), res.end()); // ordena antes de imprimir o resultado for (i = 0; i < (int)res.size(); i++) printf("%d\n", res[i]); return 0; }