Listo aqui cinco objetivos (talvez utópicos, talvez eu desista deles na próxima semana) para os próximos 50, 60 anos.

0. Ganhar uma medalha numa final mundial de um ACM ICPC.

Não é simplesmente pela competição, que é muito divertida. É também porque isso precisa de uma quantidade de estudo de ciência da computação e prática na resolução de problemas que fará diferença pro resto da minha vida e me ajudará com os outros objetivos. Afinal, a vida não passa de uma série de problemas que precisam ser resolvidos da maneira mais eficiente possiǘel.

1. Obter um bom PhD numa boa instituição.

Novamente não é simplesmente pelo prestígio e porque isso é importante na Academia, mas porque o PhD significa muita pesquisa e muita pesquisa significa MUITO conhecimento. Conhecimento este que será necessário pros próximos itens…

2. Solucionar o problema da segurança em São Paulo.

As pessoas acham que isso é impossível. Porém, eu quero resolver esse problema com ciência da computação, não com conversa mole ou politicagem. A realidade é que resolver o problema da violência em São Paulo não passa de um problema de otimização (minimizar a diferença social, minimizar o uso de drogas, maximizar a quantidade de pessoas felizes, maximizar a quantidade de respeito entre as pessoas…). Vou abstrair o problema, determinar suas causas e resolver uma por uma, de modo a contribuir pra uma cidade tão importante pra tantas milhões de pessoas.

3. Desenvolver a cura do câncer.

Na minha opinião o câncer é o mais cruel dos problemas de saúde. Atinge muita gente, sem motivo. Vem de repente, tortura e mata. Por isso acho fundamental resolver esse problema, que pode inclusive me atingir um dia. Como farei isso? Se eu soubesse, já teria feito. Mas, basicamente, atacando-o da mesma maneira que todos os outros problemas.

4. Receber um Turing Award.

Creio que será natural depois dos itens 2 e 3.

Em primeiro lugar quero afirmar aos desavisados que o curso de Ciência da Computação hoje é, na maioria dos lugares, não mais do que o estereótipo indica: um curso de viciados em jogos. Até aí tudo bem; afinal cada um faz o que bem entende nos seus momentos de lazer.

Porém, eu acho que esse fato colaborou para esse bacharelado se transformar num reduto de usuários de computador, pessoas que leram “Computação” no nome e pensaram: “Eu gosto de mexer no computador, acho que este é o meu curso”.

Se já sabemos que funciona, pra que provar?

A realidade que percebo nas turmas, tanto na UFSC quanto no IME-USP, é decepcionante. Quando um professor dá um curso mais forte e teórico, vários alunos se espantam e reclamam que o curso não está formando para a prática. Pior: em muitas universidades o curso está mudando de cara pra satisfazer estes estudantes e não o contrário, como deveria ser. O IME-USP ainda tem um curso excelente, mas advinhe o que os alunos da minha turma aprenderam na primeira matéria do curso (chamada de Introdução à Computação)? Java e programação orientada a objetos. Eles aprendem classes e métodos antes de aprenderem operadores lógicos e laços. Na única aula que fui da disciplina, o professor falava bem do Java porque as classes e métodos podem ter acentos!!!

A situação é tão desanimadora que às vezes penso que o nome do meu curso deveria mudar para não pegar desavisados que não procuram o que é antes de entrar. Deveria ser algo como Bacharelado em Ciência dos Algoritmos, Bacharelado em Matemática Discreta, que tal? Não sei. Mas é obviamente uma besteira: o que precisa mudar são as pessoas. Tanto as que entram no curso, quanto as pessoas em geral, que pedem favores pra cientistas da computação pensando que eles são técnicos de informática. As pessoas precisam entender o que é o curso antes de entrar nele, precisam saber que Ciência da Computação é um ramo da matemática que existe desde muito antes da criação dos computadores digitais.

O primeiro parágrafo do texto da Wikipedia em português sobre Ciência da computação diz (e juro que não fui eu que editei!):

Ciência da computação é o estudo dos algoritmos e suas aplicações, bem como das estruturas matemáticas indispensáveis à formulação precisa dos conceitos fundamentais da teoria da computabilidade e da computação aplicada. Desempenha por isso um papel importante na área de ciência da computação a formalização matemática de algoritmos, como forma de representar problemas decidíveis, i.e., os que são suscetíveis de redução a operações elementares básicas, capazes de serem reproduzidas através de um qualquer dispositivo mecânico/eletrônico capaz de armazenar e manipular dados. Um destes dispositivos é o computador digital, de uso generalizado, nos dias de hoje, pelo custo reduzido dos componentes eletrônicos que formam o seu hardware.

Se o Java já tem um heap implementado para que reinventar a roda?

Edsger Dijkstra, um dos grandes cientistas da computação de nossa história, disse certa vez:

Ciência da Computação está tão relacionada aos computadores quanto a Astronomia aos telescópios, Biologia aos microscópios, ou Química aos tubos de ensaio. A Ciência não estuda ferramentas. Ela estuda como nós as utilizamos, e o que descobrimos com elas.

É por tudo isso que abandono a sala ao ouvir que hoje em dia classes são mais importantes do que laços e nomear corretamente funções é mais importante do que conhecer algoritmos. (Sim, já ouvi isso de um professor dentro da universidade.)

Declaro-me a favor de um curso de Ciência da Computação onde os computadores sejam tratados apenas como ferramentas. Há outros cursos (técnicos) para quem não pensa assim e entra na universidade buscando uma formação sobre desenvolvimento ágil e produtividade. Não estou criticando quem busca isto. Porém, na minha opinião, estes definitivamente não deveriam entrar num curso chamado Bacharelado em Ciência da Computação.

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

Soma de PA

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:

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("-1\n");
    } else {
        printf("%d\n", movimentos);
    }

    return 0;
}

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

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.

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 ;)