Problema C - Transmissão secreta

O Problema

Dada uma grelha de $L$ linhas por $C$ colunas contendo células vazias, obstáculos e torres de transmissão, assim como Q mudanças de custo de torres, determinar, para o estado da grelha após cada mudança, o custo mínimo de transmissão para a grelha completa.

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

Este problema tem várias componentes por isso vamos focar-nos em cada peça antes de resolver o puzzle completo.

A primeira observação a fazer é que, visto que os alcances de todas as torres são iguais, se uma certa torre consegue transmitir uma mensagem até uma segunda torre então a segunda torre também consegue chegar à primeira, pois isto significa que as duas torres estão a uma distância igual ou inferior a $D$. Adicionalmente, se considerarmos a transmissão em cadeia, se uma torre enviar uma mensagem que é transmitida e possivelmente retransmitida (numa transmissão em cadeia) até uma segunda torre, então a segunda torre também consegue chegar à primeira. Finalmente, podemos observar que se uma torre $A$ transmite uma mensagem (possivelmente retransmitida) que chega a uma torre $B$ e por sua vez a torre $B$ transmite uma mensagem (possivelmente retransmitida) que chega a uma torre $C$, então a torre $A$ também consegue chegar à torre $C$.

Isto significa que podemos dividir as torres em grupos onde todas as torres num grupo conseguem chegar umas às outras. Uma divisão deste tipo tem a propriedade que, por definição, basta uma torre desse grupo enviar uma mensagem para todas as outras torres receberem e a enviarem. Adicionalmente, como é garantido pelo enunciado que se todas as torres enviarem mensagens então a grelha toda é preenchida, então se escolhermos uma torre de cada grupo temos a garantia que cobrimos a grelha toda.

Aparentemente esta divisão não parece ajudar a resolver o problema, mas vamos corrigir isso. Vamos construir uma divisão em grupos que tem a propriedade de ser maximal, ou seja, grupos tal que se duas torres conseguem enviar mensagens que chegam uma à outra (possivelmente retransmitida) então as duas torres estão no mesmo grupo. A imagem seguinte mostra a divisão no caso de exemplo do enunciado, onde os grupos estão ilustrados pela cor vermelha e azul, assim como o caminho entre torres.

Porquê que isto nos ajuda? Se tivermos esta construção, então sabemos que temos obrigatoriamente de escolher uma torre por grupo, pois torres em diferentes grupos não conseguem enviar mensagens entre elas. Assim, só precisamos de escolher a torre de menor custo em cada grupo e podemos responder ao que é pedido no problema ao construir a lista de grupos após cada mudança e calcular a soma das torres de custo mínimo em cada grupo.

Só nos falta saber como construir estes grupos. Existem várias maneiras de o fazer: na prática o que queremos é um algoritmo que dada uma torre descubra todas as torres que podem receber uma mensagem da primeira torre. Uma forma de o fazer é através de um algoritmo recursivo que explora todas as posições da grelha, mantendo uma matriz de posições que já visitámos. Durante o processo, se encontrarmos torres no caminho então adicionamo-las ao grupo da torre inicial (podemos manter, por exemplo, uma lista de torres). Se repetirmos isto para todas as torres, tendo o cuidado de se já adicionámos uma torre a um grupo, não temos de fazer uma nova pesquisa para essa torre.

O código seguinte em C ilustra este algoritmo. Notem que não é um código completo (nem compilável), apenas ilustra o algoritmo de explorar torres descrito. Os nomes das variáveis tentam ser auto-descritivos e usamos os mesmos nomes para as variáveis do enunciado: $C, L, D$.

int visitados[C][L];
int ordem_visita = 0; // truque para nao ter que limpar a matriz de visitas
int ordem_grupo = 0; // usado para indexar grupos

