Problema C - Aerobus

O Problema

Dada uma linha de montagem na qual estão a ser produzidas $N$ pás que se encontram em posições $X_i$, identificar o conjunto máximo de pás podem ser empacotadas em conjunto, onde cada pá no conjunto máximo está a uma distância menor ou igual a $D$ de pelo menos $K$ outras pás no conjunto.

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 5 grupos com restrições adicionais diferentes:

Solução dos casos especiais

Comecemos por analisar os casos em que $K$ = 1 e $K$ = 2 e a partir dessas ideias vamos construir a nossa solução para o problema geral.

O primeiro caso que temos de considerar, e o mais simples de todos, é o de $K$ = 1. Neste apenas temos de notar que para uma pá ser empacotada então tem de estar a no máximo $D$ de distância da próxima ou da anterior, pois assim esta tem uma pá à distância desejada e essa pá tem a pá atual a no máximo $D$ unidades de distância. Assim, basta fazer um ciclo e ver as distâncias de cada pá à próxima e à anterior e marcar consoante pode ou não ser empacotada.

Para o caso de $K$ = 2, vamos ter uma ideia semelhante, mas agora temos mais casos. Começamos por fazer um ciclo para passar por cada pá, como fizemos no parágrafo anterior. Ao percorrermos cada pá, podemos ver que os únicos casos em que não é empacotada é quando ou nenhum dos vizinhos está a uma distância válida, ou quando apenas um está. No primeiro caso podemos apenas ignorar esta pá, visto que não afeta qualquer outra pá e obviamente não faz parte da resposta. No entanto, no segundo caso teremos de ter mais cuidado. Vamos supor que estamos a considerar a pá $i$. Sabemos que pá $i$ não fará parte da resposta, mas pode acontecer que a pá vizinha desta tinha apenas dois vizinhos (sendo a $i$ um deles) e ao não contarmos $i$ para a resposta também não podemos contar a sua pá vizinha. O exemplo 2 do enunciado mostra exatamente isto.

Para resolver este problema podemos fazer o seguinte. Primeiro mantemos uma array que irá representar a resposta assim como um inteiro que representa o número de elementos na array de resposta a qualquer altura. Isto é análogo a usar a estrutura vector de C++, para quem conhece. Vamos percorrer a lista de pás e preencher esta array de resposta. Para cada pá verificamos no máximo até 4 vizinhos: os dois próximos elementos na lista (se existirem) e os dois últimos elementos da array de resposta. Porquê estes quatro? Porque só precisamos de 2 e se estes não forem vizinhos então não há mais nenhum que possa ser (pois estarão a uma distância superior). Agora, quando encontramos pelo menos 2 vizinhos adicionamos a pá que estivermos a processar à array de resposta, colocando-a na posição final disponível e incremento a nossa variável que representa o seu tamanho. Se não encontrarmos 2 vizinhos teremos de atualizar os últimos elementos desta array, como indicado no parágrafo anterior. Para tal fazemos um ciclo desde o último elemento da array de resposta até ao primeiro e vamos removendo elementos da array enquanto não forem válidos, ou seja, enquanto não tiverem pelo menos 2 vizinhos. Para tal apenas precisamos de olhar para os dois elementos anteriores na array de resposta, pois os elementos seguintes que possam existir não estarão na resposta.

A implementação da ideia anterior está no código seguinte:

#include <stdio.h>
#include <stdlib.h>

int N, D, K, resposta_tamanho;
int X[100005];
int resposta[100005];

int vizinho(int i1, int i2) {
  return abs(X[i1] - X[i2]) <= D;
}

int main() {
  scanf("%d %d %d", &N, &D, &K); // K == 2

  for (int i = 0; i < N; i++)
    scanf("%d", &X[i]);

  resposta_tamanho = 0;
  for (int i = 0; i < N; i++) {
    int num_vizinhos = 0;
    if (resposta_tamanho > 0 && vizinho(i, resposta[resposta_tamanho - 1]))
      num_vizinhos++;
    if (resposta_tamanho > 1 && vizinho(i, resposta[resposta_tamanho - 2]))
      num_vizinhos++;
    if (i + 1 < N && vizinho(i, i + 1))
      num_vizinhos++;
    if (i + 2 < N && vizinho(i, i + 2))
      num_vizinhos++;

    if (num_vizinhos >= 2)
      resposta[resposta_tamanho++] = i;
    else {
      while (resposta_tamanho > 0) {
        int num_vizinhos = 0;
        if (resposta_tamanho > 1 && vizinho(resposta[resposta_tamanho - 1], resposta[resposta_tamanho - 2]))
          num_vizinhos++;
        if (resposta_tamanho > 2 && vizinho(resposta[resposta_tamanho - 1], resposta[resposta_tamanho - 3]))
          num_vizinhos++;
        if (num_vizinhos < 2)
          resposta_tamanho--;
      }
    }
  }

  printf("%d\n", resposta_tamanho);
  for (int i = 0; i < resposta_tamanho; i++) {
    printf("%d", resposta[i] + 1);
    if (i == resposta_tamanho - 1)
      printf("\n");
    else
      printf(" ");
  }

  return 0;
}

