Módulo Algoritmos Greedy
Este é mais um tema central a concursos e a ciência de computadores. Veremos como identificar certas propriedades de problemas que permite aplicar certas ideias muito simples para os resolver eficientemente.
Neste módulo temos 2 artigos muito importantes e temos ainda um terceiro opcional. No primeiro vamos introduzir o conceito e vamos ver como é que certas ideias gerais podem ser aplicadas a todos os problemas, mesmo os que não admitem uma solução greedy:
Artigo: Introdução a algoritmos greedy
Neste artigo introduzimos o conceito e vemos os exemplos clássicos.
De seguida vamos ver alguns exemplos clássicos de problemas que admitem soluções greedy. Ver exemplos clássicos de problemas que aplicam um certo conceito é extremamente importante, visto que além de conterem a maior parte das ideias relevantes ao conceito, é muito comum conseguir generalizar as suas ideias para resolver outros problemas. Ei-lo:
Artigo: Exemplos de problemas greedy clássicos
Aqui vemos vários exemplos práticos assim como aplicações gerais do método.
Finalmente temos um terceiro artigo opcional. Este artigo é extremamente avançado e de relevância marginal para concursos. Não é recomendado que o leiam sem antes de dominarem todos os restantes módulos. Além disso requer alguma maturidade matemática, nomeadamente conhecimento de cálculo e álgebra linear. Por isso não se sintam mal em ignorá-lo!
Artigo: Ótimização convexa
Um artigo muito avançado sobre um tema teórico interessante.
Agora que já olharem para este tipo de problemas, podem começar a identificar problemas onde isto é útil. Por exemplo, considerem o problema B da final das ONI de 2017, Passeio de metro, conseguem ver que propriedade interessante do problema permite utilizar um conceito greedy? Se quiserem ler as solução do problema está disponível aqui.
Problemas de consolidação
Este conjunto de problemas é constituído por alguns problemas extra um pouco mais difíceis, mas que resumem bem a maioria dos tópicos dos artigos. Alguns dos problemas requerem que conjuguem ideias greedy com outras técnicas
Nota: A fonte dos problemas representa a plataforma de submissão (todos são submetiveis) e não o concurso onde apareceu.
- Minimum Scalar Product (fonte: kattis, minimumscalar);
- Polycarp at the Radio (fonte: CodeForces, Ronda #375, Div. 2, C) | Solução;
- Contest Balloons (fonte: CodeForces, Canada Cup 2016, C) | Solução;
- Polycarp's problems (fonte: CodeForces, Technocup 2017, Round 1, B) | Solução;