ONI 2003 - Alcunhas

O segundo problema das finais das ONI 2003 chama-se Alcunhas. Neste problema, temos um dicionário com N palavras (N <= 1000) com até 30 letras. Posto isto, é dado um número indeterminado de nomes de pessoas na mesma linha separados por espaços e temos de terminar quais os nomes cujas iniciais formam palavras do dicionário. Exemplo: as iniciais de "Rita Inês Costa Almeida" formam a palavra "rica".

Pesquisa Binária - Parte 4: Uma pergunta de entrevista tramada

Para fechar este ciclo sobre a pesquisa binária, sugiro uma pergunta de entrevista:

Dados 2 arrays de inteiros ordenados de forma crescente, determina o K-ésimo número mais pequeno do conjunto dos 2 arrays em tempo sublinear e com O(1) de memória extra.

Pesquisa Binária - Parte 3: Problema EKO - SPOJ

O último post foi dedicado a alguns fundamentos sobre a pesquisa binária. Às vezes não é óbvio que podemos utilizar este método de pesquisa e obter um algoritmo eficiente. Considerem o problema EKO do SPOJ como exemplo:

Temos uma floresta com 1 000 000 de árvores e queremos obter pelo menos M (<= 2 000 000 000) de madeira. Podemos cortar todas as árvores a uma certa altura inteira, ficando com o que for cortado. A que altura devemos cortar as árvores de modo a obter pelo menos M de madeira e o mínimo desperdício?

Pesquisa Binária - Parte 2: Fundamentos

No último post, falei um pouco sobre um método de pesquisa chamado Pesquisa Binária. Pegando na pesquisa num dicionário como exemplo, procurei demonstrar que nós próprios utilizamos este método intuitivamente. Enquanto que o outro post foi mais dedicado a código, neste post pretendo explorar um pouco os fundamentos que nos permitem usar este método de pesquisa.

Pesquisa Binária

Um dos problemas mais frequentes no dia-a-dia é a procura de informação. Dependendo do tipo de pesquisa, nós vamos descobrindo e utilizando truques para agilizar esta pesquisa. Um exemplo da nossa infância é a procura de uma palavra no dicionário. Como é que nós procuramos o significado da palavra "inócuo" no dicionário?

Suponhamos que o dicionário tem 1000 páginas. Uma abordagem comum é abrirmos o dicionário no meio, 500ª página. Digamos que calhamos numa página cujas palavras começam por "L". Isto significa que "inócuo" tem de estar para a esquerda no dicionário pois "I" vem antes do "L".
Assim, podemos repetir o processo mas considerando apenas a primeira metade das páginas. Desta vez vamos à 250ª página e suponham que esta página tem palavras começam por "F". Deste modo, sabemos que "inócuo" tem de estar para a direita - iríamos para a 375ª página a seguir. Após repetir o processo, vamos encontrar (eventualmente) uma página referente à letra "I". De seguida, continuamos com a 2ª letra da palavra a procurar - "n" em "inócuo" - e assim sucessivamente até encontrar a palavra.

Exemplo da redução sucessiva do espaço de pesquisa numa pesquisa binária

A procura no dicionário é provavelmente intuitiva para toda a gente e pode até parecer estranho sistematizar este processo. No entanto, é esta sistematização que nos permite aplicar este método num programa. No exemplo anterior, começamos com um dicionário de 1000 páginas e fomos reduzindo o intervalo de páginas a procurar (espaço de pesquisa) para metade em cada iteração: 1000 -> 500 -> 250 -> 125 -> 63 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1. Reparem que necessitamos de procurar apenas 10 páginas em vez de 1000 para encontrar a palavra.

Este método tem o nome de Pesquisa Binária (Binary Search no TopCoder). Visto que reduzimos o espaço de pesquisa para metade em cada iteração, a complexidade temporal deste método é O(log N): log₂(1000) ~ 10. O único requisito da pesquisa binária é que exista uma ordem no input, seja ele um dicionário (palavras ordenadas alfabeticamente), um array de números ordenados ou outra.
Implementação em C++ da pesquisa de um número num array ordenado de forma crescente (retorna o índice no array:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// Se existirem valores repetidos iguais a "valor", retorna um qualquer. int PesquisaBinaria(int* valores, int n, int valor) { int esq = 0, dir = n-1; while (esq <= dir) { int mid = (esq + dir) / 2; if (valores[mid] == valor) { // encontrou! return mid; } else if (valores[mid] < valor) { // está na parte direita esq = mid+1; } else { // está na parte esquerda dir = mid-1; } } return -1; // inexistente }

2 problemas relacionados já referidos em posts anteriores são:

• Procurar o menor número maior ou igual a um valor dado - função lower_bound em C++
• Procurar o menor número maior do que um valor dado - função upper_bound em C++

Este problema pode ser abordado com pesquisa binária. A diferença para a pesquisa binária tradicional é que não procuramos um número especifico. Não terminamos a pesquisa precocemente, mas encurtamos o espaço de pesquisa até 1 elemento.

Notem que a diferença entre as duas funções é apenas uma condição com < e outra com <=. Caso não exista solução, as funções devolvem n, o número de elementos do array.
No caso do LowerBound, se existirem múltiplos valores iguais ao valor a procurar, retorna o menor índice no array com esse valor.

1 2 3 4 5 6 7 8 9 10 11 12 13

// Procura o menor número maior ou igual ao valor dado num array ordenado int LowerBound(int* valores, int n, int valor) { int esq = 0, dir = n-1; while (esq <= dir) { int mid = (esq + dir) / 2; if (valores[mid] < valor) { // está na parte direita esq = mid+1; } else { dir = mid-1; } } return esq; }

1 2 3 4 5 6 7 8 9 10 11 12 13

// Procura o menor número maior do que o valor dado num array ordenado int UpperBound(int* valores, int n, int valor) { int esq = 0, dir = n-1; while (esq <= dir) { int mid = (esq + dir) / 2; if (valores[mid] <= valor) { // está na parte direita esq = mid+1; } else { dir = mid-1; } } return esq; }

Existem outras aplicações da pesquisa binária. Por exemplo: como encontrar a raiz quadrada de um número sem recorrer a funções standard?

Follow-up: número de pares de números cuja soma é <= S

No último post, apresentei algumas abordagens para verificar se existem 2 números num array cuja soma é S. Por fim, sugeri um follow-up: e se fosse para contar o número de pares de números cuja soma é menor ou igual a S?

Para começar, a abordagem O(N²) precisa apenas de uma pequena alteração para contar os pares:

1 2 3 4 5 6 7 8

long long ContaPares(int* valores, int N, int S) { long long resultado = 0; for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] <= S) resultado++; return resultado; }