Por cada pá apenas temos de verificar se têm mais de um vizinho ou não, processando-a de acordo com isso. Se a pá tiver dois vizinhos ou mais então apenas fazemos um número constante de operações. Caso contrário pode parecer que fazemos $O(N)$ por pá, mas reparem que cada pá só pode ser adicionada e retirada da array de reposta uma única vez, ou seja, no total fazemos $O(N)$ operações (este argumento é um pouco delicado, pensem bem nele). Isto significa que a ideia é rápida o suficiente para, em conjunto com o caso anterior, obter 30 pontos.

Solução base

Para uma solução para qualquer $K$ vamos generalizar a ideia que tivemos para $K$ = 2. Reparem que quando uma certa pá tem menos de $K$ vizinhos retiramo-la e queremos atualizar de alguma forma os seus vizinhos (para não contarem com este). Podemos ir retirando repetidamente as pás com menos de $K$ vizinhos no conjunto atual até não sobrar nenhuma ou todas terem mais resulta na resposta. Isto é, começamos por calcular o número total de vizinhos de cada pá e eliminamos as pás com menos de $K$. Repetimos este processo considerando apenas as pás que não foram eliminadas anteriormente. Haveremos de chegar a um ponto onde todas as pás têm $K$ vizinhos ou mais ou então eliminámos todas as pás.

Para percebermos porque é que o anterior funciona vamos tentar mostrar que esta ideia está correta. Qualquer pá que inicialmente tem menos de $K$ vizinhos não faz parte da resposta. No passo seguinte vamos, potencialmente, eliminar mais algumas pás que não têm $K$ vizinhos no conjunto de pás ainda não eliminadas. Podemos fazê-lo porque é impossível usarmos as pás que não têm $K$ vizinhos inicialmente. Podemos repetir o mesmo argumento depois de cada vez que eliminamos pás e no final temos um conjunto de pás que podem ser empacotadas e todas as outras não fazem parte da resposta, o conjunto que obtemos é máximo.

Para implementarmos isto mantemos uma array de quais pás ainda são válidas, ou seja, quais ainda não foram eliminadas e repetimos o processo de contar o número de vizinhos entre as pás até que uma passagem inteira não remova qualquer pá. O código seguinte implementa esta ideia:

#include <stdio.h>
#include <stdlib.h>

int N, D, K;
int X[100005];
int valido[100005];

int vizinho(int i1, int i2) {
  return abs(X[i1] - X[i2]) <= D;
}

int main() {
  scanf("%d %d %d", &N, &D, &K); // K == 2

  for (int i = 0; i < N; i++) {
    scanf("%d", &X[i]);
    valido[i] = 1;
  }

  int mudanca = 1;
  while (mudanca) {
    mudanca = 0;
    for (int i = 0; i < N; i++) {
      int num_vizinhos = 0;

      for (int j = 0; j < N; j++)
        if (i != j && valido[j] && vizinho(i, j))
          num_vizinhos++;

      if (num_vizinhos < K) {
        valido[i] = 0;
        mudanca = 1;
      }
    }
  }

  int resposta_tamanho = 0;
  for (int i = 0; i < N; i++)
    if (valido[i])
      resposta_tamanho++;

  int contador = 0;
  printf("%d\n", resposta_tamanho);
  for (int i = 0; i < N; i++) {
    if (valido[i]) {
      printf("%d", i + 1);
      contador++;
      if (contador == resposta_tamanho)
        printf("\n");
      else
        printf(" ");
    }
  }

  return 0;
}

Podemos ver que como em cada passagem retiramos pelo menos uma pá menos na última, fazemos no máximo $N$ passagens. Se por cada vez que estamos a contar os vizinhos de uma pá verificarmos para todos quais os que estão a no máximo $D$ de distância, fazemos $O(N)$ operações para isto, cada passagem passa uma vez por cada uma das $N$ pás e há no máximo $N$ passagens, ou seja, a complexidade final do nosso programa vai ser de $O(N^3)$, o que chega para o segundo grupo valendo mais 20 pontos.

Solução Melhorada

