Eu até tentei escrever um artigo por dia na semana passada, durante o curso da seletiva brasileira para a Olimpíada Internacional de Informática, mas não deu tempo… Então aqui vai um resumo feito uma semana depois do final do curso, separado em tópicos, com o título pouco criativo “There and back again…”
Nível mais alto
Comparando a prova da segunda fase da OBI2006 com a prova da OBI do ano passado, já era possível perceber que o nível esse ano subiu. E, como já esperado, o nível do curso e das pessoas também subiu, o que é excelente para o Brasil.
Mais prática, menos teoria
Neste ano não aconteceu a programação “normal” que tivemos nos últimos dois anos: aula teórica (só um professor apresentando slides e nós anotando, sem computadores) durante a manhã e aula prática durante a tarde.
Nos dois períodos nossas aulas foram no laboratório, com computadores, onde resolvemos uma porção de problemas do treinamento para a ACM da Universidade de Valladollid.
Criei uma pasta no meu servidor com todos os problemas que eu consegui resolver (alguns deles ficaram pela metade): tiagomadeira.net/pub/uva/ (essa pasta infelizmente foi perdida com o tempo).
Problemas sobre mais de um conteúdo
Uma característica interessante dos problemas desse ano (do treinamento e da prova) foi o uso de mais de um tipo de algoritmo para fazer a solução. A combinação mais comum foi geometria + grafos, que caiu inclusive na prova da Seletiva, no problema Labirinto.
A Prova
Primeiro Dia – Quadrado Romano
[Enunciado] 30 minutos tentando pensar em algum tipo de recorrência, 1h implementando uma solução força bruta! No final, pensei que faria uns 50 pontos (perderia um pouco por causa do tempo), mas perdi alguns pontos por resposta errada, ainda não sei por quê!
Solução: romano.c (infelizmente foi perdido com o tempo)
Pontos: 10/100
Segundo Dia – Euros
[Enunciado] Durante as duas horas da prova fiquei procurando uma recorrência. Descobri que estou muito newbie em programação dinâmica. Não programei uma linha de código…
Pontos: 0/100
Terceiro Dia – Labirinto
[Enunciado] Olhei o enunciado e já saquei o que o problema queria. Eu tenho uma boa noção de grafos (embora precise estudar fluxos) e o curso trabalhou bastante algoritmos geométricos, então sem maiores problemas fiz o algoritmo, testei várias vezes, achei que ia tirar 100. No fim, não sei o que houve, se foi falta de tempo ou resposta errada. Só vi que fiz 40 pontos…
Solução: labirinto.c (infelizmente foi perdido com o tempo)
Pontos: 40/100
Quarto Dia – Prova Final
[Caderno de Tarefas] Li todos os problemas e achei que poderia ir bem na prova (o primeiro problema eu tinha certeza que não conseguiria, mas o segundo e o terceiro dava pra fazer). Então, fui direto para o segundo problema, acreditando que era o mais fácil. Mas depois de bolar vários algoritmos, ter respostas erradas e tempos muito altos, tive que ficar com uma solução precária, um Floyd Warshall para cada troca de vértices (resultado: [tex]O(n^{5})[/tex]!) Aí depois não deu tempo de fazer o terceiro problema, mesmo eu tendo esboçado sua solução.
Solução do Teletransporte: tele.c (infelizmente foi perdido com o tempo)
Pontos: 40/300
Conclusão
O legal é que esse curso sempre dá vontade de estudar, além de ensinar bastante… Aqui ficam registrados meus objetivos e metas pro segundo semestre de 2006 e primeiro semestre de 2007.
Objetivos
Metas
- Comprar e ler Programming Challenges.
- Estudar programação dinâmica. Conhecer os algoritmos mais comuns.
- Estudar fluxos em rede e ordenação topológica.
- Estudar matemática, inclusive recorrências e geometria (que não ajudam só para olimpíada de matemática, mas pras olimpíadas de informática também)