Discussão sobre o problema Número Proibido
UnB-\(\gamma\)

A descrição do problema é bastante clara e não esconde o que precisa ser feito, no entanto é necessário que o aluno tenha alguma "malícia" algorítmica para entender como atacar o problema, mas vamos discutir isso com calma.

Primeiramente o enunciado explica que existe uma lista de números proibidos e eles possuem um tamanho bem específico, até \(140000\) números, e cada um deles é um número positivo entre \([0,2^{31}]\) (note que o intervalo é fechado), o que significa que esses números cabem em um número inteiro.

A entrada dos números inteiros é dada por um \(N\), indicando a quantidade de números proibidos, e depois os \(N\) numerais. O código para entrada é bastante direto e possui complexidade em \(\mathcal{O}(N)\), parecido com o código abaixo:

1: int proibidos[140000];
2: int proibidos_ct;
3: scanf("%d",&proibidos_ct);
4: for(int i=0;i<proibidos_ct;i++)
5:   scanf("%d",&proibidos[i]);

O código acima não tem nenhum segredo, mas o problema começa a aparecer nas próximas linhas do enunciado.

O enunciado nos conta que o depois da lista de números proibidos acontecerá um número indeterminado de perguntas, e cada pergunta consiste em saber se um número dado pertence ao conjunto de números proibidos.

A informação da quantidade indeterminada de perguntas nos sugere que elas devem acontecer diversas vezes, muitas vezes mais que a quantidade de números proibidos. E é nesse ponto que você deve ficar encafifado.

Caso você já tenha levado um Time Limit Exceeded, você percebeu que o tempo limite de execução é de meros \(0,2495\) segundos, você identifica isso dentro do log enviado pelo mojinho ao invocar o comando getlog.

Mas vou um pouco mais além e vou mostrar a informação presente nas máquinas. Hoje temos duas máquinas operando como juízes, a jaguapitanga e a ovomaltine (principal), veja a spec delas:

• jaguapitanga
  • arch: x86₆₄
  • cpu: Intel(R) Celeron(R) CPU 3867U @ 1.80GHz
  • memory: 8077352
• ovomaltine
  • arch: x86₆₄
  • cpu: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
  • memory: 16315452

As máquina são pouco diferentes e o tempo de execução são:

• jaguapitanga
  • c: .3980
• ovomaltine
  • c: .2495

Mesmo a ovomaltine sendo mais rápida os tempos não são tão diferentes. Note que a jaguapitanga só é utilizada quando a ovomaltine fica fora do ar, opera como um backup.

Agora vou executar alguns experimentos na jaguapitanga para que consigamos ter uma noção dos tempos que as coisas levam.

Considerando uma ideia bobinha, por exemplo, um código com um vetor de \(140000\) elementos procurando um elemento que não existe, ou seja, efetuando uma busca sequencial. Como o problema nos fala que a quantidade de perguntas é indeterminada, vamos monstar um exemplo que procure \(140000\) vezes um número que não existe.

Como vamos utilizar uma busca sequencial, significa que vamos ter que percorrer o vetor de números proibidos inteiro para descobrir que o número não está lá, então podemos dizer que a busca sequencial é proporcional a \(\mathcal{O}(N)\) operações, como \(N\) é \(140000\) e vamos realizar \(140000\) buscas falhas temos operações propocionais a \(N^2\).

Vamos ver como se comporta um código bobinho desses:

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: int achou(int num,int *v,int l,int r)
 4: {
 5:   for(int i=l;i<=r;i++)
 6:     if(v[i]==num)
 7:       return 1;
 8:   return 0;
 9: }
10: int main(void)
11: {
12:   int vetor[140000];
13:   //preparando para gerar números aleatórios
14:   srand(140000);
15:   //preenchendo o vetor com números aleatórios inferiores a 1milhão
16:   for(int i=0;i<140000;i++)
17:     vetor[i]=rand()%1000000;
18: 
19:   //fazendo 140000 buscas pelo número 1milhão
20:   for(int i=0;i<140000;i++)
21:     if(!achou(1000000,vetor,0,140000-1))
22:       printf("nao\n");
23:     else
24:       printf("sim\n");
25: }
26: 

Executando este código na jaguapitanga, e compilando com os mesmos parâmetros que usamos no MOJ o tempo de execução fica em enormes \(15,61\) segundos. Muito acima do tempo limite estipulado pelo MOJ.

Veja abaixo como foi executado:

ribas@jaguapitanga:/tmp$ make busca_bobinha CFLAGS='-O2 -static'
cc -O2 -static    busca_bobinha.c   -o busca_bobinha
ribas@jaguapitanga:/tmp$ time ./busca_bobinha > /dev/null

real  0m15.616s
user  0m15.607s
sys 0m0.008s

O resultado é muito aquém ao que esperamos, pois o TL é de \(0,2495\) segundos. Como poderíamos reduzir este tempo?

Lá em EDA-1 você deve ter aprendido que existe um algoritmo que sabe fazer uma busca mais rapidamente que a busca sequencial. Esta é a busca binária. O problema é que a busca binária precisa de um vetor ordenado para poder realizar a busca rapidamente.

