Problema D - Experiência microscópica

O Problema

Dado o número de bactérias $N$ na placa do João e um número máximo de comparações $Q$, descobrir quantos tipos de bactérias diferentes existem usando apenas o seu método de determinar se duas bactérias têm a mesma cor no máximo $Q$ vezes.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Solução Base

A solução mais simples possível para este problema passa por comparar cada par de posições consecutivas da placa de bactérias. Como sabemos que as bactérias do mesmo tipo/cor estão todas seguidas, sabemos que quando encontrarmos um par que difere estamos num novo grupo de bactérias e por isso podemos aumentar o número de tipos de bactérias que já vimos até agora.

O código para conseguir este tipo de solução é tão simples como:

#include "avaliador.h"

int resolver(int N, int Q)
{
  int total = 1;
  for (int i = 1; i <= N - 1; i++)
    if (!comparar(i, i + 1))
      total++;
  return total;
}

O número de comparações que fazemos é igual a $N - 1$, pois comparamos a posição 1 com a 2, a 2 com a 3, etc. Logo, esta solução seria suficiente para os dois primeiros grupos de casos de teste, ou seja, 25 pontos.

Solução (quase) Ótima

Para melhorarmos a solução mais simples, vamos fazer uso de uma das técnicas mais conhecidas em concursos de programação. Visto que o número máximo de tipos de bactérias é pequeno ($K$ é no máximo 100) e que os grupos de bactérias iguais estão juntos, podemos ser um pouco mais poupados nas comparações. Se analisarem bem o que a solução base faz reparam que está à procura de posições consecutivas onde as bactérias são de tipos diferentes. Uma forma alternativa de pensar neste processo é: se $i$ for a posição de uma bactéria de um certo tipo, qual é a posição $j$ mais próxima de $i$ tal que as bactérias em $i$ e $j$ são de tipos diferentes e $i$ precede $j$ (ou seja, $i < j$)?

A solução base responde a esta pergunta andando uma posição de cada vez, mas podemos poupar em comparações se utilizarmos pesquisa binária. Vamos tentar responder à pergunta feita atrás para uma bactéria na posição $i$: vamos escolher uma bactéria $l$ entre $i$ e $N$ e comparar o seu tipo com $i$. Se forem do mesmo tipo, então todas as bactérias entre $i$ e $l$ são do mesmo tipo, pois sabemos que bactérias do mesmo tipo estão juntas, ou seja, a posição $j$ que procuramos não pode estar nesse intervalo. Se não forem do mesmo tipo, então todas as bactérias entre $l$ e $N$ são de tipos diferentes da bactéria $i$, pela mesma razão, logo a posição $j$ que procuramos não pode estar nesse intervalo. Isto significa que, se considerarmos um intervalo de posições possíveis para $j$ (inicialmente será o intervalo $[i, N]$), ao escolhermos a posição do meio desse intervalo podemos reduzir o intervalo para metade. Agora podemos repetir a mesma operação até o intervalo conter apenas de uma posição. Isto é exatamente como funciona a técnica de pesquisa binária:

Artigo: Pesquisa Binárias

Este artigo contém uma introdução a pesquisa binária.

Um código possível para conseguir esta solução seria:

#include "avaliador.h"

int resolver(int N, int Q)
{
  int inicial = 1, total = 0;
  // vamos encontrar a ultima bacteria no mesmo grupo
  // ate chegarmos a ultima bacteria (N)
  while (inicial <= N) {
    // pesquisa binaria entre inicial e N
    int lo = inicial, hi = N;
    while (lo < hi) {
      int med = (lo + hi) / 2;
      if (med == lo)
        med++;

      if (comparar(inicial, med))
        lo = med;
      else
        hi = med - 1;
    }

    inicial = lo + 1;
    total++;
  }

  return total;
}

Esta melhoria significa que fazemos no máximo $\log(N)$ comparações por grupo, ou seja, no máximo $K\log(N)$ comparações. Visto que $N$ é no máximo 100.000, $\log(N)$ é aproximadamente 17, ou seja, no pior caso, esta solução pode fazer cerca de 1700 comparações (por exemplo, se os primeiros $K - 1$ grupos tiverem todos apenas uma bactéria), logo esta solução seria suficiente para os quatro primeiros grupos de casos de teste, ou seja, 75 pontos.

Solução ótima

A solução anterior está mesmo próxima dos 100 pontos, só precisamos de descer o número de comparações ligeiramente de 1700 para a baixo de 1500. Há várias formas de o conseguir, mas todas se baseiam numa propriedade estrutural: $K$ é muito mais pequeno que $N$. O que é que isto tem de importante? Se $K$ é pequeno, então sabemos que a maioria dos grupos de bactérias vão ser pequenos. Em média, cada grupo terá tamanho $N / K$ e sabemos que por cada grupo com mais de $N / K$ bactérias há pelo menos um grupo com menos de $N / K$ bactérias. Isto significa que para a maior parte dos grupos o ponto que procuramos com a pesquisa binária (a última bactéria do mesmo grupo) estará mais próxima do extremo esquerdo do intervalo. Logo, em vez de procurarmos no ponto intermédio entre os extremos, basta começarmos a procura mais perto do extremo esquerdo, por exemplo: seja $[e_e, e_d]$ o intervalo em que vamos fazer a nossa pesquisa binária, ou seja, queremos encontrar a última bactéria posicionada nesse intervalo com o mesmo tipo da bactéria na posição $e_e$ (tal como no código da solução anterior). Na pesquisa binária normal começamos por comparar $e_e$ com $(e_e + e_d) / 2$, mas alternativamente vamos começar por comparar $e_e$ com $\min(e_e + N / K, N)$, pois esta posição será, em média, a posição que procuramos. Após esta comparação inicial, podemos fazer o resto da pesquisa como a pesquisa binária comum ou tentar aplicar a mesma propriedade novamente.

Em média, este tipo de solução irá usar cerca de $K\log(N / K)$ comparações, ou seja, cerca de 1000 comparações. Na prática usa um pouco mais, cerca de 1200, mas é possível provar que teoricamente usa sempre menos de 1500. Assim, esta solução seria suficiente para os cinco grupos de casos de teste, ou seja, 100 pontos.

Nota final

Um tema comum a todos os problemas das ONI é a complexidade temporal das soluções. Este problema parece ser uma exceção, mas na verdade estamos a medir uma complexidade em termos de uma quantidade diferente: o número de comparações. Normalmente usamos a notação $O()$ para escrever complexidades, mas neste problema todas as nossas contas do número de comparações usadas foram exatas porque uma difereça constante entre soluções podia significar que não seja suficiente para o certo grupo de casos de teste.

Para mais informação sobre complexidade podem consultar o artigo do costume:

Artigo: Introdução à Análise de Algoritmos

Este artigo contém uma introdução a complexidade de algoritmos.