Problema B - Desorientados

O Problema

Dados $N$ postos de controlo, $M$ participantes na ONI, bem como os postos de controlo $D_i$ em que cada atleta terminou a sua prova, e $Q$ perguntas $q_i$ sobre câmeras, descobrir quantos participantes passaram por cada uma das câmeras dadas.

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

Vamos começar pela solução mais simples possível, que passa por simular a corrida representando cada posto por uma array e marcando cada posição quando alguém lá passa. Para cada valor $D_i$ fazemos um ciclo de 0 a $D_i$ incrementando cada posição da array. Depois, para cada uma das $Q$ câmaras apenas temos de olhar para valor de índice $q_i$ da array que mantemos. O código seguinte consegue exatamente isto:

#include <stdio.h>

int arr[1005];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);

  int di;
  for (int i = 0; i < m; i++) {
    scanf("%d", &di);
    for (int j = 0; j < di; j++)
      arr[j]++;
  }

  int q, qi;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d", &qi);
    printf("%d\n", arr[qi - 1]);
  }
  
  return 0;
}

Vamos agora fazer a análise da complexidade temporal deste algoritmo. Se ainda não leste o conjunto de artigos de iniciação às ONI é muito importante que o faças. Entre outros temas mais introdutórios e avançados abordamos como analisar um programa de modo a conseguir estimar quantos pontos terá. Vamos fazer essa análise a seguir para o código acima a seguir.

Artigo: Guia de iniciação às ONI

No 4o artigo deste guia abordamos o tema de análise de complexidade.

Para cada um dos $M$ valores $D_i$ fazemos um ciclo de 0 até esse valor, preenchendo cada posição, logo, visto que $D_i$ pode ser no máximo $N$, fazemos $O(N \cdot M)$ operações. Posteriormente, para cada um dos valores $q_i$ só temos de olhar para um valor numa array, ou seja, no fazemos mais $O(Q)$ operações. No total isto perfaz $O(NM+Q)$ operações, que apenas satisfaz a subtarefa 1 e obtém 20 pontos.

Subtarefa 2

Esta solução é um pouco diferente da anterior, baseada numa observação que temos de fazer. Vamos supor que guardamos todos os valores de $D_i$ numa array e agora queremos saber quantos atletas passaram pela câmara $q_j$. Ora, sabemos que para cada atleta $i$, de o seu posto final $D_i$ for maior ou igual a $q_j$ então ele passou por esta câmara. Isto significa que apenas temos de contar quantos valores de $D_i$ são maiores ou iguais a $q_j$! Podemos fazer isto fazendo um ciclo pela lista de valores que guardámos e contar quantos há seguindo a regra dada. O código seguinte consegue exatamente isto:

#include <stdio.h>

int arr[10005];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);

  int mi;
  for (int i = 0; i < m; i++) {
    scanf("%d", &mi);
    arr[i] = mi;
  }

  int q, qi;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d", &qi);

    int count = 0;
    for(int j = 0; j < m; j++)
      if (arr[j] >= qi)
        count++;
    printf("%d\n", count);
  }
  
  return 0;
}

Porque é que isto é melhor que a solução base? Ora reparem que para cada um dos $M$ atletas apenas temos de o guardar numa array, ou seja fazemos $O(M)$ operações no total. De seguida, para cada uma das $Q$ câmaras só temos de percorrer os $M$ atletas para ver quantos passaram por esta câmara, ou seja, fazemos no total $O(MQ)$ operações. No total isto perfaz $O(M + MQ) = O(MQ)$ operações, o que é suficiente para as subtarefas 1 e 2, obtendo 45 pontos.

Subtarefa 3

Vamos agora ver uma outra forma de obter 45 pontos resolvendo a subtarefa 3 em vez da 2. Esta solução é muito semelhante à solução da subtarefa 1, mas vamos melhorar uma das suas componentes.

