Arquivo mensais:abril 2006

Fase de Correção

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.

OBI2006 em fase de correção…

As tarefas da modalidade Programação estão sendo corrigidas. Os gabaritos das provas da modalidade iniciação estão disponíveis, por enquanto apenas para professores (algumas escolas atrasaram a realização da prova, por isso a demora na divulgação do gabarito). Solicitamos os professores que consultem a área de acesso restrito para informações de como proceder para enviar os resultados de sua escola. (retirado do site da OBI)

O pessoal da Iniciação já sabe como foram por aqui… Meu colégio até que teve um resultado legal: dois alunos da iniciação 1 (meu irmão é um deles) fizeram 12 de 16 e três alunos da iniciação 2 fizeram 19 de 22. Provavelmente esses vão pra segunda fase.

E por falar em ir pra segunda fase…

Pensando um pouco, cheguei a conclusão de que todo competidor que acertou mais de uma questão (ou talvez até menos que isso) já deve estar na segunda fase.

Uns 20 competidores devem ir para Campinas (medalha de ouro). Outros 20 devem conseguir medalhas de prata, mais 30 medalhas de bronze e 30 menções honrosas. Então, no mínimo 100 precisam fazer a segunda fase.

Neste ano, 520 pessoas participaram da modalidade Programação 2. Grande parte desses falta na prova ou zera (digamos que seja metade). Dessa forma, sobram 260.

Já que essa prova de primeira fase foi só para acabar com os casos de cola (tanto que a pontuação dela nem soma com a da segunda fase para dar a nota final e decidir se o competidor vai ao curso de programação em Campinas), acho bem razoável que esses 260 participem da segunda fase para no fim ficarem os 100 melhores.

Mas é só um palpite…

Meus códigos-fonte

Já que não é mais possível submeter resultados (as tarefas já estão sendo corrigidas), agora publiquei meus códigos-fonte na seção de scripts do meu site.

Colheita de Caju

Como vocês podem ver nos links aí em cima, a minha pior solução foi para o problema Colheita de Caju. A complexidade ficou um pouco (na verdade bastante) alta: O(L.C.(L-M).(C-N)). É a solução força bruta do negócio, bem simples de implementar e que com certeza funciona, mas para um caso com [L=1000, C=1000, M=1, N=1], ela demora um tempo no mínimo razoável… Mas tudo bem, os outros acho que passam talvez até com a pontuação máxima.

A solução ótima seria usando programação dinâmica; um algoritmo que depois eu comento melhor.

Nota esperada

Quase duas semanas depois da prova, meu chute para a nota da primeira fase é 420/500. Mas nunca se sabe… :)

Primeiras Impressões

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.

Ontem, no período da tarde, foi aplicada a prova da primeira fase da OBI2006, modalidade Programação Nível 2. Já que nem todos os colégios submeteram as soluções de seus alunos, ainda não vou publicar os meus códigos nem o enunciado dos problemas, mas apenas escrever sobre o que achei da prova (assuntos separados em tópicos).

Tempo de Prova

O caderno foi composto por cinco questões, para serem resolvidas em cinco horas. Na minha opinião, foi tempo até demais para o nível dos problemas. Acabei a prova em pouco mais de três horas (depois de criar outros casos de teste, ver a complexidade dos algoritmos e tudo…).

Dificuldade da Prova

Embora no começo eu sempre leve um susto, no fim achei a prova fácil. Fiz as cinco questões, acho que acertei todas e a complexidade de nenhum dos meus algoritmos ficou muito pesada (mas também nunca se sabe…). Espero tirar uma nota superior a 400 (de 500) e acho que é possível até eu ter gabaritado.

Complexidade

Neste ano, o pessoal deixou a parte de tempo bem fácil. Ao invés de ser um conjunto de teste em cada entrada, foi apenas um teste por entrada. A conseqüência é que, além da questão de tempo ficar mais fácil, também não precisamos nos preocupar em zerar as variáveis a cada loop.

Problema mais difícil

O melhor problema da prova foi, na minha opinião, o Escada Perfeita. Infelizmente, não posso comentar muito a respeito dele até todos submeterem suas soluções, mas esse problema foi muito bom.

No meio de um problema de grafos (Museu), dois de coisas básicas tipo entrada/saída (Truco e Jogo de Cartas) e um problema para mostrar que sabemos mexer com matrizes (Colheita de Caju); o sistema de equações que dava pra montar neste problema (Escada Perfeita) baseado na fórmula de soma de PAs (aquela lenda do Gauss quando tinha cinco anos…) e depois um algoritmo guloso, fizeram com que eu ficasse mais de uma hora tentando encontrar a solução (que ficou com complexidade O(n)). Depois crio um post para comentar mais a respeito!


Enfim… Não posso entrar em muitos detalhes por enquanto e nem tenho certeza de como fui. A fase pós-prova/pré-nota é sempre complicada… Mas, se não cometi erros que [se existirem] devo perceber e comentar nos próximos artigos, rumo a segunda fase!

Pessoal que participou também, comentem aí dizendo como foram!