Maratona De Programacao
Aqui eu coloco algumas dicas sobre Maratonas de Programação, uma das atividades que considero das mais importantes para cientistas da computação.
Background
Entrei na UFRGS em 2008. Lá em todo semestre há maratonas de programação na semana acadêmica, participei já no primeiro. A primeira maratona sempre há alguns tropeços em como tratar entrada e saída.
Em 2009, montamos um time: eu, Kauê Silveira e Bruno Fiss. Nosso time chegou a final nacional. Infelizmente, não participei tanto pois estava mais focado em escrever um artigo para a bolsa :/
Fiz a cadeira de Desafios de Programação em 2012/1. A cadeira é básica, mas fundamental para entender (e revisar) os principais fundamentos cobrados em maratonas.
Em 2012, formamos outro time. Duas semanas antes da regional, começamos a treinar pelas regionais passadas. Na regional em Pelotas/RS ficamos em primeiros colocados. Porém não ficamos contentes com nosso desempenho: eu travei num problema (que resolvi sem muito esforço mais tarde), não lemos todos os problemas com cuidado (havia um fácil que foi mal interpretado) e num problema deveriamos saber sobre Euler Totient. :/
Continuamos praticando para a final. Alguns tópicos praticados foram: Suffix Array, LCP, Segment Tree, Rolling Hash, ... A final foi em Londrina/PR, ficamos em 12º. Entre os problemas, fiz um de Segment Tree rapidamente, porém por descuido eviei sem verificar alguns casos, tomamos uma penalidade. Em 2h de competição estavamos travados, resolvemos fazer um de grafos. Demoramos o resto da competição para fazer, sendo o André quem mais puxou nesse problema. Passamos nos últimos 3 minutos. Como nos últimos minutos de competição não dá para saber os resultados, só ficamos sabendo quando o placar foi anunciado no final da competição.
Livros e Material
Art of Programming Contest, Ahmed Shamsul Arefin
Livro bem básico e rápido. Problemas simples (e também antigos). Ótimo para começar.
The Hitchhiker’s Guide to the Programming Contests, Nite Nimajneb
Livro mais avançado, possuí vários conceitos básicos, mas que não caem diretamente em competições. Ler, entender e levar para competições.
Competitive Programming, Steven Halin
Livro da cadeira de Desafios e Programação. Os problemas desse livro são dividos em nível de dificuldade e podem ser encontrados no uHunt.
CS 97SI: Introduction to Competitive Programming Contests
Curso da Universidade de Stanford. Na página há slides com muito conteúdo para estudar: http://www.stanford.edu/class/cs97si/
Há também a cola usada pela equipe de Stanford: http://stanford.edu/~liszt90/acm/notebook.html.
Curso: Algorithms, Robert Sedgewick, Kevin Wayne
Curso online da Universidade de Princeton. Baseado no livro Algorithms (4th Edition). Curso impotante para solidificar o conhecimento em algorítimos.
TopCoder Algorithm Tutorials
https://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index
Lista com artigos sobre os principais algoritimos e técnicas cobrados em competições de programação. Alguns são mais avaçados. O interessante é que os artigos são inteiramente focados em competições.
Algoritimos mais importantes
Discussa feita no Quora sobre quais são os principais algoritmos para resolver desafios de programação.
Sites de desafios
Alguns sites com desafios para praticar são:
- uHunt - Usa o banco de problemas do UVa e sugere outros problemas para serem resolvidos
- Topcoder
- Codeforces
- Hacker Rank Challenges - Tem problemas interessantes e bem desafiadores. Algumas empresas usam esse site para recrutamento.
- Hacker.org
- Project Euler - Desafios matemáticos
Algumas sites de competições são:
O que estudar
Há uma discussão interessante no Quora sobre quais são os principais algoritmos: Quora - What are 10 algorithms one must know in order to solve most algorithm challenges/puzzles?
Abaixo coloco minha lista de tópicos que considero importante.
Data Strucutres
- Stacks/Queues/Heaps/...
- Segment Tree
- BitVec
Graph
- DFS
- BFS
- Topological Sort
- Kruskal
- Prim
- Dijkstra (with previous nodes)
- Bellman Ford
- Floyd-Warshall (minimax, maximin, safest path, transitive hull)
Dynamic Programming (DP)
- Knaspack
- LIS/LDS (n^2 e n log n)
- LCS
- Counting Change
Math and Number Theory
- Base Convertion
- GCD/LCM
- Primes, sieve
- powMod
- Fibonacci Mod
- Polar coordinate system
- LatlongDistance
- Modular arithmetics
- Combinatorics
- Totient
- Carmichael Number
- Catalan Formula
- Recursion as matrix exponentiation
Geometry
- Point, distance, triangle area, collinear, counter-clockwise
- Line, parallel
- Convex Hull: Graham Scan
Strings
- Suffix array
- LCP
* A lista está incompleta, ainda deve ser finalizada!!
blog comments powered by Disqus