Programação para concursos - Parte 2

[Warrior]

Estive os últimos 5 dias num estágio com os Professores Pedro Guerreiro da Universidade Nova de Lisboa e Pedro Ribeiro da Faculdade de Ciencias do Porto, visto ser um dos 4 representantes nas olimpíadas internacionais, e decidi "acabar" o tópico iniciado aqui

Durante o estágio resolvemos fundamentalmente problemas da UVa ( http://acm.uva.es/problemset/ ) logo será aí que me irei basear, mostrando exemplos de problemas, e dando dicas para a resolução.

Não devo postar as minhas resoluções para estes problemas pois acho que cada um de vós deve subir no "ranking" através do vosso próprio suor.

No outro tópico começei por falar em Ordenações de vectores. Este não será excepção. Mas desta vez não irei abordar o algoritmo em si (algo que aprendi é que em concursos não perdemos tempo a ordenar à mão) mas sim usando a função qsort() da biblioteca stdlib.h.

E se pode parecer complicado ao inicio: nada com dois exemplos para a perceberem melhor.

Aplicado a inteiros:

int compare(const void *a,const void *b) {
   int c,d;
   c=*(int*)a;
   d=*(int*)b;
   return c-d;
}
int main() {
   int v[5];
   int i;
   for (i=0;i<5;i++) scanf("%d",&v[i]);
   qsort(v,5,sizeof(int),compare);
   for (i=0;i<5;i++)
       printf("%d\n",v[i]);
   system("PAUSE");
   return 0;
}

Aplicado a strings:

int compare(const void *a,const void *b) {
   char c,d;
   c=*(char*)a;
   d=*(char*)b;
   return c-d;
}
int main() {
   char s[30];
   int i;
   scanf("%s",s);
   qsort(s,strlen(s),sizeof(s[0]),compare);
   printf("%s\n",s);
   system("PAUSE");
   return 0;
}

Basicamente a função recebe 4 parametros: o vector, o numero de elementos, o tamanho de cada elemento (inteiro/char) e uma função externa que faz a comparação entre dois elementos. Podem parecer estranhos os parametros que a função recebe, mas apesar de se poder "aldrabar" os parametros fazendo-se um casting implicito, pode dar erro com algumas flags de compilação mais "chatas".

No caso dos inteiros, podia-se simplificar com:

int compare(int *a,int *b) {
   return *a-*b;
}
(...)
   qsort(v,5,sizeof(int),(void *)compare);
(...)

Mas se tentarmos compilar com, por exemplo "-Wall -ansi -pedantic" iremos obter Warnings, o que é igual a "Compilation Error" em concursos. Depende do vosso objectivo. Num programa "caseiro" pode-se sempre simplificar, logo não há necessidade de preocupações.

Podem encontrar bons problema para ordenação de vectores Number Chains ou DNA Sorting.

Geração de numeros primos:

Não irei voltar a abordar este tópico (foi falado aqui) mas podem encontrar problemas: Prime Factors, Goldbach's Conjecture

Todos estes passam por gerar os numeros primos usando o Crivo de Erastotenes.

Congruencias

Isto é também algo que eu referi por alto aqui.

E não há muito mais a dizer, são essas as fórmulas.

A parte complicada é decidir: como aplicá-las?

Problem E - Ones

Desistam de testar 1 a 1. 100 1s não cabem num inteiro. E aplicar divisão a strings? Possivel, mas muito trabalho pela frente.

Como o resolver então?

Vou-vos resolver a parte mais dificil deste problema: (ou tentar)

Começemos pelo 7.

1 % 7 = 1 (resto da divisão de 1 por 7)

11 (ou seja 1 * 10 +1) % 7 = 4

111 (11*10+1) % 7 = ? Mais dificil de fazer de cabeça, não?

Segundo a formula das congruencias:

111 % 7 = ((1 % 7 * 10 +1) % 7)*10+1)%7. Ou seja, 6. Basicamente, 4*10+1=41%7 = 6.

Ou seja, para sabermos se 111 é divisivel por 7 ou não, basta-nos ir ao resto da divisão de 11 por 7 e aplicar uma pequena matemática. Bastante simples daqui para a frente, se a minha explicação tiver sido boa o suficiente..

Pesquisa binária:

Este tema também ja foi coberto aqui.

Mais um problema: Compound Words.

Também se podia resolver utilizando Hash Tables, algo que irei falar (espero) daqui a uns dias, mas demonstra bem a eficácia da pesquisa binária em relação à pesquisa linear. No pior caso (120.000 palavras no dicionario) a pesquisa binária só faz 17 (se não estou em erro, não me apetece fazer as contas) comparações contra as 120.000 da pesquisa linear.

Espero poder falar de Permutações, Combinações, Grafos, Hashing e Programação dinâmica..

[HecKel]

Boas!

Sou aluno da FCTUNL (onde o professor Pedro Guerreiro dá aulas) e tenho participado nas estapas desta ultima TIUP, é a minha primeira vez em concursos de programação..., pessoalmente não gosto muito de programar sob tensão no entanto é excelente para desenvolver o conhecimento de algoritmia, por vezes olhamos para o enunciado e vemos logo a resposta..., ou não 🙂 E quando já estamos à uns bons minutos a martelar naquela opção vemos que não era a mais sensata 😞

Não sei se vou participar na ultima etapa da TIUP, no entanto recomendo a todos nem que seja só pela curiosidade B)

abraços, HecKel

[Warrior]

Permutações

As permutações, tal como as combinações, devem ser usadas quando não existe um método 100% seguro para resolver o problema, de modo que testamos "todas" as soluções possíveis e daí escolhemos a melhor. (coloquei "todas" porque podemos utilizar o prunning ou o backtracking para "saltar" algumas soluções)

Como sempre, dois problemas: Collecting Beepers e o mais do que famoso 8 Queens Chess Problem

Vamos nos concentrar no primeiro. Podíamos pensar "se ele se dirigir sempre para o ponto mais perto, percorre a menor distância possível". Mas isso está errado. Vejam o seguinte exemplo, começando no top-left (usando a técnica enunciada) os beepers seriam recolhidos por esta ordem:

http://img212.imageshack.us/img212/4787/beepersdc2.th.jpg

Contudo, a distância mais curta seria desenhando somente um quadrado! Como saber então por que ordem recolher os beepers? Geramos todas as ordens possíveis, e testamos uma a uma. Sim, há problemas que inevitavelmente recorrem a este métodos "menos bonito".

char used[MAX+1];
int perm[MAX+1];
void goperm(int p,int n) {
int i;
if (p==n) {
	for (i=0;i<n;i++) 
		printf("%d",perm[i]);
	putchar('\n');
	return;
}
for (i=1;i<=n;i++) {
	if (!used[i]) {
		used[i]=1;
		perm[p]=i;
		goperm(p+1,n);
		used[i]=0;
	}
}
}
int main() {
goperm(0,4);
return 0;
}

Basicamente, mantemos 2 vectores: um onde guardamos a informação se já foi ou não usado o elemento "x" do vector, e outro onde vamos estar a criar a permutação propriamente dita.

Neste código imprimem-se todas as permutações, mas podia-se efectuar uma chamada para outra função para fazer o processamento. Neste caso, ver a distância entre os beepers.

goperm(0,3) gerará os conjuntos:

123

132

213

231

312

321

Combinações

Tal como as permutações, as combinações também são usadas quando queremos testar as soluções possíveis.

Só que desta vez, agrupamos o nosso conjunto de numeros k a k.

Se partirmos do conjunto:

1 3 5 7 e agruparmos os numeros em grupos de dois temos:

1 3

1 5

1 7

3 5

3 7

5 7

int comb[3];
void gocomb(int n,int k,int p,int l) {
int i;
if (k==p) {
	for (i=0;i<k;i++) 
		printf("%d",comb[i]);
	putchar('\n');
}
for (i=l;i<=n;i++) {
	comb[p]=i;
	gocomb(n,k,p+1,i+1);
}
}
int main() {
gocomb(5,2,0,1);
    system("pause");
return 0;
}

Podem aplicar combinações na resolução deste problema: CD