Ora, na nossa solução base, para cada um dos $D_i$ percorríamos a array da posição 0 até à posição $D_i$ incrementando cada uma. Em vez disto vamos fazer o seguinte: para cada $D_i$ incrementamos apenas a posição $D_i$. Depois de processarmos cada uma, vamos percorrer a array desde a posição $N$ até à posição 0 (a ordem importa aqui, como verão) mantendo um contador que inicialmente é 0 que irá representar o número de atletas que chegaram à posição atual (que estamos a processar neste momento). Quando chegamos à posição $i$, aumentamos este contador com o valor contido na posição $j$ da array. Porquê? Porque suponhamos que a posição $j$ da array marcada contém o valor 5. Isto significa que ao fazermos o nosso processamento inicial vimos que há 5 valores de $D_i$ iguais a $j$, ou seja, houve 5 atletas que terminaram a sua prova exatamente aqui. Isto implica que estes 5 atletas passaram por todas as posições anteriores de 0 a $j$, logo, o nosso contador é aumentado por 5 unidades para refletir isto. Ao percorrermos toda a array como descrito preenchemo-la exatamente como na nossa solução base, mas, como iremos ver, de forma muito mais eficiente. Assim podemos usar a mesma ideia para ver os valores para cada câmara. O código seguinte consegue exatamente isto:

#include <stdio.h>

int arr[100005];

int main() {
  int n, m;
  scanf("%d %d", &n, &m);

  int mi;
  for (int i = 0; i < m; i++) {
    scanf("%d", &di);
    arr[di - 1]++;
  }

  int contador = 0;
  for (int i = n - 2; i >= 0; i--) {
    contador += arr[i];
    arr[i] = contador;
  }

  int q, qi;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d", &qi);
    printf("%d\n", arr[qi - 1]);
  }

  return 0;
}

Neste solução fazemos uma operação por cada um dos $M$ atletas seguido de um ciclo pelos $N$ postos para preencher a nossa array. Para responder aos valores das câmaras só olhamos para a array, ou seja, no total fazemos $O(N + M + Q)$ operações, o que é suficiente para as subtarefas 1 e 3 obtém assim 45 pontos.

Solução ótima

Vamos voltar à solução que fizemos para a subtarefa 2 e tentar melhorá-la. Para isso vamos usar duas técnicas muito conhecidas: ordenar e fazer uma pesquisa binária. Se não conheces estas técnicas podes aprender sobre elas no nosso guia de iniciação às ONI, que foi mencionado anteriormente. O artigo número 5 aborda exclusivamente estes dois tópicos com grande detalhe.

Artigo: Guia de iniciação às ONI

No 5o artigo deste guia abordamos o tema de ordenação e pesquisa binária.

Como referido, para uma dada câmara $j$, a nossa tarefa é apenas contar quantos valores de $D_i$ são maiores ou iguais a $q_j$. Vamos imaginar que a lista dos $D_i$ estava ordenada. Nesse caso, se encontrarmos o primeiro elemento desta lista que é maior ou igual a $q_j$ sabemos que todos os elementos seguintes são maiores ou iguais a $q_j$ e os restantes menores. Vejamos um exemplo.

Suponhamos que $q_j = 10$ e que a nossa lista ordenada de $D_i$ de cada atleta é exatamente $[1, 4, 8, 10, 14, 20, 21]$. Os atletas com $D_i$ maior ou igual a 10 passaram pela câmara que nos interessa, ou seja, há exatamente 4 (de valores 10, 14, 20 e 21) com essa propriedade. O primeiro elemento maior ou igual a 10 é o elemento de valor 10, que se encontra na posição 3 desta lista (indexada em 0). Visto que $M = 7$, ou seja, a lista tem 7 elementos, há $7 - 3 = 4$ elementos maiores ou iguais a 10 na lista, e assim há 4 elementos que passaram pela câmara 10.

Agora, como podemos encontrar o primeiro elemento de uma lista ordenada com valor maior ou igual a outro dado? É para isto que serve pesquisa binária! No artigo mencionado acima o exemplo da secção "Aplicações de pesquisa binária em listas" explica exatamente como se faz uma pesquisa binária deste género para encontrar o último valor menor ou igual a um outro dado, que é equivalente.

Falta-nos ordenar a lista de valores $D_i$, mas para isso podemos usar um qualquer algoritmo eficiente de ordenação clássico. No mesmo artigo a secção "Ordenar eficientemente" explica em detalhe um possível algoritmo.

Finalmente, falta-nos analisar esta solução. Precisamos de ordenar uma lista de $M$ elementos, o que podemos fazer em $O(M\log(M))$. Posteriormente, temos de fazer uma pesquisa binária numa lista de $M$ elementos por cada uma das $Q$ câmaras, ou seja, fazemos $O(Q\log(M))$ operações. No total fazemos $(O(Q + M)\log(M))$ operações, o que é suficiente para os 100 pontos!