Arquivo da tag: olimpíadas

Provisoriamente 2^4

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.

Saiu o resultado da modalidade programação nível 2 da OBI2007. Eu fiz 210 pontos, atingindo a décima-sexta colocação. A pontuação foi melhor que eu pensava, porque soluções de força bruta levaram uma grande quantidade de pontos. Porém, o que está previsto no regulamento é que 10 pessoas (no mínimo) viajarão para Campinas.

Agora vejam minha lógica: todos na Olimpíada Brasileira de Informática são programadores. Nosso sistema de numeração é o binário. Um número igual ou maior que 10 em decimal deve ser? Exatamente: 16 (10000 em binário).

Dezesseis primeiros colocados

  1. Eduardo Augusto Ribas
  2. André Linhares Rodrigues
  3. David Nissimoff
  4. Daniel dos Santos Marques
  5. ALEXANDRE NOBUO KUNIEDA
  6. REGIS PRADO BARBOSA
  7. Ricardo Hahn Pereira
  8. Rodrigo Alves Lima
  9. Cesár Ryudi Kawakami
  10. Gabriel Luís Mello Dalalio
  11. José Marcos Andrade Ferraro
  12. Fábio Mallaco Moreira
  13. Hailton Ferraz da Silva Junior
  14. Daniel Santos Ferreira Alves
  15. Paulo André Carvalho de Melo
  16. Tiago Madeira

A classificação oficial e a lista de convocados para a seletiva da IOI deve ser divulgada na semana que vem.

Segunda fase da OBI2007

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.

A prova de segunda fase da Olimpíada Brasileira de Informática aconteceu há duas semanas e eu havia me esquecido de comentar aqui no blog como eu fui. O resultado deve sair amanhã ou depois de amanhã, segundo um dos caras responsáveis pela organização no orkut. Se tudo der certo e Éris quiser eu participarei pela quarta vez do curso de programação e da seletiva para a IOI.

Telemarketing (OBI2007 – Programação Nível 2 – Segunda Fase)

A solução mais eficiente usa heaps. Sem conseguir pensar nesta solução no momento da prova, implementei uma força bruta bem otimizada. Infelizmente, ela tem um pequeno erro que uma alma boa que se apresenta como CEO da Oracle encontrou para mim:

No seu programa, você faz um “for” que vai de “ultimo” até “n”, armazenando o id do vendedor que vai ficar desocupado primeiro na variável “mt”. Então você faz um “for” de 1 até “ultimo” mudando a variável “mt” apenas quando o vendedor ficar livre antes do “mt”, sendo que, como o id dele é menor, deve atender a ligação caso fique disponível antes ou ao mesmo tempo em que o vendedor “mt” ficar livre. Para resolver isso, fiz um “for” que vai de “ultimo” até 1 usando um “if” com “<=”.

Acredito que receberei no máximo 20/100 pontos.

#include <stdio.h>
#include <values.h>
 
#define NMAX 1010
 
int main() {
	int n, l, duracao, c=0, ocupado[NMAX], mt, ligacoes[NMAX], oc;
	int i, j, ultimo;
 
	scanf("%d %d", &n, &l);
 
	for (i=1; i<=n; i++) {
		ocupado[i]=0;
		ligacoes[i]=0;
	}
 
	ocupado[0]=MAXINT;
	ultimo=0;
 
	for (i=1; i<=l; i++) {
		scanf("%d", &duracao);
		c=0;
		mt=0;
		for (j=ultimo+1; j<=n; j++) {
			if (!ocupado[j]) {
				ocupado[j]=duracao;
				ligacoes[j]++;
				c=1;
				ultimo=j;
				break;
			} else {
				if (ocupado[j]<ocupado[mt]) {
					mt=j;
				}
			}
		}
		if (!c) {
			for (j=1; j<=ultimo; j++) {
				if (ocupado[j]<ocupado[mt]) {
					mt=j;
				}
			}
			oc=ocupado[mt];
			ultimo=0;
			for (j=1; j<=n; j++) {
				ocupado[j]-=oc;
			}
			ocupado[mt]=duracao;
			ligacoes[mt]++;
		}
	}
 
	for (i=1; i<=n; i++) {
		printf("%d %dn", i, ligacoes[i]);
	}
 
	return 0;
}

Pizza (OBI2007 – Programação Nível 2 – Segunda Fase)

A solução mais eficiente usa programação dinâmica. A minha solução é uma força bruta, mais simples impossível. O programa está correto, mas não passará em muitos casos de teste por estourar o tempo limite. Espero mais uns 20/100 pontos.

#include <stdio.h>
 