Vamos agora melhorar a ideia anterior um pouco. Primeiro vamos calcular o intervalo de pás que estão no máximo a $D$ de distância de cada pá, evitando recalculá-lo de cada vez. Primeiro determinamos a pá mais à esquerda e a mais à direita que satisfazem a condição. Começamos por marcar que a pá mais à esquerda da primeira é ela própria, pois não há nenhuma antes. Depois, para a $i$-ésima pá, vemos qual a pá mais à esquerda da anterior que está a no máximo $D$ distância dela, e partimos dessa avançando para a direita e vendo uma a uma até encontrar uma que satisfaça a condição para a atual, que existe sempre pois ela própria está à distância $0$ de si mesma, guardando quando encontrarmos uma. Esta ideia tem complexidade $O(N)$, pois apesar de podermos fazer $N$ operações duma vez, podemos verificar que nunca passamos mais de 2 vezes na mesma pá, a primeira para calcular e a segunda num possível cálculo associado às próximas pás.

A partir daqui, temos também os graus iniciais de cada pá (defina-se grau como número de vizinhos a no máximo $D$ de distância no conjunto atual), que guardamos para atualizar. Assim, em vez de passar por todas as pás várias vezes, apenas mantemos uma lista de todas as pás com menos de $K$ vizinhos inicialmente, e para cada uma delas vamos atualizar os vizinhos diminuindo em $1$ o grau. Sempre que uma pá passar a ter grau menor que $K$ adicionamos ao conjunto. Para atualizar os graus dos vizinhos basta utilizar os valores calculados anteriormente e fazer um ciclo que passe por cada um deles, verificando se deixam de ter grau maior ou igual a $K$ de cada vez.

A atualização associadas às pás que se encontram inicialmente no conjunto de pás com grau menor que $K$ obviamente tem complexidade $O(K)$, mas nós vamos atualizar e adicionar novas pás a este conjunto, qual a complexidade para essas pás? Podemos verificar que também é $O(K)$, pois caso uma pá tenha grau inicial maior que $2*K$, significa que tem de um dos lados $K$ pás à distância menor ou igual a $D$, e essas pás também satisfazem essa condição umas para as outras, pois as distâncias entre si são menores do que a da mais afastada da pá inicial. para perceber melhor analisemos a figura:

Para $K$ = 3, e $D$ = 10, a primeira pá é vizinha de todas à sua direita. Para qualquer par de pás das outras, a distância que as separa é menor que a distância que separa a mais à direita das duas da primeira, pois a primeira está mais à esquerda de todas. Assim, qualquer outro par de pás são vizinhas e têm todas grau maior ou igual a $K$ sempre, fazendo parte da resposta. Logo, qualquer pá com grau inicial maior ou igual a $2*K$ faz parte da resposta sempre, e apenas vamos ter de atualizar $O(K)$ pás sempre.

Assim, a complexidade final desta ideia é de $O(NK)$, pois podemos retirar cada pá uma vez e por cada remoção fazemos $O(K)$ operações. Isto chegaria para 70 pontos.

Solução Ótima

Falta-nos melhorar a parte de atualização. Para isto vamos utilizar uma estrutura de dados denominada de árvore de segmentos. Se ainda não conheces esta ideia, começa por ler o nosso artigo:

Artigo: Árvores de segmentos

Neste artigo apresentamos os básicos sobre segment trees.

Nesta nova ideia começamos por repetir o cálculo anterior para cada pá para descobrir o intervalo que esta afeta. Depois, construímos uma árvore de segmentos de mínimos, em que os valores base são os graus de cada pá. De seguida, encontramos o mínimo dos graus, partindo da raiz e vendo qual dos dois filhos tem menor valor e ir para esse e repetir até chegar a uma folha. Obtendo o mínimo, se este tiver grau maior ou igual a $K$ então o conjunto atual é a resposta. Caso não, vamos ter de retirar esta pá do conjunto e atualizar o intervalo correspondente subtraindo 1 a este todo e de seguida somando um valor muito grande à posição da pá, para esta não ser novamente encontrada como mínimo, a não ser que todas as outras já tenham sido retiradas do conjunto.

Para esta ideia ser eficiente, temos de atualizar um intervalo inteiro. Para isso, basta para cada nó da árvore de segmentos guardar uma variável extra que corresponde ao valor a adicionar a esse intervalo. Quando estamos a passar pela árvore em qualquer momento, propagamos sempre este valor, atualizando o mínimo (Se estamos a somar um certo valor a um intervalo inteiro, então o mínimo também aumenta nesse valor) e adicionando esse número à variável de cada um dos filhos, caso não se trate duma folha. Quando estamos a atualizar, sempre que o intervalo se encontra totalmente fora do que estamos a considerar ignoramos, se estiver dentro adicionamos o valor à variável e todos os outros casos fazemos recursivamente a atualização em ambos os filhos.

Podemos ver que esta ideia funciona em $O(N\log(N))$ devido às complexidades associadas a usar a árvore de segmentos, e como tal, dados os limites, chega para obter 100 pontos e resolver o problema.