Informações sobre desafios e competições de programação

E aí pessoal!

Seguindo um dos posts da Loiane sobre problemas de computação e matemática, deixo aqui o link para o repositório no Github com alguns algoritmos que usei para resolver uns problemas no SPOJ. Gostaria contribuir mais com o projeto, mas infelizmente estou com o tempo encurtado e essa parte exige um esforço maior (principalmente porque estou 'enferrujado').

Acho bastante interessante o estudo de algoritmos e matemática, não somente para o profissional de computação. Na minha opinião, é o fundamento de toda a computação: algoritmos e matemática sendo usados juntos para a resolução de problemas (muitas vezes complexos). Acho interessante o estudo de novas linguagens, paradigmas e modelos de arquitetura, mas, acima de tudo, algoritmos e matemática ainda deveriam vir em primeiro lugar na lista de prioridades de estudo de qualquer pessoa que tenha como objetivo o desenvolvimento de sistemas.

Abaixo deixo uma lista de competições de programação que conheço (a Loiane colocou mais alguns no blog dela. Estou colocando somente os que conheço e já participei):

• TopCoder: mensalmente acontecem competições online (as chamadas SRMs - Single Round Matches), com um certo limite de tempo. Além disso, os competidores podem olhar o algoritmo dos outros competidores e desafiar com entradas diferentes. Os problemas são, em sua maioria, submetidos por competidores. Existem também outras modalidades, como as Marathon Matches (com problemas mais complexos e tempo mais longo para resolver) e as High School Matches (que são as SRMs com problemas um pouco mais fáceis). Esse site também contém um material (escrito por competidores) sobre como resolver os problemas;
• SPOJ Brasil e SPOJ Internacional: problemas das maratonas de computação nacionais (as qualificativas para o ACM ICPC) e internacionais (geralmente warm-ups que acontecem antes do mundial) e alguns problemas da OBI (Olimpíada Brasileira de Informática);
• Google Code Jam.

Vale ressaltar que a maioria desses sites (sei que o TopCoder e os SPOJs) tem foruns sobre dicas de como resolver os problemas.

Livros

• Introduction to Algorithms, Cormen et. al.: acredito ser o principal livro de algoritmos;
• Concrete Mathematics, Knuth et. al.: um livro bastante 'pesado', mais voltado para a matemática (teoria dos números, probabilidade, otimização combinatório, geometria e afins);
• Programming Challenges, Skienta et. al.: livro voltado para as competições, comentando os algoritmos utilizados, as limitações e como abordar os problemas de computação.

Outros links interessantes

• Algorithmist: site contendo explicações sobre algoritmos e alguns problemas resolvidos;
• 'Notebooks' criados por brasileiros: site com 'notebooks' (pdf com algoritmos implementados) e mais dicas sobre os tipos de problemas que encontramos nas competições.

Se você quer entrar nessa área logo de cara mas tem certo receio de não saber muito bem a parte matemática, indico bastante o estudo de Matemática Discreta. Provavelmente é a parte matemática que mais se aplica à computação, apesar de ser muito fácil encontrar problemas que envolvem Geometria.

Mais algumas dicas

• Não desista se a sua primeira submissão deu errado, principalmente se você está começando. Existem diversas categorias de problemas, desde erros ao formatar a entrada ou saída a tempo de limite excedido (TLE);
• Pra quem tem muito erro de TLE, a resposta é bem simples (se você não está tanto problemas pra ler a entrada de dados): você provavelmente está resolvendo da forma errada. Algumas vezes técnicas como memoization ajudam a diminuir o tamanho da memória utilizada e a velocidade de re-computações (como é o caso do fatorial e dos números primos);
• Algumas competições (como o SPOJ e o UVa) tem problemas que são facilmente quebrados pelo fato da entrada ser muito grande. Linguagens como Java e Python infelizmente sofrem um tanto com isso (em 2011 acredito que Java não sofra tanto, mas Python ainda tem alguns problemas). Na maratona de programação da ACM, a ICPC, é muito fácil ver quem fez código em Java ter problemas com as entradas. Uma das razões pelas quais comecei a usar C++ (ou melhor, C com a stdlib) foi justamente o problema das entradas. O TopCoder tem uma vantagem: você não usa a função main; você cria um método (exatamente como descrito na descrição do problema) e trabalha com os parâmetros dentro do método.

Volto a dizer: acredito fielmente que o estudo de paradigmas, linguagens e modelos de arquitetura são importantíssimos, assim como o estudo de matemática e computação para resolução de problemas.

Qualquer dúvida, postem! Vou enriquecendo o conteúdo do texto conforme for encontrando links interessantes.

Até a próxima!