void visitar(int posicao_x, int posicao_y, int movimento_restante, int grupo) {
  // garantir que estamos dentro da grelha
  if (posicao_x < 0 || posicao_x >= C || posicao_y < 0 || posicao_y >= L)
    return;

  // verificar que ainda nao visitamos esta posicao
  if (visitados[posicao_x][posicao_y] < ordem_visita)
    return;
  visitados[posicao_x][posicao_y] = ordem_visita;

  // verificar que nao estamos num obstaculo
  if (grelha[posicao_x][posicao_y] == '#')
    return;

  // se estivermos numa torre podemos avancar mais D passos e 
  if (grelha[posicao_x][posicao_y] == 'T') {
    movimento_restante = D;
    adicionar_ao_grupo(posicao_x, posicao_y, grupo);
  }

  // verificar que ainda podemos continuar a propagar a mensagem
  if (movimento_restante == 0)
    return;

  // visitar os pontos adjacentes
  visitar(posicao_x + 1, posicao_y, movimento_restante - 1, grupo);
  visitar(posicao_x - 1, posicao_y, movimento_restante - 1, grupo);
  visitar(posicao_x, posicao_y + 1, movimento_restante - 1, grupo);
  visitar(posicao_x, posicao_y - 1, movimento_restante - 1, grupo);
}

int main() {
  // Ler input

  for (int x = 0; x < C; x++)
    for (int y = 0; y < L; y++)
     visitados[x][y] = 0;

  for (int x = 0; x < C; x++)
    for (int y = 0; y < L; y++)
      // veriricar se e torre e se ainda não a visitamos/adicionamos a um grupo
      if (grelha[x][y] == 'T' && visitados[x][y] == 0) {
        ordem_visita++;
        visitar(x, y, D, ordem_grupo);
        ordem_grupo++;
      }

  // Calcular resto da resposta
}

Com este tipo de solução, construir um grupo é feito em tempo $O(L \cdot C)$. É importante notar que se não usarmos o truque de não limpar a matriz de visitados ou se fizermos uma pesquisa por cada torre (mesmo depois de encontrarmos o seu grupo) a complexidade do nosso tempo pode subir para $O((L \cdot C)^2)$.

No total, esta solução funciona em $O(LCQ)$, o que seria suficiente para 40 pontos.

Notação de grafos

Para quem conhece o conceito de grafos, uma forma diferente de pensar nos grupos de torres é considerar os grupos como componentes conexas num grafo onde duas torres tem uma aresta entre elas se tiverem dentro do alcance $D$ uma da outra.

Artigo: Componentes conexos

Este artigo contém uma introdução algoritmos simples para grafos, incluindo como calcular componentes conexos.

Solução Ótima

Para melhorar a nossa solução temos de arranjar uma forma melhor de calcular o custo ótimo após uma mudança. Reparem que quando uma torre muda o seu custo quase tudo se mantém igual, exceto (claro) o custo da torre que mudou. Em particular, a única decisão que pode mudar é a torre a escolher no grupo da torre que mudou de custo. Se mudamos o custo de uma torre e essa torre era a torre de custo mínimo no seu grupo, então podemos ter que escolher uma nova torre com custo menor.

Para fazer isto eficientemente, podemos usar uma estrutura de dados que permita inserir e remover (ou atualizar) elementos assim como determinar o elemento mínimo de forma eficiente. Há várias possibilidades para algo do género, como por exemplo uma árvore binária de pesquisa. Para quem usar C++ ou Java, não é necessário implementar uma de raíz, visto que ambas as linguagens incluem implementações eficientes de uma estrutura de dados com estas propriedades: set no caso de C++; TreeSet no caso de Java.

O seguinte artigo inclui mais informação sobre as estruturas de dados existentes em C++ e Java e como as usar.

Artigo: Implementações de estruturas de dados

Este artigo contém informação sobre implementações de estruturas de dados eficientes em C++ e Java.

Se quiserem antes aprender um pouco mais como funcionam as árvores binárias de pesquisa, as estruturas de dados implementadas em C++ e Java para resolver o problema mencionado, o próximo artigo pode ser útil.

Artigo: Árvores binárias de pesquisa

Este artigo contém uma introdução a árvores binárias de pesquisa.

Usando esta estrutura de dados, cada atualização é feita em tempo $O(\log(LC))$ (na verdade é tempo proporcional ao logaritmo do número de torres, mas este é no máximo $LC$).

No total, esta solução funciona em $O(LC + Q\log(LC))$, o que seria suficiente para 100 pontos.

Nota final

Apesar das ideias algoritmicas deste problema não serem muito difíceis (os tópicos de componentes conexas e árvores binárias de pesquisa são ambos introdutórios), o problema necessitava de bastante código e não era fácil de juntar todas as peças num código eficiente e correto. Por isso, o problema podia parecer um pouco mais difícil na prática do que a solução teórica indicava.