Re: [cef-maratona] Treinamento

[Marcel Kenji de Carli Silva <magal@linux.ime.usp.br>]

Falae.

Acho que a maioria conhece, mas um bom livro para a implementação de algoritmos
em geometria é o

Computational Geometry in C
Joseph O'Rourke

Afinal, o CLR[S] só tem o pseudocódigo e em geometria a implementação pode ficar
bem complicada.

Citando 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
> 
> 


Marcel K. de Carli Silva (BCC2001 IME-USP)