Prazo de submissão: 15 de Maio (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. Relembre 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 programação dinâmica. Será por isso conveniente ver o que foi falado nas teóricas:
Slides (capítulo "5 - Árvores Binárias de Pesquisa Equilibradas")
Exercício 1) Usando as implementações de árvores de pesquisa da sua linguagem
Quase todas as linguagens têm uma implementação de árvores de pesquisa equilibradas que garantem operações logarítmicas para pesquisa, inserção e remoção. O objectivo deste exercício é conhecer duas dessas estruturas, que nas versões actuais dos compiladores respectivos são implementadas usando árvores red-black:
Para os estudantes que usam C, a ideia neste exercício é verem o código de C++. Vão notar que o código é quase igual, incluindo na maneira de ler e escrever (podem pensar no C como um subset do C++), mas que usa pedaços de C++ quando necessário. Para compilarem basta usar g++ na linha de comando em vez de gcc (ex: g++ -Wall -o bst bst.cpp)
Basicamente o problema pede-lhe para arranjar maneira eficiente (logarítmica) de suportar três operações:
Inserir elementos num conjunto (podem haver elementos repetidos)
Retirar o elemento mínimo
Retirar o elemento máximo
As estruturas de dados set e TreeSet não suportam elementos repetidos, pelo que temos de lidar com isso. Fica a sugestão de usarem uma de duas hipóteses:
Usar um multiset de C++ que suporta elementos repetidos (ver documentação). Para retirar um elemento podem simplesmente chamar a operação erase sobre um iterador "normal" (não invertido - para irem à posição final podem ir ao .end() e decrementar uma posição).
Usar um map (C++) ou TreeMap (Java) de inteiros para inteiros onde guardam para cada energia de bakugan o número de elementos com essa energia. Assim, ao adicionar podem incrementar o contador respectivo e ao retirar pode decrementar, apagando-o do mapa se o número chegar a zero.
Se usar Java, não se esqueça de ler com a classe FastScanner (podem existir 110 mil linhas de input)
Exercício 3) Um problema de implementação de árvores
Como o enunciado mostra, apenas existem 83681 palavras válidas
A sugestão é por isso gerar (uma única vez, no início da execução) todas as palavras válidas, e guardá-las numa árvore binária de pesquisa (um mapa que associa uma string ao seu número ordem)
Para responder a cada pergunta basta agora ir ao mapa e ver se a palavra existe (como chave), devolvendo o valor correspondente (esta operação tem custo logarítmico, pois a árvore é equilibrada)
Vou deixar ficar para já só estas dicas, deixando ficar para vocês pensarem como gerar as palavras válidas (sendo que existem várias maneiras diferentes de o fazer); se tiverem dificuldades contactem-me no Slack
Se usar Java, não se esqueça de ler com a classe FastScanner e escrever com a classe FastPrint (podem existir 50 mil linhas de input e de output)
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 é mais fácil que os das semanas anteriores, e não envolve nenhum tipo de matéria de que não tenhamos já falado. A dificuldade passa unicamente em como ser eficiente na resposta das queries (que podem ser 100 mil), sendo que por isso um algoritmo quadrático não passará no tempo. O problema está disponível para submissão no Mooshak: