Introdução às competições de programação

Se já estão interessados em formar equipas/participar em torneios, mandem-me um mail para formarmos uma espécie de "núcleo" de programação e criarmos os nossos torneios internos na UA para preparação para a MIUP! Visitem também o problema deste mês e enviem ideias, sugestões, etc. Se houver interesse posso fazer outras páginas sobre algoritmos e estruturas de dados.

Conteúdo

Em Portugal o mais conhecido é talvez a MIUP (Maratona Inter-Universitária de Programação), que se realiza uma vez por ano numa Universidade portuguesa. A MIUP 2004 já decorreu na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa e Aveiro participou com 4 equipas, conseguindo os "aveiro_secreto" um 3º lugar. A MIUP 2005 já está a ser preparada e vai ser realizada em Aveiro! Por isso, temos este ano para nos preparar para no próximo ano participar com mais equipas e obter ainda melhores resultados!

Outra competição que surgiu como prova de treino para a MIUP é a TIUP (Torneio Inter-Universitário de Programação), que se realizou pela primeira vez este ano e que é constituída por vários torneios, de mês a mês, em que as equipas acumulam pontos como num campeonato. A próxima TIUP vai começar em Janeiro e é uma excelente prova para quem se inicia nestes torneios se ambientar com o sistema e o tipo de problemas, bem como com o stress!

A MIUP serve também de prova nacional para qualificações para a SWERC, uma prova internacional onde competem os melhores de alguns países europeus para depois se apurarem 1 ou 2 participantes para as finais mundiais. A SWERC 2004 é já em novembro e conta com a participação dos aveiro_secreto como uma das equipas portuguesas.

Há outros torneios de programação, como a CENPL (programação em lógica) e outros parecidos com a MIUP em se pode participar pela Internet.

Para participar é preciso ter sólidos conhecimentos de programação e de estruturas de dados, mas principalmente é precisa muita imaginação para resolver os problemas, e achar não só uma solução mas uma solução rápida, eficiente e robusta. Ao resolver estes problemas aprendemos vários algoritmos e de certo que melhoramos imenso o nosso desempenho como programadores.

É importante salientar o que é mais importante (uh...) aqui: Paciência. Montes dela.

2 Usar o stdin/stdout

Problema

"O input consiste num número N, seguido de N linhas cada uma com um número inteiro. O programa deve escrever como output o maior dos N números lidos."

Input (exemplo)

5
2
10
3
123
6

Output (do exemplo)

123

#include <stdio.h>

int main()
{
    int n;
    int i;
    int valores[1000];
    int maior;

    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
	scanf("%d", &valores[i]);
    }
    
    maior = 0;
    
    for (i = 0; i < n; i++) {
	if (valores[i] > maior)
	    maior = valores[i];
    }

    printf("%d\n", maior);
    
    return 0;
}

gcc programa.c -o programa -Wall

./programa < input.txt

./programa > output.txt

./programa < input.txt > output.txt

É preciso compreender como isto funcinou para poder prosseguir, mas não há muito mais para saber! Usar ficheiros de texto como input é muito útil para testar a validade do programa feito. Em C++, usa-se o cin e o cout para ler e escrever:

#include <iostream>

using namespace std;

int main()
{
    int n;
    int i;

    cin >> n;

    for (i = 0; i < n; i++)
	cout << i << "\n";

    return 0;
}

Outro problema é a linha maior = 0;. E se os números no input forem todos negativos? Então o programa escreve 0, que está errado porque 0 não foi o maior número lido.

Os programas devem prever todo o tipo de input válido e gerar respostas correctas para todos os casos. Outra solução que corrige estes problemas é a seguinte: o 1º número lido é assumido como o maior (isto resolve o problema dos números serem todos negativos). Há medida que forem lidos números, comparamos o número lido com o maior, e se for ainda maior guardamos esse número. Isto faz que com não seja preciso o array valores e resolve o problema dos inputs maiores que 1000 números e ainda faz o programa usar menos memória! O programa completo fica:

#include <stdio.h>

int main()
{
    int n;
    int i, tmp;
    int maior;

    scanf("%d", &n);
    
    for (i = 0; i < n; i++) {
	scanf("%d", &tmp);

	if (i == 0) {
	    maior = tmp;
	} else {
	    if (tmp > maior)
		maior = tmp;
	}
    }
    
    printf("%d\n", maior);
    
    return 0;
}

Dada uma matriz de dimensões MxN, em que cada posição (x,y) corresponde a um custo de passar nessa casa, determinar o custo mínimo para ir desde a casa (1,1) até à casa (M,N). Só é válido andar para cima, baixo, esquerda e direita.

1	2	3
4	5	6
7	8	9

a solução é 21, que é fazer o caminho 1-2-3-6-9. O input do programa consiste numa linha com 2 números M e N, que representam as dimensões da matriz. As seguintes M linhas têm N números cada uma, que correspondem ao custo da casa (x,y) onde x é a linha e y a coluna. Para o exemplo anterior vinha:

3 3
1 2 3
4 5 6
7 8 9

21

Um dado do problema é também o limite de M e N. Vamos assumir que M e N são sempre maiores que 0 e menores que 100. Outro dado é o custo máximo numa casa. Vamos assumir que os custos são sempre maiores que 0 e não tão grandes que façam problema em 2^32 bits :) Uma solução em C++ pode ser:

#include <iostream>

using namespace std;

int m, n;
int matriz[100][100];
bool marcados[100][100];
int melhor;
int total;

void saltar(int x, int y)
{
    if (marcados[x][y])
	return;

    marcados[x][y] = true;
    total += matriz[x][y];

    if (x == m-1 && y == n-1) {
	if (melhor == -1 || total < melhor)
	    melhor = total;
    } else {
	if (x != 0)
	    saltar(x-1, y);
	if (x != m-1)
	    saltar(x+1, y);
	if (y != 0)
	    saltar(x, y-1);
	if (y != n-1)
	    saltar(x, y+1);
    }

    marcados[x][y] = false;
    total -= matriz[x][y];
}

int main()
{
    int i, j;

    cin >> m >> n;

    for (i = 0; i < m; i++) {
	for (j = 0; j < n; j++) {
	    cin >> matriz[i][j];
	    marcados[i][j] = false;
	}
    }

    melhor = -1;
    total = 0;
    saltar(0, 0);

    cout << melhor << "\n";
    
    return 0;
}

A função saltar começa por ver se a casa onde entrámos está marcada; se sim, sai. Se não, marca a casa e adiciona o seu custo ao total. De seguida, se a casa é a final, guarda o total caso seja menor que o melhor encontrado ou caso não haja ainda um melhor. Se não for a última, saltamos para as casas à volta, mas só podemos saltar para casas válidas! Por exemplo, se o x é 0, não podemos saltar para a esquerda. Antes de sair da função, temos de desmarcar a casa e subtrair o seu custo ao total, para que o programa possa tentar outros caminhos.

Para compilar o programa, usa-se o comando

g++ ch4.cpp -o ch4 -Wall

./ch4 < ch4.txt

5 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

6 6
1 1 9 1 1 1
9 1 9 1 9 1
9 1 1 1 9 1
9 9 9 9 1 1
9 9 9 9 1 9 
9 9 9 9 1 1

./ch4 < ch4_3.txt

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

top

Vamos tentar perceber o que aconteceu. O nosso programa testa todos os caminhos possíveis desde o início até ao fim, para achar o melhor deles. Vamos modificar o programa para dizer também quantos caminhos diferentes percorreu. Para isso, adicionamos uma variável caminhos que aumentamos cada vez que chegarmos à casa final. O programa pode ser copiado daqui: ch4_2.cpp. Os resultados são:

Tamanho da matriz	Caminhos
1x1	1
2x2	2
3x3	12
4x4	184
5x5	8512
6x6	1262816

Como dá para ver, os caminhos que são testados explodem quando aumentamos só um bocado a matriz. Para 10x10 o número deve ser tão grande que é provável que o programa não acabe nem ao fim de um mês a correr. Se alguém corajoso tentar e conseguir que o programa chegue ao fim, pode enviar-me o tempo que demorou e quantos caminhos percorreu, para ficar aqui para registado para o bem da humanidade :)

O tipo de solução que usámos chama-se brute force, porque testa todas as maneiras possíveis de encontrar uma saída. Mas como deu para ver, apesar de o programa estar correcto pode não ser útil na prática por demorar demasiado tempo. É como tentar adivinhar uma password; um programa possível e correcto é um que testa todas as passwords possíveis até acertar, mas isso demora tanto tempo que nem adianta tentar. Este problema apareceu com este enunciado numa prova organizada pela Universidade do Porto em setembro de 2003. Pode-se consultar o site em http://acm.up.pt/local e pode-se encontrar o enunciado completo deste problema na secção "Historial", 2ª prova da edição de 2003, problema A: "Number Maze". Como se pode ver no enunciado, o limite do tamanho da matriz é 999x999! De certo que existem soluções bem melhores que a que usámos!

Uma solução muito mais rápida e eficiente é bastante complicada, mas penso apresentar uma solução deste problema depois de ter acabado esta e outras páginas sobre programação, principalmente as páginas sobre estruturas de dados e algoritmos. Se alguém estiver muito interessado posso arranjar a solução, mas não é trivial de perceber. A ideia da solução pode ser obtida analisando o que fazemos mentalemente para o exemplo de input 3: nós seguimos os 1's, porque é claramente um caminho menos custoso que seguir 9's. O programa não tenta de maneira nenhuma seguir um caminho especial; uma solução melhor deve valorizar caminhos menos custosos.

5 Falhas comuns nos programas

Às vezes, os resultados estão correctos mas são mal apresentados. Por exemplo, se o programa tivesse de dizer os sítios por onde passou, um por linha, e o programa os escreve-se todos na mesma linha, apesar de estarem correctos são um Presentation Error, ou seja, os dados não foram apresentados como se pedia. Isto normalmente significa uns espaços ou linhas em branco a mais.

Além disso, é preciso que o programa seja eficiente em tempo e espaço. Nas competições há sempre um limite de tempo e de memória que o programa pode usar, que se ultrapassar é dado como inválido. Um programa não pode ser como o dos caminhos, que demora muito, nem pode usar mais do que um certo número de MB de memória. Quando um programa demora demasiado tempo a falha mostrada é Time Limit Exceeded.

Um erro mais chato é o Segmentation Fault. Isso quer dizer que algures no programa, tentamos usar memória que não é do programa. Isso acontece normalmente ao usar (mal) ponteiros, e ao indexar arrays com índices negativos ou além do tamanho do array. Por exemplo, o 1º programa (que encontrava o maior número no input), para inputs com mais de 1000 linhas, provavelmente ia dar um segmentation fault (também se chama segfault).

Há outros erros mais são menos comuns. Quando o programa é aceite, aparece Accepted no sistema.

6 Usar o Mooshak

Depois de entrar, temos 4 áreas principais: "Submissions", "Ranking", "Questions" e "Printout". No Ranking estão as classificações das equipas. Para cada problema, é mostrado o tempo em que a equipa o conseguiu resolver (ou está em vazio, se ainda não tentaram). O número entre parêntesis é o número de vezes que tentaram mas não conseguiram. A coluna seguinte, "Solved", indica quantos já resolveram no total e a "Time" diz quanto tempo acumularam. Isto funciona assim: ganha quem resolver mais problemas (solved). Em caso de empate, desempata-se com o tempo usado. O tempo acumulado por cada equipa começa a 0. Quando resolvemos um problema, o tempo é aumentado pelo tempo que levámos desde o início da competição até entregarmos a resposta correcta. Por cada tentativa errada, o tempo aumenta 20 minutos. Por exemplo: mandamos uma solução ao fim de 1 hora para um problema e outra ao fim de 2 horas para outro. Se tentámos uma vez o 2º mas não foi aceite, o tempo acumulado fica então 1h + 2h + 20m = 3h20m. Normalmente é mostrado quanto tempo falta para acabar na página principal do Mooshak mas como esta página é um exemplo sem fim, não aparece o tempo.

Nas Submissions podemos ver se um programa que enviámos foi aceite ou não. Também dá para ver as tentativas de submissão das outras equipas, mas não dá para ver os programas delas.

Nas Questions aparecem as respostas dos organizadores às perguntas que fazemos. Podemos fazer uma pergunta caso não seja claro um enunciado usando o botão, bem, "Ask". Se quisermos uma versão imprimida de um programa que enviámos usamos o "Print" (e aparece o pedido nos Printouts). Isto é útil porque só há um computador por equipa, e se um programa estiver errado podemos pedir uma cópia imprimida para estudar enquanto outro membro da equipa usa o computador para tentar resolver outro problema.

A melhor maneira de aprender é mesmo a participar num torneio como a TIUP, que serve mesmo para treinar!

7 Exemplo usando o online-judge.uva.es

Vamos começar por nos registar. Usamos o link "Register". Depois de preencher tudo, é atribuído um User-ID, como "53120YF". A password é a que usámos no registo.

De volta à página principal, vamos consultar os problemas. Arrastando a página um pouco para baixo aparece uma tabela com vários volumes. Vamos começar por ver o "Volume I". Agora aparece uma lista de problemas, numerados. O número do problema é preciso para dizer o que estamos a tentar resolver quando enviarmos uma resposta. Vamos ver o primeiro, problema nº 100 "The 3n+1 problem". Depois de ler o enunciado e compreendido o problema (este é fácil...), vamos escrever uma solução. Em C++, aqui está uma: ch7.cpp

#include <iostream>

using namespace std;

int calc(int i, int j)
{
	int n, count, greater;
	
	if (i > j) {
		int tmp = i;
		i = j;
		j = tmp;
	}

	greater = 0;
	for (int iter = i; iter <= j; iter++) {
		n = iter;
		count = 1;
		while (n != 1) {
			if (n % 2 == 0)
				n /= 2;
			else
				n = 3*n + 1;
			count++;
		}

		if (count > greater)
			greater = count;
	}

	return greater;
}

int main()
{
	int i, j;
	
	while (cin >> i) {
		cin >> j;

		cout << i << " " << j << " " << calc(i, j) << endl;
	}
	
	return 0;
}

Agora, para enviar o programa voltamos à página principal e usamos o link "Submit your Code". Na página de submissão, temos de escrever o número do problema (tem de ser o número certo!), neste caso é o 100. Temos também de meter o nosso User-ID, como o "53120YF". Dizemos qual é a linguagem em que fizemos o programa (C++ neste caso, mas também podia ter sido C, Pascal ou Java) e podemos copiar o programa para a caixa "Source code" ou podemos enviar um ficheiro do disco com o botão "Browse...". Depois clicamos no botão "Submit problem". Supostamente, tudo corre bem e aparece uma página a dizer que foi recebida a submissão. Podemos ver logo se foi aceite o nosso programa no link "View YOUR SUBMISSIONS! in the judge status". Algures na página diz se foi aceite ou não, ou então diz que ainda está a correr.

Podemos ver a página de resultados de um utilizador qualquer no link "Author" (mais abaixo). Metemos o User-ID e aparece uma página com os problemas resolvidos e várias estatísticas do utilizador. O "53120YF" foi um utilizador que criei enquanto escrevia esta página e na página dele pode ver-se o problema 100 resolvido, e mais nenhum :)

8 Preparar-se para a MIUP

A melhor maneira de se prepararem para a MIUP 2005 é a resolver problemas das outras MIUPs, e os que estão no online-judge da Universidade de Valladolid. Um treino indispensável é a TIUP, que vai começar em Janeiro, onde podem treinar também contra o relógio e o trabalho em equipa para usar o computador o mais eficientemente possível.

Para estar apto para participar num concurso e ter bons resultados, recomendo domínio do C, algum do C++ (não é preciso muito, diria que basta saber usar templates) e muita prática. Eu pessoalmente uso o C++ por causa da STL. A STL é uma biblioteca que faz parte do standard C++ que inclui muitas estruturas de dados fundamentais como listas, árvores, stacks, etc e algoritmos de ordenação e outros. Isto poupa imenso tempo comparado com C, em que se tem de criar as listas e o resto à mão, além de estar sujeito a ter erros nessas partes do programa. A referência da STL está em http://www.sgi.com/tech/stl/ mas não serve de introdução. É preciso conhecimento aprofundado de estruturas de dados (ajuda muito tentar fazê-los à mão!). Uma página com uma boa introdução é http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/ds_ToC.html. É importante saber as vantagens/desvantagens de uma lista em relação a um array, a uma árvore, etc, e saber quais são as operações que são rápidas e lentas, nuns e noutras. Por exemplo, é mais rápido adicionar um elemento a uma lista do que a um array, mas é mais rápido ir buscar um elemento a uma array do que ao meio de uma lista.

Ao início, pode parecer ser muita coisa de uma vez. É bom não ficar desmotivado e persistir; a ordem que eu recomendo é esta:

Para começar, podem tentar resolver problemas mais simples, como o "3n+1". Convém ir aprendendo gradualmente algoritmos novos para conseguir resolver problemas mais complicados, mas se tentarem ir logo para os complicados pode ser desmotivante. Para já, podem tentar resolver o meu problema do mês.

Boa sorte e espero vir a competir com todos os que lerem isto na próxima MIUP!