Treinamento

[Aritanan Borges Garcia Gruber <gruber@ime.usp.br>]

Olá a todos.

Bem vindos à lista de discussão sobre a maratona de programação 2003 do IME-USP.
Para quem não me conhece, meu nome é Aritanan; para quem conhece, eu sou o pil.
:) E tenho treinado os times do IME nos últimos cinco anos...

Como vocês bem sabem, no próximo dia 17/08, realizaremos nossa maratona de
número VII. Por um lado, a Maratona é uma oportunidade de diversão sem igual.
Por outro, representa a chance de integrar um time do IME na sulamericana da
ACM, em novembro, e quem sabe, chegar a participar das finais mundiais de 2004
em Praga, na República Tcheca.

Neste ponto, alguns de vocês podem estar a se perguntar: E como faço para obter
um bom resultado na Maratona? A resposta é simples: treino! Quanto mais, melhor!
E também existem alguns algoritmos que devem ser prontamente conhecidos.

Sobre a parte de treinos, existem alguns juízes automáticos na www. O mais
famoso deles é o de Valladolid:

  http://online-judge.uva.es/

Vários problemas utilizados em regionais (e até em finais) passadas estão lá
disponíveis, esperando suas submissões. Alguns são muito fáceis, outros mais 
interessantes. Aliás, aqui está uma lista de bons problemas para um treinamento
(compilada por Steven Skiena):

  http://www.cs.sunysb.edu/~skiena/392/hw.txt

O site dele em 

  http://www.cs.sunysb.edu/~skiena/392/

tem um monte de outras informações úteis. Não deixe de vê-lo!

Outro juíz automático mora em:

  http://acm.timus.ru/

Alguns problemas aqui são triviais. Outros são de tirar o chapéu. :)

É possível também participar de concursos on-line em:

  http://online-judge.uva.es/contest/

  http://ipsc.ksp.sk/

Não esqueçamos do arquivo de regionais/finais da própria ACM (mas estes não têm
correção automática).

  http://www.acm.inf.ethz.ch/ProblemSetArchive.html

  http://icpc.baylor.edu/past/default.htm

Existiam fundamentalmente, no passado, dois tipos de prova: a americana e a 
européia. A prova americana visava a codificação. Linhas e linhas de código em
uma coleção de problemas de baixa complexidade. A versão européia era muito mais
elaborada. Problemas que geralmente envolviam sacadas teóricas e codificação
curta e limpa. Atualmente esta distinção foi atenuada, mas a favor do estilo
europeu. (Digamos 75% a 35%.) Minha sugestão é que vocês comecem com provas 
americanas e depois utilizem as européias.

O é recomendado saber?
Algoritmos em grafos como

. buscas em largura e profundidade
. componentes conexos, fortemente conexos, ordenação topológica
. dijkstra e floyd-warshall para caminhos mínimos
. kruskal e prim para árvores geradoras mínimas
. emparelhamento máximo / cobertura mínima em grafos bipartidos.
. noções de problemas de fluxo máximo, fluxo de custo mínimo (desejáveis).

Algoritmos de enumeração de subseqüências, k-subseqüências (combinações) e
permutações. Busca exaustiva (backtracking).

Algoritmos de geometria computacional como

. par mais próximo
. fecho convexo
. interseção de segmentos
. teste de pertinência de pontos a polígonos

Algoritmos gulosos, programação dinâmica, noções de problemas NP-completos
e NP-difíceis, noções de programação linear, noções de autômatos, linguagens
formais e compilação.

Livros úteis:

. Introduction to Algorithms, 1st or 2nd edition.
  Cormen, Leiserson, Rivest, Stein (only in 2nd).

. Programming Challenges.
  Skiena, Revilla.

. The Algorithm Design Manual.
  Skiena.

. Programming Pearls.
  John Bentley.

. Network Flows: Theory and Algorithms.
  Ahuja, Magnanti, Orlin.

. C: The Programming Language (ANSI Standard).
  Kerninghan, Ritchie.

. Combinatorial Algorithms.
  Keher, Stinson.

Provavelmente esquecí de algum. Se você se lembrar, me escreva. :)

Bom, ficou um pouco bagunçado, mas é isso aí. Mãos à obra, divirta-se e
boa sorte. 

[]'s

pil

--
"Some moments are longer than lifetimes."
                          -Max Rebo Kids