#define MAX 100010
 
int main() {
	int n, soma;
	int i, j;
	int k[MAX];
	int maximo=0;
 
	scanf("%d", &n);
	for (i=1; i<=n; i++) {
		scanf("%d", &k[i]);
		k[i+n]=k[i];
		if (k[i]>maximo) {
			maximo=k[i];
		}
	}
 
	if (maximo==0) {
		printf("0n");
		return 0;
	}
 
	for (i=1; i<=n; i++) {
		soma=0;
		if (k[i]>0) {
			for (j=i; j<i+n; j++) {
				soma+=k[j];
				if (soma>maximo) {
					maximo=soma;
				}
			}
		}
	}
 
	printf("%dn", maximo);
 
	return 0;
}

Labirinto (OBI2007 – Programação Nível 2 – Segunda Fase)

O único problema que resolvi de maneira eficiente. A solução transforma o problema do labirinto em um grafo e depois chega à solução com uma busca em largura. Nesse eu espero a pontuação máxima, 100/100 pontos.

#include <stdio.h>
#include <values.h>
 
#define NMAX 55
#define VERTICES 2510
 
int n, m;
int nivel[VERTICES], vizinhos[VERTICES];
int fila[VERTICES*VERTICES], nvl[VERTICES*VERTICES];
int max[VERTICES];
int grafo[VERTICES][VERTICES];
int saida=MAXINT;
 
int identificador (int a, int b) {
	return (b+(a-1)*m);
}
 
int rn (int nivelerrado) {
	while (nivelerrado>9) {
		nivelerrado-=10;
	}
	return nivelerrado;
}
 
int main() {
	int i, j;
	int idmax, atual, idv;
	int niv, nivv, niva;
	int ini, fim;
 
	scanf("%d %d", &n, &m);
 
	idmax=n*m;
 
	for (i=1; i<=idmax; i++) {
		for (j=1; j<=idmax; j++) {
			grafo[i][j]=0;
		}
		vizinhos[i]=0;
		max[i]=0;
	}
 
	for (i=1; i<=n; i++) {
		for (j=1; j<=m; j++) {
			atual=identificador(i, j);
			scanf("%d", &nivel[atual]);
			if (i-1>0) {
				idv=identificador(i-1, j);
				if (idv>0) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (j-1>0) {
				idv=identificador(i, j-1);
				if (idv>0) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (i+1<=n) {
				idv=identificador(i+1, j);
				if (idv<=idmax) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			if (j+1<=m) {
				idv=identificador(i, j+1);
				if (idv<=idmax) {
					grafo[atual][vizinhos[atual]++]=idv;
				}
			}
			grafo[atual][vizinhos[atual]++]=atual;
		}
	}
 
	ini=0;
	fim=0;
	nvl[fim]=0;
	fila[fim++]=1;
	while (ini!=fim) {
		niv=nvl[ini];
		if (niv<saida) {
			atual=fila[ini++];
			niva=rn(nivel[atual]+niv);
			if (atual==idmax) {
				if (niv<saida) {
					saida=niv;
				}
			} else {
				for (i=0; i<vizinhos[atual]; i++) {
					idv=grafo[atual][i];
					nivv=rn(nivel[idv]+niv);
					if (nivv<=niva+1&&niv+1>max[idv]) {
						nvl[fim]=niv+1;
						max[idv]=niv+1;
						fila[fim++]=idv;
					}
				}
			}
		} else {
			ini++;
		}
	}
 
	printf("%dn", saida);
	return 0;
}

Conclusão

O resultado da olimpíada deve sair amanhã ou depois de amanhã e a nota de corte deve ser entre 100 e 150 pontos. Pelos meus cálculos, eu devo ter feito 140 (20+20+100), o que talvez me classifique para a próxima fase. Mais notícias a qualquer momento ;)

OBI2007 – Primeira fase

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.

Não divulgarei minhas soluções (aka gabarito… :p) até sexta-feira, que é quando os professores já vão ter enviado a prova para a comissão organizadora da Olimpíada Brasileira de Informática.

Ontem, sábado 17 de março, foi a primeira fase da OBI. Eu resolvi a Iniciação Nível 1 para me divertir, vi a prova da Programação Nível 1 (que a Carol resolveu, com uma noção de C muito boa adquirida em um mês) e solucionei a prova da Programação Nível 2. Só vou falar sobre ela por enquanto, depois crio outros posts para falar sobre as outras.

Pra começar, a prova estava fácil. Eu resolvi em duas horas. Isso foi uma opinião de todos que fizeram a prova. Creio que estava mais fácil que a do ano passado. O caderno de tarefas era composto por cinco questões:

  • Chocolate – Uma barra de chocolate é dividida várias vezes. O objetivo do programa é contar a quantidade de pedaços em que ela foi dividida. Basta ir pegando os números e ir somando-os -1.
  • Repositório – Uma lista de números de programas e a versão em que estão instalados num computador. Depois, uma lista de números de programas e a versão em que eles estão disponíveis na internet. Decidir que programas devem ser atualizados no computador (determinar sempre a maior versão) e imprimí-los.
  • Pastas – Dada uma lista de inteiros, verificar se os números aparecem a mesma quantidade de vezes (ex.: 1, 1, 2, 2, 3, 3 é válido; mas 1, 2, 2, 3, 3 não é).
  • Móbile – Interpretei como um problema de grafos. Sabe o que é um móbile? Você tem que ver se todos as peças de um mesmo “nível” tem a mesma quantidade de filhos. Eu fiz um BFS (busca em largura) para determinar o nível de cada um e depois foi só ver se todos de cada nível tinham a mesma quantidade de filhos.
  • Sacoleiro – Um cara quer comprar presentes para seus filhos. Em cada cidade há presente para um ou para outro, com preços diferentes. Ele quer ser justo. Seguindo um trajeto possível, passando por uma cidade e comprando um ou mais presentes ou até nenhum, qual a menor diferença possível entre os preços dos presentes? Sem dúvidas o problema mais difícil da prova (creio que o único difícil). Ainda não conheço a solução ideal, que deve usar programação dinâmica. Implementei um DFS (busca em profundidade) que testa todas as possibilidades.

No orkut já me disseram que cometi um erro ridículo:

No terceiro parágrafo do Repositórios, ele diz: “Um programa deve verificar então qual a versão de cada programa instalado nos computadores (todos eles possuem os mesmos aplicativos instalados e nas mesmas versões) e INSTALAR TODOS AQUELES QUE AINDA NÃO FORAM INSTALADOS ou cuja versão instalada seja anterior a versão mais recente.” Portanto, se um programa disponível na internet não está instalado nos computadores, ele deve ser instalado.

E meu Sacoleiro provavelmente não vai passar no tempo. Então espero 300 pontos e alguns quebrados.

O resultado sairá até o dia 7 de abril lá no site deles. Eu gero uma lista de classificação quando sair. :)

for (d=hoje; d<=17/03; d++) { Estude – OBI }

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.

IMPORTANTE: Esse post não é recomendado pra quem nunca programou. Escrevi sem pensar neles… :-)

Bom… Existem pessoas que sabem programar e não programam. O difícil na arte de programar é pensar, porque o resto é escrever em inglês e se acostumar com uma sintaxe rigorosa.

Comecei ontem a ensinar um amigo a programar em C para participar da OBI 2007, que foi anunciada nessa semana. Eu poderia ensinar Pascal, que é mais que suficiente para olimpíadas (quem conhece o André Linhares entende o que eu quero dizer…), mas resolvi ensinar C porque eu me embabacaria no Pascal e no C eu vejo os blocos mais “definidos” com as chaves; aqueles begins e ends “sujam” o código. E como diz o lema do sistema desse blog, code is poetry.

O reverendo e meus leitores mais novos devem estar se perguntando: como o Tiago é capaz de fazer essas loucuras? É verdade que fiquei um bom tempo sem escrever sobre programação, mas adoro isso! É lazer pra mim e essa também é a minha profissão, já que eu não consigo viver desse blog (por culpa sua que não clica nos meus anúncios…). Só quando começo a brincar é que lembro como é divertido e acho que é porque eu me sinto “no poder”. :-)

Mas voltando ao assunto… Esse meu colega é campeão regional de matemática e tem uma facilidade incrível para matérias exatas (e pras humanas mais ainda, eu acho). Eu estava sem nada pra escrever aqui no blog e resolvi escrever sobre o que eu vou ensinar pra ele amanhã: arrays e for.

Meu aluno está resolvendo a prova da Programação Nível 1 da OBI2005. Ele já resolveu a Frota de Táxi e agora precisa resolver o problema Campos de Minhoca.

O problema é que, pela primeira vez, ele se depara com uma situação em que tem que receber como entrada uma tabela completa! Sugeri que ele usasse dois while, um dentro do outro. Ele pensou um pouco e conseguiu fazer o seguinte código:

scanf("%d %d", &n, &m);
 
natual=1;
while (natual<=n) {
	matual=1;
	while (matual<=m) {
		scanf("%d", &valor);
		matual=matual+1;
	}
	natual=natual+1;
}

Perfeito. Era o que eu queria que ele fizesse. Mas agora entenda sua situação: como armazenar todos esses números pra depois trabalhar com eles?

Dessa maneira, cada vez que recebemos um novo elemento da tabela, colocamos numa variável valor e ao final do recebimento da entrada ficaremos apenas com o último elemento da tabela.

E então entram os arrays…

Arrays são matrizes de matemática ou, numa língua muito mais fácil, tabelas. Vamos supôr que eu receba 1000 valores e queira saber qual é o maior deles. Imaginem como seria para declarar suas variáveis, recebê-los e tratá-los:

int var1, var2, var3, var4, ..., var1000;
 
scanf("%d", &var1);
scanf("%d", &var2);
scanf("%d", &var3);
scanf("%d", &var4);
...
scanf("%d", &var1000);
 
if (var1>maior) {
	maior=var1;
}
 
if (var2>maior) {
	maior=var2;
}
 
if (var3>maior) {
	maior=var3;
}
 
...

Impossível! Totalmente inviável. Então alguém teve a brilhante idéia de criar um elemento que guarda várias variáveis de uma vez. Então surgiram os arrays. Você cria uma só variável e na sua declaração coloca o número de elementos que ele tem dentro de chaves.

int var[1001];

Depois para receber os valores você pode então simplesmente usar o while como usou no exemplo do Campos de Minhoca:

int var[1001], indice;
 
indice=1;
while (indice<=1000) {
	scanf("%d", &var[indice]);
	indice=indice+1;
}

E para ver qual é o maior deles basta usar mais um while:

indice=1;
while (indice<=1000) {
	if (var[indice]>maior) {
		maior=var[indice];
	}
}

Mas peraí… Então como faríamos no Campos de Minhoca? Lá não temos só uma lista de N números, mas uma tabela mesmo, com altura e largura. É simples, basta fazer com que cada índice dessa lista seja outra lista.

int tabela[1001][1001];

Assim, podemos acessar todos os elementos e pra saber o elemento da coordenada 5, 23 basta usar a variável tabela[5][23].

Aí aquele primeiro código do Campos de Minhoca torna-se:

scanf("%d %d", &n, &m);
 
natual=1;
while (natual<=n) {
	matual=1;
	while (matual<=m) {
		scanf("%d", &valor[natual][matual]);
		matual=matual+1;
	}
	natual=natual+1;
}

As variáveis [n,m]atual vão crescendo e preenchendo a tabela. :)

Só que acontece que se programássemos dessa maneira gastaríamos uma porção de códigos e ficaríamos confusos pra trabalhar com arrays, tendo que sempre verificar os índices e acabaríamos errando bastante. Então criou-se o for. O for é uma simplificação desse tipo de while. Você diz que:

para todo natual de 1 a n, faça:
	alguma coisa
fim-para

Escrever for em Pascal é super divertido, porque você se sente falando com o computador:

for i:=1 to 100, do begin
	código aqui
end;

No C existe uma sintaxe mais versátil, mas que pode ser um pouquinho mais difícil de entender no início:

for (atribuição; condição; incremento)

A atribuição é onde você coloca o primeiro valor do índice. A condição é a condição para que o enquanto continue funcionando. O incremento é o que ele deve fazer ao final de cada loop (geralmente é aumentar um).

Então, ao invés de fazer esse while:

indice=1;
while (indice<=1000) {
	scanf("%d", &var[indice]);
	indice=indice+1;
}

Você pode escrever:

for (indice=1; indice<=1000; indice=indice+1) {
	scanf("%d", &var[indice]);
}

E como resolver a parte da entrada do Campos de Minhoca sabendo disso?

Simples… Basta colocar um for dentro do outro:

scanf("%d %d", &n, &m);
 
for (i=1; i<=n; i++) {
	for (j=1; j<=m; j++) {
		scanf("%d", &matriz[i][j]);
	}
}

Observação 1: Escrever variavel++ é a mesma coisa que escrever variavel=variavel+1.

Observação 2: Geralmente utiliza-se i para o primeiro for, depois j, k, l e eu nunca tive que passar do l. :)

Observação 3: Se eu queria um vetor de 1000 posições lá em cima, por que eu declarei 1001? Bom… O C conta a partir de 0. Quando eu peço 1000, ele vai me dar um vetor de 0 a 999. Já que eu queria ter o var[1000] eu precisei declarar de 1000+1=1001.

Ficou claro ou muito confuso? Se deu pra entender isso aí, agora é só mandar a ver no resto do problema! :)

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

Primeira fase das Olimpíadas de Matemática

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.

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.

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á 12 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…

Fase de Correção

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