There and back again…

ATENÇÃO: Este conteúdo foi publicado há 11 anos. Eu talvez nem concorde mais com ele. Se é um post sobre tecnologia, talvez não faça mais sentido. Mantenho neste blog o que escrevo desde os 14 anos por motivos históricos. Leia levando isso em conta.

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): http://tiagomadeira.net/pub/uva/.

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

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

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

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)

4 comentários sobre “There and back again…

  1. Oi, Tiago. No site da olimpíada (http://olimpiada.ic.unicamp.br/seletivaIOI/tarefas_solucoes) publicaram os arquivos de teste e as nossas soluções “canônicas” para os problemas. Dê uma olhada lá e teste suas soluções, procure seus erros etc. Se não entender alguma coisa, pode entrar em contato. :) Ah, e divulgue isso tb para o pessoal que vc conhecer, é difícil ter algum retorno (comentários, dúvidas, sugestões etc) de vcs, já que vcs são muito tímidos e não falam muito conosco! hahahaha :P

  2. Pois é…

    Ano passado aconteceu algo bem parecido comigo: Eu saí da prova sabendo resolver todos os problemas, mas não ganhei quase nada nas questões… Ainda bem que esse ano isso não ocorreu. hehe… =)

    Mó raiva quando isso acontece…

    Ah, e você poderia mandar o email do demasi, aí em cima, pra mim? LOL. Eu esqueci de anotar o email dele, e queria perguntar uns troços… hehe

  3. Além de comprar o Programming Challenges (é verdade, eu tb precisava comprar ^^;;;) , recomendo ir ao site do mesmo (google google google – achei, é http://www.programming-challenges.com/). Lá há um monte de problemas para resolver (assim como no UVA, mas mais user-friendly)

    Aliás, foi esse site que usamos no IME-USP, quando eu fiz uma matéria optativa chamada “Desafios de Programação” – aka “Estamos tentando formar novos talentos para Maratonas de Programação”, rs….

Deixe uma resposta