Roteiro 11

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

< Voltar para: Roteiros | Roteiro 10

Introdução

Neste roteiro, você será apresentado a estruturas de dados que resolvem problemas bem interessantes de forma eficiente. As estruturas apresentadas aqui aparecem em vários problemas tanto como principal elemento na solução quanto como solução para um subproblema de um problema maior. Naturalmente, as estruturas de dados estudadas não são universais: em cada problema, você deverá adaptá-la segundo as suas necessidades. Por isso, não adianta tê-las implementadas na biblioteca de código do seu time e não as entender bem. A principal estrutura apresentada será a Árvore de Segmentos.

Materiais de apoio

Links que você deve ler antes de resolver os problemas:

Problemas

Lista de problemas para serem resolvidos. A solução está disponível, mas recomendamos que não a consulte antes de sofrer horrores com o problema. Os problemas em negrito são os mais importantes. Faça-os antes de prosseguir para o próximo roteiro. O aquecimento (questões em rosa) não é sobre árvore de segmento mas para estrutura de dados em geral. Muito bom para se aquecer para as demais questões.

Roteiro 11
# Problema Link Online Judge Nível Observações
1 BORABORA Bora Bora SPOJ-BR 1 Aquecimento - Simulação
2 BOLSA Bolsa de Valores SPOJ-BR 2 Aquecimento - std::priority_queue
3 Live Archive 6139 Interval Product Live Archive 3 -
4 SUBSEQ Counting Subsequences SPOJ 3 -
5 ANDROUND AND Rounds SPOJ 3 -
6 TOPOLAND To Poland SPOJ 3 -
7 Live Archive 5798 Jupiter Attacks! Live Archive 3 -
8 APAGA Apagando e Ganhando SPOJ 2 A solução "correta" é gulosa. Tente resolver usando RMQ
9 BANFARAO Banco do Faraó SPOJ-BR 3 -
10 URI1500 URI1500 URI 3 -
11 NICEDAY The day of the competitors SPOJ 4 -

Próximo roteiro

No roteiro seguinte estudaremos, mais uma vez, Programação Dinâmica. Desta vez, os problemas serão um pouco mais desafiadores que no roteiro 4. Recomendamos que você avance apenas depois de ter entendido bem Árvores de Segmentos e ter feito, pelo menos, 6 dos problemas sugeridos, incluindo os em negrito.

Link para o Roteiro 12

Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas