Saiu ontem o resultado do Desafio Nacional Acadêmico. Minha equipe, 2 Pi ficou em 24º lugar no Brasil e em 2º lugar em Santa Catarina depois de acabarmos o desafio no dia 15 às 20h00.
Poderíamos ter ido melhor se a organização não tivesse mudado a data do desafio final (eu estava em Campinas, fazendo a seletiva para IOI e não pude participar do jeito que deveria) e um participante da nossa equipe priorizasse o desafio ao invés do download do Missão Impossível III. De qualquer maneira, valeu!
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…”
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.
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).
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.
[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
[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
[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
[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
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.
Estou hospedado na casa do meu irmão, em Campinas, desde ontem de manhã (viajei domingo a noite de ônibus). Hoje foi o primeiro dia do curso preparatório para a seletiva da IOI2006, que começou às 9h00 devagarinho.
O dia hoje serviu para “nivelar” os participantes e treinar um pouquinho a resolução de problemas. De manhã, algumas pessoas tiveram uma aula sobre estruturas de dados, grafos e o básico de programação dinâmica e outras (a maioria) resolveram três problemas da Universidade de Valladollid:
Enunciado – Minha Solução
Não é um problema muito complexo, mas eu usava um algoritmo muito demorado para determinar se dois números tinham ou não um fator comum, que não passava por tempo limite excedido. Então, o Fábio Dias Moreira nos passou uma propriedade bem interessante de MDC (Máximo Divisor Comum):
mdc(x, y) = mdc(x%y, y)(onde o % é o resto da divisão, no C)
Aí dá pra fazer uma função recursiva mdc bem rápida, que eu apliquei na [minha solução][3].
Enunciado – Minha Solução
Esse problema nem tem muito o que comentar. Implementação de dois minutos… hehehe… Eu podia ter feito uma função recursiva pra ficar um pouco mais “decente” (e poder mudar de 6 para outro número no futuro), mas não tinha necessidade, então ficou assim mesmo (e passou de primeira no site).
Enunciado – Minha Solução
O objetivo é provar a Conjectura de Goldbach para todos os pares menores que 1000000. Meu programa ainda não roda dentro do tempo, mas depois vou continuar a adapta-lo. Eu posso, por exemplo, ir fazendo a média entre o maior possível e o menor possível (aquele “algoritmo” que usamos quando alguém fala: “Pensei num número de 1 a 100. Tente advinhar…”) ao invés desses loops, o que já vai tornar o programa mais rápido (não sei se o suficiente).
Nesse problema, o Fábio me lembrou do Crivo de Eratóstenes. Bem interessante, nunca tinha implementado. :)
Provavelmente pela primeira vez, o almoço dos participantes do curso não foi no “bandeijão”, mas sim num restaurante chique perto do IC. Achei bem legal… Além de andar menos, o ambiente é melhor e a comida também.
Durante a tarde, o Fábio nos passou o algoritmo de Longest Common Subsequence (esse eu já sabia… hehehe) e depois o algoritmo que resolve o problema Subseqüências que caiu na prova da segunda fase (esse um pouquinho mais complicado!). Esse segundo eu pretendo implementar e depois até fazer um artigo sobre…
Depois, o Fábio nos deu algumas dicas, principalmente sobre os cálculos problemáticos que o computador faz com pontos flutuantes (algo bem interessante, que eu não entendia porque acontecia). Por exemplo, quando criamos um double x=0.1 o seu valor não é 0.1, mas sim o 1/1010 (em binário) que dá uma dízima periódica! E isso não é muito agradável, pode gerar até loops infinitos… Então, ele sugeriu que criássemos uma função para comparar dois números reais, com um código como esse:
/*
USO: Substituir...
x == y <==> cmp(x, y) == 0
x != y <==> cmp(x, y) != 0
x < y <==> cmp(x, y) < 0
x ### y <==> cmp(x, y) ### y
O "###" é "qualquer-coisa". Hehehe...
*/
#include <math.h>
const double EPS = 1.0e-10
int cmp(double x, double y) {
if (fabs(x-y)<EPS) {
return 0;
} else if (x>y) {
return 1;
} else {
return -1;
}
}Foi um bom ponto de partida legal, começamos de leve. Ainda não sei sobre o quê será a aula de amanhã…
Neste ano vão haver quatro provas para selecionar os quatro participantes que irão representar o Brasil na Olimpíada Internacional de Informática em agosto, no México. As três primeiras, identificadas como “testes” no calendário da seletiva, terão apenas um problema e durarão duas horas cada uma. A última será no domingo, às 7h45min, terá três questões e durará cinco horas (pô, vou perder o comecinho do jogo de Brasil contra Austrália!). Achei legal esse método, mas como o César Kawakami disse: dessa maneira, não treinamos a estratégia, que é algo importante para a prova da IOI.
Por enquanto é só. Se der tempo, pretendo colocar um post por dia sobre o curso até o final dessa semana. :)
Você, que é aluno do ensino médio, não pode ficar de fora do maior evento virtual já organizado no Brasil.
Serão milhares de escolas inscrevendo seus representantes para participar do Desafio Nacional Acadêmico – DNA 2006.
O DNA 2006 será a maior Gincana de Conhecimento já realizada pela internet. Fundamentado na filosofia pedagógica WebQuest, o DNA é uma fantástica oportunidade para os participantes ampliarem seus conhecimentos, ao mesmo tempo em que desenvolvem a criatividade, a noção de liderança, o trabalho em equipe e a tomada de decisão. Para mais informações leia o Manual do Participante.
Somado a isso, os participantes poderão fazer novas amizades e conhecer alunos do Brasil inteiro. O DNA será um encontro marcado para um público estimado em milhares de jovens.
Pô… A idéia dos caras foi ótima. As perguntas foram super criativas e as equipes pesquisaram um monte, trocaram um monte de informações… O DNA apareceu em vários fóruns de discussão, comunidades do Orkut; nos mais diversos meios de comunicação na internet. Minha equipe se divertiu bastante, pesquisando exaustivamente durante cinco dias e duas noites viradas.
Entre vários desafios difíceis (de coisas que não se achava na internet ou que eram muito difíceis de serem encontradas – como por exemplo o nome da mãe de um marinheiro brasileiro pouco conhecido, que só aparece num PDF em francês pesquisando no Google), uns foram mais divertidos por causa do que tivemos que fazer para conseguir a resposta.
Como exemplo, vou citar um desafio que era traduzir um arquivo de áudio (MP3) com quatro palavras em russo. Primeiro tinha o trabalho de identificar a linguagem… Mas vinha uma imagem junto que era de um astronauta russo, então fomos direto pro caminho certo. Aí depois de ligar para a embaixada russa (e descobrir que ninguém lá fala português) e pra mais um monte de gente, adicionar 40 contatos russos no ICQ (usando as White Pages) e perguntar para vários russos que estavam ausentes ou não queriam ajudar (teve um que ficou me criticando porque eu estava falando inglês ao invés da minha língua materna – reflexos da Guerra Fria?), encontramos UM que falava inglês (bem mal, mas pelo menos falava). Aí depois de eu explicar 100 vezes pra ele o que tinha que fazer e ele me xingar de beach (dá pra ver que o cara não fala inglês, né?) e eu quase desistir dele, vieram as quatro palavras desse MP3 (infelizmente, esse áudio foi perdido com o tempo): peixe água açúcar cozinha. Aleluia!
Trecho da conversa cômica com o russo que nos ajudou no DNA
[…]
Russo: i fuck your Grandpa and she Scream ” YES !!! BABY !
Eu: cool… now, listen to the mp3 file…
Russo: i am Terminator
Eu: ok, me too
Russo: COOL
Eu: ok. now, please listen to the file.
Russo: i am Usama BenLaden
Eu: ok, cool. you can explode my house after you say me what the words mean
Russo: i sit not on the full internet (não entendi o que isso significa, mas acho que ele não conseguia baixar)
Eu: how can i send you? can you receive it by e-mail?
Russo: BEACH
Eu: are you in a beach? nice… what’s your e-mail address?
Já começava a desconfiar do evento quando percebi que o site deles era hospedado num servidor Microsoft/IIS, programado em ASP e só funcionava no Internet Explorer (hehehe, nenhum defensor dessa combinação mortífera precisa se sentir ofendido)… Pior ainda foi quando minha equipe começou o desafio e, além do congestionamento, nos deparamos com vários erros de programação, server e client-side.
A decepção final foi hoje, quando foi divulgado no site oficial que o final do evento será prorrogado. Pô, minha equipe pulou três questões por causa do tempo! Além disso, o “desafio final” (o último desafio, que promete ser muito difícil e vale mais pontos) vai ser nessa quinta-feira e eu vou estar viajando. Infelizmente, tornou-se impossível vencer.
O desafio foi muito legal e ano que vem sem dúvidas participarei de novo, mas a organização e o planejamento do evento foram péssimas; houve incompetência principalmente por parte dos programadores. Bom… Espero que ano que vem seja melhor… Aproveito pra agradecer para os amigos (em especial pro Reinaldo, que conseguiu a resposta de uma questão de biologia, na etapa surpresa, que iríamos demorar muito pra conseguir – se conseguíssemos…) e professores que nos ajudaram. E também um agradecimento especial para o nosso amigo russo. :)
Ah, no fim o russo perguntou pra quê queríamos saber o que as palavras significavam (eu já tinha falado umas três vezes que era um “virtual challenge”), então resolvi inventar um motivo fictício que ele pudesse entender: “O prêmio é uma viagem à Rússia.” Ele disse que vai nos mostrar a sua cidade quando formos lá e que vamos jogar Counter-strike! :D
[editado] Parece que consideraram nosso recurso, estamos com a pontuação máxima. Agora é só pesquisar pro desafio final! [/editado]
[editado de novo] Se for fácil como parece, acho que descobrimos a resposta do desafio final (sem nem ter a pergunta)! Agora é só digitar rápido na quinta-feira… :) [/editado de novo]
Ocorreu hoje a tarde a prova da primeira fase da Olimpíada Brasileira de Matemática (e da Regional/catarinense também, a primeira fase é igual). A prova tava difícil, ao menos pros padrões daqui… :) Acertei 16 de 25 questões, segundo gabarito extra-oficial, três delas foram chutes! Mas tá bom, creio que isso classifique pra segunda fase sem problemas.