Prazo de submissão: 8 de Novembro (submeter no Mooshak de DAA)
Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem. Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relebre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Conteúdos das teóricas
Nesta aula iremos abordar conceitos de algoritmos greedy. Será por isso conveniente ver o que foi falado nas teóricas:
Exercício 1) Considere o problema do caixeiro viajante (versão
euclideana): dados N pontos no plano, arranjar o ciclo mais curto que
visita todos os pontos.
Imagine que começa num ponto qualquer e depois segue uma escolha
greedy. Para cada uma das hipóteses a seguir mencionadas,
arranje um caso onde a escolha greedy daria uma solução ótima e
também um contra exemplo onde essa mesma escolha não daria
uma solução ótima.
Em cada passo escolher o ponto não visitado mais à
esquerda (menor coordenada X). No final ligar o último ponto escolhido
ao primeiro.
Em cada passo escolher sempre o ponto não visitado mais próximo do ponto actual. No final ligar o último ponto escolhido ao primeiro.
Exercício 2) Considere o problema do troco: dada um conjunto de moedas S e uma quantia K, descobrir o menor número de moedas de S que somadas dão a quantia K (podendo repetir moedas).
Considere o algoritmo greedy de em cada passo escolher a maior moeda que não faz passar da quantia K.
Indique um conjunto de moedas S para o qual o algoritmo greedy não é ótimo para fazer a quantia K=100.
Indique uma quantia K para o qual o algoritmo greedy não é ótimo se o conjunto de moedas for S={1,15,50}
Será que basear-se apenas no tempo de execução chega? Consegue arranjar um contra-exemplo onde não basta começar pelo par de sapatos que demora menos tempo?
Será que basear-se apenas na multa chega? Consegue arranjar um contra-exemplo onde não basta começar pelo par de sapatos que tem maior multa?
Que escolha consegue imaginar baseada ao mesmo tempo no tempo e na multa?
Exercício extra) Alguns problemas greedy III
Este exercício é um extra, e não é considerado essencial no contexto desta aula. Use-o se quiser consolidar os seus conhecimentos num problema um pouco mais complicado, pois implica ser eficiente (para além de correcto).
Para este problemas as dicas estão "escondidas" atrás do botão seguinte (que lhe permite experimentar tentar resolver sem as ler primeiro, se preferir). Além da estratégia greedy, a dificuldade principal aqui é conseguir ser eficiente: como pode, existir N=100 mil balões, a solução não pode ser quadrática e tem de ser pelo menos linearítmica, ou seja O(n log n).
Existem várias estratégias greedy possíveis. Aqui vamos explorar só uma delas.
Em relação ao balão mais à esquerda, é inevitável que tenhamos de disparar uma flecha que comece por o atingir a ele, certo?
Uma vez atingido esse balão, o resto do percurso fica "inevitável", e o que sobra é um problema "igual" ao primeiro, mas com menos balões, onde podemos aplicar o mesmo processo
Quando estamos a simular o percurso depois de começar pelo balão mais à esquerda ainda não rebentado, precisamos de responder à pergunta: "Qual é o primeiro balão ainda não rebentado, que está na altura H-1 e está localizado à direita de uma posição P?. Esta pergunta vai ter de ser respondida O(n) vezes, pelo que:
Uma solução naive que linearmente procure o balão vai implicar um custo total quadrático, pelo que não é suficiente para ter os 100 pontos.
É necessária solução pelo menos logarítmica para esta pergunta (que resulta em O(n log n) para o programa completo). A sugestão que damos é manter um array do tamanho da altura máxima, sendo que cada posição do array guarda o conjunto de balões a essa altura.
Cada posição deste array, um conjunto de inteiros (alturas), pode ser por exemplo mantida com um set (em C++) ou um TreeSet (em Java). Pode ver exemplos de uso em C++ ou Java.
As estruturas de dados atrás mencionadas são implementas com árvores binárias de pesquisa equilibradas (iremos falar disso noutro capítulo) e possibilitam perguntar precisamente qual o menor número maior que uma dada posição (lower_bound ou ceiling).
Se estiver a usar C, esta é uma boa oportunidade para experimentar incorporar um pouco de C++. Pode usar todo o resto do programa em C "puro", incluindo ler com scanf e print, mas adicionar o uso do set, "bastando" para já usar a extensão .cpp e compilar com g++ ao invés de gcc.
Caso esteja em Java não se esqueça de ler com o FastScanner.
Nota: É também possível uma solução O(n) para o problema. Consegue imaginar? (dica: tente disparar todas as setas ao mesmo tempo...)
Exercício de Desafio
Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.
Para esta semana o desafio é resolver um problema de "nível MIUP" (a Maratona Inter-Universitária de Programação), o concurso de programação mais prestigiado para alunos universitários nacionais. O problema, criado por mim, era um dos mais "complicados" da edição 2019 e está disponível para submissão no Mooshak:
Se já tiverem feito tudo e estiverem "presos" neste, e quiserem mesmo fazer o desafio, podem contactar-me para eu "dosear" as dicas, sabendo que este problema é mais complicado que os outros desta aula.