Então PARA TUDO! Precisamos ordenar esse vetor antes de fazer a busca!

Aprendemos diversos algoritmos de ordenação neste semestre e temos uma noção de como cada um se comporta.

Peguei rapidamente o Benchmark de Ordenação e resolvi experimentar na jaguapitanga primeiramente testando os clássicos:

• bubblesort

  • seletionsort
  • insertionsort
  • mergesort

  Sabemos que somente o mergesort, dentre os listados acima, possui complexidade em \(\mathcal{O}(N \log{}(N))\), enquanto que os outros estão em \(\mathcal{O}(N^2)\).

  Table 1: Tabela de tempos de execução para os algoritmos de ordenação para entradas de tamanhos entre \(2^8\) e \(2^{20}\), com tempo limite de execução em 20 segundos

  Alg/#Elementos	256	512	1024	2048	4096	8192	16384	32768	65536	131072	262144	524288	1048576
  bubblesort	0.00	0.00	0.00	0.01	0.04	0.20	0.91	3.89	16.01	TLE	TLE	TLE	TLE
  selectionsort	0.00	0.00	0.00	0.00	0.01	0.05	0.23	0.91	3.61	14.42	TLE	TLE	TLE
  insertionsort	0.00	0.00	0.00	0.00	0.00	0.01	0.04	0.16	0.67	2.79	11.69	TLE	TLE
  mergesort	0.00	0.00	0.00	0.00	0.00	0.00	0.00	0.01	0.03	0.06	0.12	0.25	0.53

Para gerar a tabela acima o benchmark de ordenação foi executado da seguinte maneira na jaguapitanga:

TIMEOUT=20 BINARY="bubblesort selectionsort insertionsort mergesort" make time.aleatorio

Veja que os algoritmos quadráticos (os três primeiros) crescem na proporção esperada, ou seja, ~4x mais tempo é necessário para ordenar um vetor com o dobro do tamanho.

Logo, é perceptível que somente o mergesort consegue ordenar o vetor dentro do limite de tempo tão justo, ou seja, sabemos que ele ordena \(262144\) elementos em \(0,12\) segundos.

Nesse ponto sabemos o que fazer! Para poder utilizar a busca binária devemos ordenar o vetor com o mergesort, para que seja possível sobrar mais tempo para realizar as consultas.

Modificando o Código da Busca Bobinha para ordenar com MergeSort e realizar a busca binária, ficaria da seguinte forma:

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: //Mergesort e Intercala OMITIDOS! Use a versão disponibilizada na Aula 3, seção 3.1
 4: 
 5: int buscabinaria(int num,int *v,int l,int r)
 6: {
 7:   if(l>r) return -1;
 8:   int meio=(l+r)/2;
 9:   if(less(v[meio],num))
10:     return achou(num,v,meio+1,r);
11:   else if(lesseq(v[meio],num))
12:     return meio;
13:   else
14:     return achou(num,v,l,meio-1);
15: }
16: int main(void)
17: {
18:   int vetor[140000];
19:   //preparando para gerar números aleatórios
20:   srand(140000);
21:   //preenchendo o vetor com números aleatórios inferiores a 1milhão
22:   for(int i=0;i<140000;i++)
23:     vetor[i]=rand()%1000000;
24: 
25:   //Tenha cuidado com a chamada do MergeSort, o intervalo é FECHADO [l,r]
26:   //por isso é subtraído 1 do tamanho do vetor, para ficar [0,139999]
27:   //que representa os 140000 elementos.
28:   mergesort(vetor,0,140000-1);
29: 
30:   //fazendo 140000 buscas pelo número 1milhão
31:   for(int i=0;i<140000;i++)
32:     if(!buscabinaria(1000000,vetor,0,140000-1))
33:       printf("nao\n");
34:     else
35:       printf("sim\n");
36: }
37: 

O código acima possui a implementação da BuscaBinária e utiliza o MergeSort implementado na Aula 3.

Seguimos a execução conforme abaixo:

ribas@jaguapitanga:/tmp$ make busca2 CFLAGS='-O2 -static'
cc -O2 -static    busca2.c   -o busca2
ribas@jaguapitanga:/tmp$ time ./busca2 >/dev/null

  real  0m0.032s
  user  0m0.028s
  sys 0m0.005s

O que antes demorava mais de \(15\) segundos, passou a executar em apenas \(0,032\) segundos, bem abaixo do tempo limite estipulado no sistema MOJ.

Implementado um código que utiliza esta estratégia sai do custo de \(\mathcal{O}(N^2)\) operações para \(\mathcal{O}(N log{}(N) + N log{}(N))\), pois a ordenação fica em \(\mathcal{O}(N log{}(N)\), e a busca binária fica em \(\mathcal{O}(log{}(N))\), sendo executada \(N\) vezes, pois são feitas \(140000\) perguntas.

A busca que implementamos neste exercício mental trata de uma entrada próxima do pior caso, e que força uma implementação simples a ficar com custo proporcional a \(\mathcal{O}(N^2)\), enquanto que podemos implementar de uma maneira mais eficiente apenas pensando nos custos envolvidos.