Como se tornar um programador competitivo
Por Matheus Pimenta (matheuscscp@gmail.com).
Leia este tutorial todo de uma vez! E depois leia de novo, e de novo, e de novo…
Por que se tornar um programador competitivo
- Prêmios.
- Balões de gás hélio p/ falar com a voz engraçada.
- Viajar com amigos.
- Conhecer pessoas, fazer amigos e contatos importantes.
- Adquirir facilidade para aprender Ciência da Computação.
- Adquirir facilidade para aprender qualquer ciência exata.
- Desenvolver capacidade de raciocínio muito acima da média.
- Obter as melhores oportunidades de emprego em Ciência da Computação.
- Porque é legal.
- Porque sim.
- http://www.redgreencode.com/12-reasons-to-study-competitive-programming/
Os três pilares do programador em uma competição
Entre as várias características que podem ser úteis para um programador durante uma competição, as três descritas nesta seção são especiais no seguinte sentido: a falta de apenas uma delas já é um grande abismo entre você e os resultados de mais destaque (medalha, primeiro lugar, vaga na próxima etapa, vaga no mundial, etc.). Se você acha que não possui algumas destas características, não se preocupe, pois você pode adquirir todas elas com trabalho duro e disciplina.
Conhecimento
Descrição: Conheça em detalhes muitos problemas, algoritmos e estruturas de dados.
Por que adquirir: Justificativa desnecessária.
Como adquirir: Em primeiro lugar, nunca tente adquirir durante uma competição um conhecimento que você não possui previamente e é necessário para resolver o problema, pois isto seria extremamente injusto com os outros competidores e você dificilmente seria capaz de obter este conhecimento em tempo hábil. Com certeza, seria mais produtivo tentar resolver outros problemas. Durante o tempo de treino e aprendizado, não tenha medo de encarar livros avançados sobre algoritmos e estruturas de dados em inglês, nem de encarar blogs em inglês, nem blogs em russo, nem blogs em chinês, nem blogs em japonês, nem de encarar aquele assunto que você desconhece completamente. Além disso, fique atento aos assuntos que estão “na moda”, pois “ondas” de problemas sobre um mesmo assunto são muito comuns. Não tenha medo também de pedir para alguém te ensinar alguma coisa ou te ajudar a resolver um problema, pois algum dia esta situação irá se inverter; e neste momento você deve retribuir a ajuda para aquela pessoa desconhecida que mora em outro país e te ajudou! Não tenha medo de encarar o código bagunçado de outra pessoa, pois muitas vezes é só isso que vai estar ao seu alcance para aprender como se resolve o problema. Não tenha medo de gostar de matemática, teoria e demonstrações formais! Não tenha medo!
Esperteza (experiência)
Descrição: Seja esperto para observar detalhes não-triviais.
Por que adquirir: Competições de programação estão muito longe de destacarem apenas quem tem mais conhecimento e de serem apenas sobre implementação de algoritmos. Pouquíssimos problemas se resumem a uma combinação simples de algoritmos e estruturas de dados. Na verdade, é o contrário! Os problemas que colocam o seu time na frente são aqueles onde a combinação de técnicas não é trivial. É necessário observar um fato, uma propriedade matemática que está completamente escondida nas entrelinhas, e somente então será possível construir uma solução para o problema. Mais que isso, a parte difícil de muitos problemas é apenas encontrar esta observação não-trivial. Por exemplo: “As restrições do problema fazem com que o grafo da entrada seja sempre planar! Então podemos aplicar o teorema das quatro cores.” Aplicar o teorema é provavelmente muito fácil e pode ser que todos do seu time conheçam o teorema. Mas será que alguém vai perceber que todos os grafos do problema são planares? Se ninguém perceber, conhecer o teorema não irá adiantar de nada.
Como adquirir: Esperteza é sinônimo de experiência. Quanto mais problemas você resolver, mais propriedades você irá conhecer. Quanto mais problemas sobre uma mesma propriedade você resolver, mais facilidade você terá para enxergar esta propriedade nas entrelinhas de um novo problema. Quanto mais problemas você resolver, mais “truques” você irá conhecer. E, acredite, existe uma quantidade surpreendente de “pequenos truques” que fazem a diferença em programação competitiva. Um “truque” é uma maneira extremamente rápida e eficiente de fazer alguma coisa que a maioria dos programadores comuns ignora. Por exemplo: como decidir se x é potência de 2? Resposta em C++: (x&(x-1))==0 (pesquise!). Hacker não é quem rouba senha de banco. Hacker é quem tem esperteza e conhece vários “truques”, ou seja, vários hacks. A competição realizada pelo Facebook, por exemplo, o Facebook Hacker Cup, não é uma competição relacionada à segurança computacional. Ela segue os mesmos formatos das competições de programação tradicionais. Portanto, seja hacker! E lembre-se: para observar o detalhe que falta é preciso olhar a situação de todos os pontos de vista. É muito comum fracassar em um problema durante uma competição por “viciar” em um único ponto de vista que não ajuda. Se uma abordagem não está funcionando, tente outra!
Agilidade
Descrição: Tenha agilidade para escrever e depurar código.
Por que adquirir: O seu time pode ter o conhecimento e a esperteza necessários para resolver o problema, mas muitos outros times podem não apenas possuir estas mesmas características como podem também possuir um membro que é vencedor de concursos de digitação. Um cenário bastante frequente onde isto pode ser péssimo é no caso de um conjunto de problemas onde a maior parte é fácil e pouquíssimos são difíceis. Estas provas são consideradas “corridas contra o tempo”, pois, em qualquer competição, um único problema fácil não resolvido é uma enorme desvantagem. E quanto maior for a quantidade de problemas fáceis, mais grave esta desvantagem se torna! E não se engane, pois o conceito de “problema fácil” é extremamente relativo. Por “conjunto de problemas fáceis”, entenda “conjunto de problemas que a grande maioria dos times da competição é capaz de resolver sem dificuldade”. Logo, provas em que este conjunto é a maior parte podem aparecer com mais frequência do que você imagina!
Como adquirir: Durante o tempo de treino, resolva muitos problemas e não reaproveite código de um exercício para o próximo: digite todo o código do zero. Tente cronometrar o tempo que você leva para resolver um problema e tente melhorar este tempo constantemente. Faça isto durante várias simulações de competições (como as participações virtuais oferecidas pelo Codeforces). Durante uma competição, tenha impressa uma biblioteca de macros, algoritmos e estruturas de dados implementados nas suas linguagens de programação preferidas que são permitidas em competições (C++ e Python, claro!). Por exemplo, tenha uma macro para escrever apenas
rp(i,a,b)
no lugar de
for (int i = a; i <= b; i++)
Acredite, faz muita diferença! E lembre-se: para ser ágil é necessário manter a calma. A frieza para terminar de codificar e depurar um programa no último minuto de uma competição pode ser o obstáculo entre o seu time e a vaga no mundial! Uma vez, eu participei de uma competição entre duplas. Perto do fim, nossa dupla estava em segundo lugar e eu estava escrevendo o programa que faltava, era um algoritmo bem simples. Faltando 5 minutos, eu travei por conta do nervosismo. Mas o meu colega conseguiu terminar e enviamos o código faltando exatamente dois segundos para o fim da competição. Ficamos em primeiro lugar! A melhor maneira de treinar agilidade sob pressão é participar de várias competições, como os rounds individuais do Codeforces, por exemplo.
Características adicionais que fazem a diferença
- Aprenda a se comunicar, principalmente se você pretende participar de competições entre times. Trabalho em equipe é mais do que importante nesta modalidade: é eliminatório. Ninguém consegue “levar um time nas costas” quando os adversários são times bem preparados e em boa sintonia. E a chave do trabalho em equipe é a comunicação! Aprenda a ouvir as ideias, sugestões e opiniões dos seus colegas de time e se esforce para entender o eles estão dizendo. Aprenda a transmitir com clareza o seu raciocínio e lembre-se de dizer todas as observações que você já fez acerca do problema.
- Aprenda a se comunicar em fóruns e comunidades de programação. Isto inclui aprender a ler e escrever em inglês, inclui aprender cordialidade e boa educação e inclui aprender o uso de notação matemática formal. Aprenda a usar LaTeX em fóruns que oferecem esta funcionalidade!
Agenda para se tornar um programador competitivo
Não há uma maneira “correta” de se tornar um programador competitivo, mas se você se sente na posição de um completo novato e não possui nenhuma experiência, talvez seja uma boa ideia ler as sugestões a seguir.
- Aprenda o básico de programação. (que se resume a: manipulação e armazenamento de dados, entrada e saída, estruturas condicionais, laços de repetição e funções)
- Aprenda a provar/verificar a correção de algoritmos e aprenda a analisar a complexidade de algoritmos. Um algoritmo para um problema é satisfatório se: 1) ele é de fato um algoritmo para o problema, ou seja, ele dá a saída correta para qualquer entrada válida; 2) ele possui complexidade de tempo adequada; e 3) ele possui complexidade de espaço adequada. Pesquise e aprenda o significado destes termos!
- Aprenda o que são estruturas de dados e como usá-las (as mais básicas são: array, vector, linked list, stack, queue, priority queue, sets e maps). Cada ED possui uma complexidade de espaço e um conjunto de operações. Cada operação de uma ED é na verdade um algoritmo, ou seja, possui complexidade de tempo e de espaço. Algoritmos são construídos a partir de estruturas de dados.
- Aprenda todas as características de uma linguagem de programação popular em competições. As mais populares são C++ e Python e cada uma tem seus próprios motivos para ser usada. Aprenda a utilizar todas as funções e estruturas de dados da biblioteca padrão desta linguagem. Aprenda todas as funções e técnicas para entrada e saída que esta linguagem oferece.
- Enquanto completa os estágios de 1 a 4, cadastre-se em algum online judge (por exemplo: URI OJ e UVa OJ) e pratique os conceitos que você está aprendendo, enquanto faz exercícios básicos. Acostume-se com o ambiente e com a formatação dos problemas.
- Nesta primeira etapa, você deve aprender programação, o básico de algoritmos e estruturas de dados e deve se acostumar a utilizar OJs. Após completar os 5 primeiros estágios, você estará pronto para começar o estudo sério. Está na hora de começar a descobrir quais são os tipos de problemas que existem; e quais são as suas soluções.
- Leia a bíblia: o livro Competitive Programming, dos irmãos Halim. Este livro apresenta a maioria dos assuntos, problemas, algoritmos e estruturas de dados que aparecem em competições de programação, incluindo implementações e explicações detalhadas.
- Enquanto estiver lendo o livro dos irmãos Halim, passe um bom tempo exclusivamente em cada assunto, resolvendo vários problemas. Por exemplo: 50 problemas de cada. Aqui vai quase a totalidade dos assuntos que de alguma forma já cruzaram o meu caminho:
- Os quatro paradigmas de algoritmos: busca completa; divisão e conquista; algoritmos gulosos; e programação dinâmica.
- Problemas ad-hoc (problema de Josephus, 2-SAT, problema das oito rainhas, movimentos do cavalo...)
- Busca e ordenação (busca binária, fractional cascading, busca binária paralela, merge sort, contagem de inversões, radix sort, k-th order statistics, wavelet trees...)
- Problemas de intervalo (range minimum/maximum/sum query, algoritmos online e offline, algoritmo de Mo, sparse table, decomposição em raiz quadrada...)
- Estruturas de dados avançadas (disjoint sets union/union-find, árvores de busca binária, heaps, treaps, segment trees, fenwick trees/binary indexed trees, link-cut trees, Euler tour trees, lazy propagation, estruturas de dados persistentes...)
- Strings (autômatos, casamento, prefix function, algoritmo KMP, Z function, trie, algoritmo Aho-Corasick, array de sufixos, hashing...)
- Álgebra (conjuntos, relações, funções, operações, grupos, anéis, corpos, polinômios, FFT/NTT, algoritmo baby-step giant-step/meet-in-the-middle, algoritmo de Floyd para ciclos, algoritmo Pollard’s rho...)
- Teoria dos números (divisibilidade, números primos, teorema fundamental da aritmética, crivo de Eratóstenes, fatoração, funções sobre divisores, teorema de Fermat-Euler, teorema chinês do resto, equações diofantinas...)
- Álgebra linear (espaço vetorial, dimensão e base, espaço linha, espaço coluna, espaço nulo, transformação linear, núcleo e imagem, eliminação gaussiana…)
- Análise combinatória (princípio da inclusão-exclusão, fatoriais, binômio de Newton, combinações, arranjos e permutações, anti-fatoriais, stars and bars theorems, números de Catalan, sequências de Prüfer, fórmula de Cayley...)
- Aproximações numéricas (processos iterativos, método Newton-Raphson, busca binária, busca ternária, integração numérica, regra do trapézio, regra de Simpson...)
- Teoria da probabilidade (princípio da inclusão-exclusão, teorema da probabilidade condicional, teorema de Bayes, média/valor esperado/esperança matemática, variância e desvio padrão, processos estocásticos, cadeias de Markov...)
- Geometria computacional (primitivas geométricas e suas propriedades, princípio da inclusão-exclusão, convex hull, line/radial sweep, bin packing, k-d trees...)
- Grafos (tipos de grafos, busca em profundidade, busca em largura, componentes e conectividade, arestas de corte/pontes, vértices de corte/articulação, componentes bi-conectadas por vértices/arestas, diâmetro, dominator tree, árvores e florestas, LCA, HLD, small to large/DSU on tree, centroid decomposition, árvore de extensão mínima, algoritmo de Kruskal, MST dinâmico, caminho mínimo, algoritmo de Dijkstra, algoritmo Floyd-Warshall, problema do caixeiro viajante, DAGs, componentes fortemente conexas, algoritmo de Kosaraju, conectividade dinâmica, travessia paralela, caminho Euleriano, caminho Hamiltoniano, redes de fluxo, teorema do fluxo máximo e corte mínimo, método Ford-Fulkerson, algoritmo Edmonds-Karp, algoritmo de Dinic, algoritmo push-relabel/preflow-push, fluxo de custo mínimo, grafos bipartidos, casamento bipartido máximo, cobertura mínima de vértices, conjunto independente máximo, algoritmo dos caminhos de aumento, algoritmo Húngaro Kuhn-Munkres, problema do casamento estável, casamento em grafos quaisquer, Blossom algorithm, coloração de vértices e arestas, grafos planares, teorema de Kuratowski, teorema das quatro cores...)
- Teoria dos jogos (Nim game, Sprague-Grundy theorem, Grundy number...)
Para este estágio, utilize os OJs: codeforces, TopCoder e UVa OJ.
- Enquanto completa os estágios 6 e 7, participe dos rounds do codeforces. Estas competições duram duas horas, têm por volta de cinco problemas, são feitas de uma até quatro vezes por semana e são planejadas para serem feitas individualmente.
- Os estágios de 6 a 8 são para que você se acostume com os tipos de problemas e soluções que existem. Esta é a etapa em que você deve adquirir mais conhecimento e deve começar a se acostumar com competições.
- Observe que exercícios que envolvem somente um assunto ajudam a fixar este assunto, mas são exercícios fáceis! Exercícios médios/difíceis são aqueles que combinam diferentes assuntos/técnicas, ou aqueles que não deixam claro qual é o tipo de técnica que deve ser utilizada na solução, ou seja, é necessária uma observação não-trivial para resolver o problema. A melhor maneira de treinar para estes problemas é fazer um time de três pessoas e simular os contests de cinco horas do codeforces. Estas competições têm entre dez e doze problemas, são competições oficiais passadas e foram feitas para se fazer em time. De preferência, encontre pessoas empolgadas para estudar/treinar no mesmo ritmo que você. Assim, se algum integrante do time começar a perder o ritmo de treino, os outros dois vão puxá-lo de volta! Tentem fazer pelo menos uma simulação por semana!
- Não pare de resolver individualmente os rounds do codeforces, e também não deixe seus colegas de time pararem.
- Nesta etapa, o time deve treinar trabalho em equipe e aprender a resolver exercícios difíceis. Com pelo menos um ano nesta etapa, há grandes chances do time ficar pelo menos entre os 15 primeiros em uma final brasileira.
Conselhos gerais
- Certifique-se de nunca deixar um exercício lido por fazer. É justamente o exercício que você leu e não entendeu, ou o exercício que você leu e pensou “não faço ideia de como resolver” que vai te ensinar algo novo. É justamente este exercício que você deve sentir mais vontade de resolver!
- Todos os integrantes do time devem ter conhecimentos iguais. Todos devem resolver os mesmos problemas! Comente sobre soluções interessantes que você acabou de aprender com os seus colegas de time. Faça-os aprender tudo o que você aprendeu! Isto é de importância fundamental. Por exemplo: Bob está quase resolvendo um problema, mas o raciocínio dele está “viciado” e por isso ele não consegue ver um detalhe que está faltando. Se Bob mostrar o que ele já tem pronto para seus colegas de time, algum deles pode ver o detalhe que está faltando, pois, assim como Bob, eles possuem o conhecimento necessário, mas, diferentemente de Bob, eles não estão com o raciocínio viciado, ou seja, eles não estão concentrados no mesmo ponto de vista deste problema por muito tempo.
- É bom descansar de um problema que esteja tomando muito tempo para ser resolvido. Como dito no item anterior, raciocínio viciado pode ser o maior obstáculo para observar o detalhe crucial que falta para resolver um problema; e descansar elimina este raciocínio viciado. Descansar pode significar voltar ao exercício somente após uma semana, ou após um mês, ou após um ano! Eu já demorei 18 meses para voltar em um problema. Quando voltei, consegui entender a solução do autor e resolvi! No meio tempo em que você está “descansando” daquele problema, pode ser que você resolva um exercício mais simples, mas que seja parecido; e que te leve a observar o detalhe que faltava, ou a entender melhor a técnica utilizada no problema. Na maioria das vezes, uma simples boa noite de sono faz o milagre.
- Sempre que você encontrar um problema que não sabe resolver, não pesquise a solução imediatamente. Primeiro, tente pensar mais para resolver sozinho. Procure a solução apenas quando sentir que já apanhou do problema o suficiente. Isto é fundamental para o aprendizado ser sólido. O “choque” que levamos quando descobrimos a solução para um problema que estamos tentando resolver há muito tempo faz a gente gravar a solução profundamente!
- Tente reduzir o problema. Reduzir um problema A para um problema B significa encontrar uma maneira de mapear as respostas do problema B para as respostas do problema A que desejamos encontrar. Por exemplo: o problema de encontrar a altura máxima de um sólido de revolução de tal forma que seu volume não ultrapasse V unidades se reduz ao problema de encontrar o volume do sólido utilizando uma altura fixa de H unidades e comparar este valor com o valor de V. O mapeamento entre as respostas pode ser feito por meio de busca binária no valor da altura.
- Não basta saber implementar um algoritmo. É preciso entender como ele funciona. Precisamos aprender como um algoritmo funciona, para podermos adaptá-lo quando for necessário. Na maioria das vezes, é isso o que fazemos. Combinamos e adaptamos diferentes algoritmos para resolver um mesmo problema.
- Para muitos problemas, a solução se torna bem mais clara assim que desenhamos e fazemos representações visuais do problema. Isto também ocorre quando observamos a resposta do problema para alguns casos de teste específicos. Pode ser que os exemplos que estão no enunciado do problema não ajudem muito. Inclusive, muitas vezes, autores escolhem omitir certos exemplos que ajudam a solucionar o problema mais rapidamente! Desenhe e tente encontrar estes casos de teste chave!
- Aprenda a escrever códigos minimalistas. Em uma competição, não há tempo para escrever/depurar códigos muito grandes. Todo programador competitivo precisa ser adepto do princípio KISS.
- Programação competitiva se trata de encontrar soluções satisfatórias para problemas, antes de mais nada em um nível abstrato. Somente após encontrar uma solução adequada é que devemos implementá-la. Perder tempo implementando um algoritmo errado, ou que não seja rápido o suficiente, é um erro extremamente comum e pelo qual paga-se muito caro. No entanto, se houver tempo sobrando, é comum gerar casos de teste e implementar um algoritmo força bruta para tentar encontrar um padrão nas respostas do problema.
Links úteis