Arquivo da tag: obi 2006

Escada perfeita (OBI2006)

ATENÇÃO: Este conteúdo foi publicado há 10 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.

Depois de meses sem postar, resolvi que a partir de agora darei mais atenção pra este blog. Muita gente me manda e-mail e comentários com dúvidas e gostaria de deixar bem claro que eu não faço trabalhos de faculdade pra ninguém, mas que se você tiver uma dúvida real onde eu possa ajudar eu ajudarei de bom grado.

Pensei muito sobre o que postar aqui, tenho rascunhos sobre buscas em grafos e sobre resoluções de problemas de grafos, mas resolvi quebrar toda a ordem e, a partir de um scrap de orkut, acabei me lembrando do problema Escada perfeita, da OBI 2006, e me deu vontade de resolvê-lo aqui.

Por que o problema Escada Perfeita?

A programação deste problema é extremamente simples, mas a sua lógica (matemática pura) é muito inteligente. Tente resolver o problema antes de ver minha solução e, caso não consiga, depois veja como a solução é bonita.

Vamos ao enunciado…

Uma construtora, durante a criação de um parque temático, encontrou no terreno um conjunto de várias pilhas de cubos de pedra. Ao invés de pagar pela remoção dos cubos de pedras, um dos arquitetos da empresa achou interessante utilizar as pedras para decoração do parque, determinando que as pedras fossem rearranjadas no formato de “escada”. para isso, os funcionários deveriam mover alguns cubos para formar os degraus das escadas. Só que o arquiteto decidiu que, entre uma pilha e outra de pedras deveria haver exatamente uma pedra de diferença, formando o que ele chamou de escada perfeita. O exemplo abaixo mostra um conjunto de cinco pilhas de pedras encontradas e as cinco pilhas como ficaram após a arrumação em escada perfeita.

Tarefa

Dada uma seqüência de pilhas de cubos de pedras com suas respectivas alturas, você deve determinar o número mínimo de pedras que precisam ser movidas para formar uma escada perfeita com exatamente o mesmo número de pilhas de pedras encontrado inicialmente (ou seja, não devem ser criadas ou eliminadas pilhas de pedras). O degrau mais baixo da escada deve sempre estar do lado esquerdo.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha contém um inteiro n que indica o número de pilhas de pedras. A segunda linha contém N números inteiros que indicam a quantidade de cubos de pedras em cada uma das pilhas, da esquerda para a direita.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro: o número mínimo de cubos de pedras que devem ser movidos para transformar o conjunto de pilhas em uma escada perfeita, conforme calculado pelo seu programa. Caso não seja possível efetuar a transformação em escada perfeita, imprima como resultado o valor -1.

Exemplos

Exemplo 1

Entrada
5
5 4 5 4 2

Saída
5

Exemplo 2

Entrada
6
9 8 7 6 5 4

Saída
9

Exemplo 3

Entrada
2
1 5

Saída
-1

OK. Estão prontos?

Depois de pensar um pouco, conclui-se que:

  1. A escada perfeita é uma PA de razão 1 (aumenta de um em um). Você lembra disso do seu primeiro ano do Ensino Médio? Senão, é bom dar uma relembrada. As fórmulas (simples e facilmente deduzíveis) da PA são:

    Termo geral da PA

    a_{n} = a_{1} + (n-1).r

    Soma de PA

    \displaystyle S_{n} = (a_{1}+a_{n}).\frac{n}{2}

  2. Sabemos quanto vale n (o número de pilhas, número de elementos da PA) e conseguimos calcular a soma de todos os elementos (podemos fazer isso até durante o loop da entrada, certo?)
  3. Sabemos quanto vale a razão (r=1).
  4. Substituindo o que sabemos nas fórmulas conseguimos formar um sistema de equações básico e desta forma torna-se fácil descobrir o valor do primeiro e do último termo da PA (a_{1} e a_{n}). Resumindo um pouco os cálculos, depois de alguma manipulação algébrica você chega a: \displaystyle a_{n} = \frac{\frac{2.S_{n}}{n}+n-1}{2}

    \displaystyle a_{1} = 1 + a_{n} - n

  5. Agora que já sabemos onde começa e onde termina a escada basta fazer um loop em cada fila de blocos e adicionar à uma variável movimentos a quantidade de quadradinhos que estão sobrando nesta fileira (por exemplo, na primeira fileira da figura do enunciado está sobrando três quadradinhos para chegar ao a_{1}=2). Ao mesmo tempo, adicionamos à outra variável (moves) a quantidade de quadradinhos que devem ser retirados ou colocados na fileira (porque depois se esta variável não for igual a 0 imprimimos -1). Ficou claro?

Implementação

Variáveis

  • n: número de degraus (fileiras de blocos)
  • a: a_{1}, número de blocos do primeiro degrau.
  • b: a_{n}, número de blocos do último degrau.
  • soma: S_{n}, soma da PA.
  • pilha[]: vetor de degraus.
  • movimentos e moves: explicados no quinto passo da solução.
  • i e j: variáveis auxiliares para fazer os loops.

Codeado em C

#include <stdio.h>
#define PMAX 10001
 
int main() {
    int i, j;
    int n;
    int soma=0;
    int a, b;
    int pilha[PMAX];
    int moves=0;
    int movimentos=0;
 
    scanf("%d", &n);
    for (i=0; i<n; i++) {
        scanf("%d", &pilha[i]);
        soma+=pilha[i];
    }
 
    b=(((2*soma)/n)+(n-1))/2;
    a=1+b-n;
 
    for (i=0; i<n; i++) {
        moves+=(pilha[i]-(i+a));
        if (pilha[i]>i+a) {
            movimentos+=(pilha[i]-(i+a));
        }
    }
 
    if (moves!=0) {
        printf("-1n");
    } else {
        printf("%dn", movimentos);
    }
 
    return 0;
}

Prontinho! Qualquer dúvida escrevam seus comentários.

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)

Curso da Seletiva IOI 2006: Primeiro Dia

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.

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:

412 – Pi

EnunciadoMinha 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.

441 – Lotto

EnunciadoMinha 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).

543 – Goldbach’s Conjecture

EnunciadoMinha 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ã…

Seletiva IOI

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. :)

Resultado da OBI2006

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.

Em breve, estarei divulgando o how-to: Como perder uma viagem, um curso e uma oportunidade de representar o Brasil numa olimpíada internacional por um erro de digitação… :(

Um dia depois do prazo que consta no regulamento, a Comissão Organizadora da OBI2006 divulgou o resultado da modalidade programação. Para minha surpresa, fiz 20 pontos: 10 no Lobo Mau e 10 no Penalidade Mínima.

No último post eu mencionei que estava mal no dia da prova e nem fiz o último problema, mas não esperava tão poucos pontos. Aí baixei os testes do problema Lobo Mau e, com poucos testes, percebi que o erro do meu programa estava na entrada. Os arquivos que a OBI está usando estão no formato DOS (tem um caracter estranho além do n a cada quebra de linha) e por isso o meu programa não pegava corretamente os dados (ele pega todos os caracteres da matriz com scanf(“%c”); e o caracter de quebra de linha da mesma maneira). Já mandei o pedido de correção ontem a noite mesmo e eles já disseram que vão recorrigir.

Maldito erro de digitação!

Agoca… O pcoblema sécio veio depois. Ao lec o ródigo da minha solução*, pecrebi que eccei um racartec no acgumento rondirional de um loop! Tcoquei um “r” (rê) poc um “c” (ecce) (veja a linha 63 do ródigo que está linkado no astecisro), racarteces que signifiravam as linhas e rolunas da matciz, cespertivamente. Maldito ecco de digitação!

Corrija a frase acima, JavaScript! (são as inutilidades que o vício em linguagens client-side pode fazer…)

Se eu não tivesse trocado esses caracteres, tiraria 30 pontos a mais do que eu já devo tirar com a solicitação das quebras de linha: 110 pontos, o suficiente para participar do curso e da prova Seletiva para IOI.

* Minha solução para o problema Lobo Mau: lobo.c

Bom… Já que é a lógica do problema que é o desafio na OBI, vocês não acham que erros de digitação deveriam poder ser corrigidos? Além disso, acho que eles podiam somar essa nota com a nota da primeira fase (mesmo que ela tivesse um peso bem menor).

Eu já esperava ir mal, mas pensei que os 100 pontos do Lobo Mau estavam garantidos, pelo menos. :(

Por enquanto é isso aí… Me ferrei, mas agora pelo menos nunca mais vou errar uma coisa dessas numa prova de programação e nunca mais vou comer no Mc Donalds antes de uma prova… (tô tentando ser otimista, mas tá difícil… hehehe) Parabéns pra quem passou e boa sorte! Embora eu não tenha gostado do resultado, na verdade não tenho motivos lógicos para reclamar. Vacilei na segunda fase mesmo e provas são sempre traiçoeiras (com certeza elas não são a melhor maneira de avaliação).

Resumã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.

Segunda Fase da OBI2006

Sábado foi a OBI em Blumenau. A prova estava cansativa e difícil pra caramba… Na minha opinião, o nível de dificuldade foi semelhante a da Seletiva para IOI do ano passado.

Fui muito mal, mas pelos comentários parece que ninguém foi muito bem. Essa espera pelo resultado vai ser longa… Hehehe… Teve gente que não me interpretou direito, então vou falar de outra maneira: Estou ansioso pelo resultado, por isso as duas semanas vão demorar pra passar.

Resposta à Veja

Não posso deixar de linkar esse ótimo artigo do Falcon Dark (assinem o feed desse cara… tudo que ele escreve é excelente!): Para o público e o privado sem ideologismo. Ele comenta sobre a reportagem da Revista Veja de 17 de maio de 2006, página 68, O grátis saiu mais caro.

O Laptop do Reinaldo

Instalei GNU/Linux (Slackware) no laptop do Reinaldo. Um Pentium 3 900mhz, 128 mb ram, 6 gb de HD; que tá com uma performance legal agora, sem o Windows XP que possuía (ou melhor, que o possuía).

O legal é que a placa de rede do laptop era PCMCIA e o CD e o disquete não funcionavam direito! Foi uma experiência única e desesperadora… :) Hehehe…

Consegui bootar por um CD velho do Slackware 10.0 (o drive de CD só conseguiu ler esse CD de todos que eu tinha aqui) e só deu pra instalar a série A (os pacotes mais básicos). O resultado foi um sistema sem absolutamente nada (andei até perguntando pro Lorn se tinha como configurar rede sem ifconfig… hehehe). Depois de dois dias, quando quase estava indo entregar para o Reinaldo o laptop destruído (sem sistema operacional), lembrei que tinha um velho zip-drive externo USB aqui em casa. Pluguei, montei e funcionou! Aí consegui instalar a série N (Network) e a AP (aplicações básicas) para conseguir ver o meu computador na rede e copiar o Slackware 10.2 inteiro.

Finalizado esse passo, reiniciei o computador bootando pelo CD do Slackware 10.0, deletei tudo do HD (com excessão exceção do CD do Slackware 10.2 que eu tinha copiado) e consegui fazer a instalação. O computador tá excelente agora, com uma performance impecável! :D (usando XFCE como gerenciador de janelas)

Desafio Nacional Acadêmico

Esse ano vai acontecer pela primeira vez o DNA. É um dia com várias provas (segundo eles, quase impossíveis) solucionadas pela internet por equipes de cinco componentes. Tem prêmios para os três melhores colocados e já inscrevi minha equipe. A inscrição custa R$ 50,00. Quem puder, participe! É uma oportunidade legal…

Mais uma vez, novo design!

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 tenho alterado o design do meu site a cada seis meses, mas dessa vez me cansei do design anterior um pouco mais cedo e reorganizei o site agora em maio mesmo… :)

Estou usando WordPress 2.0 agora e aproveitei a mudança de design pra mudar um pouco a organização do site. Resolvi separar o blog dos artigos (clique no link aí em cima que você vai ler que tipo de coisa eu publicarei em cada seção).

O design ficou bem claro, porque não consegui juntar nenhuma outra cor com esse amarelo estranho que “roubei” do A List Apart. Sugestões para melhora são bem-vindos.

O logo ainda é o que o Cosme fez pra mim… Só modifiquei as cores.

O site agora fica ocupando toda a largura em qualquer resolução…

Espero que gostem… Por ter publicado o site meio rápido, é capaz de vocês encontrarem algum erro aqui dentro. Caso isso aconteça, me avisem!


A comissão organizadora da OBI2006 ainda não divulgou o resultado da primeira fase… Falta menos de uma semana pra segunda fase e eu ainda nem sei se vou ter que viajar para fazê-la!


[editado] Oops, me esqueci de fazer o código de publicação de comentários… Peraí, já vai! Tá OK agora…

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!

Anunciada a OBI2006

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.

Anunciada a OBI2006! E temos novidades…

A partir desse ano a OBI será realizada em duas fases: a primeira fase nas escolas cadastradas e a segunda, com os melhores classificados da primeira fase, em universidades localizadas nas capitais dos estados e em cidades com grande concentração de competidores.

As provas da primeira fase da OBI2006 serão realizadas no dia 08 de abril (sábado) para a modalidade Programação: a prova do nível 1 ocorrerá no período da manhã, e a prova do nível 2 ocorrerá no período da tarde. Na modalidade Iniciação a prova será aplicada em dia a ser definido pela escola, entre 06 e 13 de abril.

As provas da segunda fase serão realizadas no dia 13 de maio (sábado), tanto para a modalidade Iniciação quanto para a modalidade Programação. Todas as provas seão aplicadas no período da tarde.

Copiado de: Site da OBI

Vamos participar, né? Estou ensinando meu amigo Ivo a programar e estou disposto a ajudar a quem quiser; para mim é um prazer ensinar coisas que eu gosto a quem está disposto a aprender.

E sobre a IOI…

Em 2006 a IOI será realizada no México, de 13 a 20 de agosto. Quatro competidores da Modalidade Programação, Nível 2, representarão o Brasil. Você pode ser um deles! [é a minha meta pro ano!]


Fiquei mais de um mês sem postar (ando sem inspiração). Desculpem-me por deixar a Série Algoritmos parada e não noticiar alguns fatos legais que aconteceram enquanto eu não postei (eu parei de escrever, mas comecei a ler mais). Vou voltar de leve agora…

Tenho estudado bastante matemática e física… pras olimpíadas, pro vestibular do ITA, pra desenvolver minha mente, etc. No fundo, é só porque eu gosto mesmo! :) Além disso, o ano letivo começou. Estou com um monte de coisa pra fazer (ainda não estou acostumado com o ritmo), mas vou voltar a postar ativamente.

De qualquer maneira, a pausa foi boa para uma reflexão pessoal e político-filosófica. Essas mudanças meus leitores provavelmente perceberão nos próximos artigos [ou talvez não].