Note-se que se o array tiver uma dimensão considerável, e.g. ~100 000, o resultado pode exceder facilmente os 32 bits dos ints. Por outro lado, um programa com complexidade 100000²  é lento. Só esta função demoraria cerca de 15 segundos no meu computador.

Ordenação ajuda?
Como queremos os pares menores ou iguais a S, ordenar volta a parecer fazer sentido. Voltando ao exemplo dado no último post, o array ordenado fica -3, -2, 1, 5, 6, 7, 10 e S = 12.
Para o número -3, precisamos de saber quantos números existem menores ou iguais a S - (-3), ou seja, 15.
Para -2, seria quantos <= 14,
Para 1, quantos <= 11,
etc.

Se viram os links dados no último post, isto pode ser feito de forma eficiente com pesquisa binária. Assim, basta procurar qual é o índice do primeiro número do array ordenado maior do que S - número_actual e contar quantos números existem entre o número actual e esse índice.
No caso do C++, basta usar a função upper_bound().

1 2 3 4 5 6 7 8 9 10 11

long long ContaParesNlogN(int* v, int N, int S) { sort(v, v+N);  long long resultado = 0; for (int i = 0; i < N; i++) { // v+i+1 porque procuramos a partir da posição i+1 // caso não exista nenhum número > S-v[i], pos = N int pos = upper_bound(v+i+1, v+N, S-v[i]) - v; resultado += pos - (i + 1); } return resultado; }

Temos a ordenação e é feita uma pesquisa binária para cada um dos N números. Assim, o tempo de execução é O(N log N).

De modo análogo ao problema anterior, podemos voltar a eliminar a pesquisa binária. Se -3 + 10 for maior do que S, então o 10 não vai formar um par válido com nenhum outro número e pode ser descartado.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

long long ContaParesNlogNv2(int* v, int N, int S) { sort(v, v+N); long long resultado = 0; int a = 0, b = N-1; while (a < b) { // descarta números que formam pares inválidos. while ((b > a) && (v[a] + v[b] > S)) b--; // conta os pares (a,a+1), (a,a+2), ... (a,b) = b - a pares resultado += b - a; a++; } return resultado; }

O ciclo while exterior tem, no máximo, N-1 iterações. Cada iteração do ciclo while interior descarta um número do fim do array e retira uma iteração ao ciclo exterior porque decrementa b. Assim, o tempo de execução é O(N). Contudo, o tempo total continua dominado pelo O(N log N) da ordenação.

E hashing?
Como vimos no post anterior, as hash tables são muito úteis. No entanto, não podem ser usadas em todas as situações. Para contar o número de pares de forma eficiente, precisamos de usar a ordem dos números. As hash tables são excelentes para inserir, eliminar ou pesquisar elementos, mas não nos dizem nada sobre a ordem dos números e são inúteis para este problema.

O(N) é possível?
No caso de arrays já ordenados, sim. Basta usar o método referido acima.
Para arrays não ordenados, estamos limitados pela ordenação. No caso de termos números inteiros, temos:

• Counting Sort: pode ser utilizado quando sabemos que os números estão contidos num intervalo pequeno (e.g. entre 0 e 1000, -100 e 100 ou 1000 e 9999).
• Radix Sort: depende do número de bits K necessário para representar todos os números e é bastante útil em algumas situações. O tempo de execução é O(K * N) e é considerado linear se K for considerado uma constante (K é independente do valor N).

Dados N números inteiros, existem 2 números cuja soma é igual a um dado número S?

No último post, usei o seguinte problema como exemplo:

Dados N números inteiros, existem 2 números cuja soma é igual a um dado número S?

A solução mais óbvia é testar todos os pares de números e foi demonstrado que o seguinte algoritmo tinha um tempo de execução O(N²).

1 2 3 4 5 6 7

bool VerificaPares(int* valores, int N, int S) { for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) if (valores[i]+valores[j] == S) return true; return false; }

A notação Ó-grande significa que o tempo de execução do algoritmo é no máximo proporcional a N².
Agora o desafio é: como fazer melhor para podermos suportar mais de 10000 números?