Problema B - A corrida

O Problema

Dado um conjunto de $N$ charcos e $Q$ posições iniciais onde o Nuno pode iniciar a sua corrida, determinar para cada posição inicial o comprimento total dos charcos que o Nuno tem de atravessar se iniciar a sua corrida daí.

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

É nos pedido que calculemos o comprimento de interseção de uma reta com um conjunto de retângulos. A própria ilustração do enunciado do problema parece indicar uma possível abordagem muito simples ao problema: desenhar todos os retângulos numa grelha. Visto que os retângulos têm todos coordenadas inteiras, é possível representar todos os retângulos numa grelha. Se $d_m$ for o valor da coordenada máxima possível de qualquer ponto de um retângulo, então podemos usar uma array de tamanho $d_m$ por $d_m$ para representar cada retângulo.

Se as coordenadas de um retângulo forem x1 y1 x2 y2 (como dado no input do problema), então o seguinte código preenche uma array grelha com as posições onde há parte de um retângulo:

for (int xi = x1; xi < x2; xi++)
  for (int yi = y1; yi < y2; yi++)
    grelha[yi][xi] = 1;

Como não há interseções entre retângulos (segundo o enunciado), basta nos marcar as posições que têm uma parte de um retângulo.

Agora, dada uma posição inicial $x_i$, basta percorrer todos os pontos com coordenada x igual a $x_i$ e verificar quais posições na array grelha estão preenchidas.

Como isto nos obriga a passar por todos os pares de coordenadas possíveis, a solução obriga a gastar espaço proporcional a $O(\max(x, y)^2)$ e tempo proporcional a $O(\max(x, y)^2 + Qy)$, visto que para cada posição inicial temos de iterar por todos os valores possíveis de $y$.

Esta seria uma solução $O(\max(x, y)^2 + Qy)$ que daria aproximadamente 20 pontos.

Solução Melhorada

Para melhorar a solução anterior, basta observar que não nos interessa passar por todas as coordenadas, apenas saber quais retângulos são intersetados por cada linha de um possível percurso da corrida.

Assim, para cada uma das $Q$ posições iniciais, basta percorrer todos os $N$ retângulos e calcular os que intersetam a linha da posição inicial. Se uma posição inicial tiver coordenada x $x_0$, um retângulo com coordenadas $x_1 y_1 x_2 y_2$ interseta a linha dessa posição inicial se $x_0 \geq x_1$ e $x_0 < x_2$.

Como nesta solução, para cada posição inicial, passamos por todos os retângulos, o tempo que ela demorará a correr será proporcional a $QN$.

Esta seria uma solução $O(QN)$ que daria aproximadamente 50 pontos.

Solução Intermédia

Com as duas soluções anteriores conseguimos resolver os primeiros dois grupos de casos de teste, por isso agora vamo-nos focar no terceiro grupo. Visto que o valor máximo da coordenada y de um retângulo é apenas 500, podemos usar este facto a nosso favor.

Visto que os retângulos não se intersetam, dada uma posição inicial qualquer, só podemos intersetar um retângulo por cada valor da coordenada y. Sendo assim, uma solução possível será, para cada coordenada y, guardar de alguma forma quais os valores de x que contêm algum retângulo. Depois, para cada posição inicial, teremos de iterar por cada y possível e verificar se existe algum retângulo que intersete essa posição.

Concretizando, o que podemos fazer é guardar uma lista de retângulos ordenada pela coordenada x por cada coordenada y. Isto é, teremos $y$ listas de retângulos ordenados pela coordenada x, sendo que um retângulo pertence à i-ésima lista se alguma parte dele intersetar a linha horizontal com coordenada y igual a i. Para gerar esta lista basta percorrer todos os retângulos e adicioná-los às listas a que pertencem. Depois ordenam-se todas as listas.

Para calcular a resposta de uma posição inicial $x_0$, basta percorrer todas as listas e encontrar o último retângulo com coordenada x menor que $x_0$. Este será o único que pode intersetar a linha com coordenada x igual a $x_0$. Para descobrir este retângulo, visto que temos uma lista ordenada, podemos aplicar uma pesquisa binária na lista.

Artigo: Pesquisa Binária

Neste artigo podem ver uma discussão sobre pesquisa binária, dos conceitos introdutórios até algumas aplicações mais avançadas.

Para gerar a lista precisamos de iterar por todos os $N$ retângulos e pelas suas coordenadas y assim como ordenar cada uma das $y$ listas. Como cada lista pode ter no máximo $N$ retângulos e ordená-las tem complexidade temporal de $O(N\log(N))$, temos uma complexidade temporal total de $O(Ny\log(N))$. Adicionalmente, para cada posição inicial temos de fazer uma pesquisa binária em cada uma das $y$ listas, o que corresponde a uma complexidade de $O(Qy\log(N))$.

Esta seria uma solução $O(Ny\log(N) + Qy\log(N))$ que daria aproximadamente 80 pontos.

Solução Ótima

Usando algumas das ideias da solução anterior, vamos agora descrever uma possível solução ótima para este problema.

É importante notar que, na prática, há no máximo $2N$ pontos "de interesse". Com isto queremos dizer que só há no máximo $2N$ respostas diferentes a posições iniciais. Isto porque, se entre duas posições possíveis $x_1$ e $x_2$ não há nenhum retângulo a começar ou a acabar (ou seja, não há nenhum limite de um retângulo, quer esquerdo quer direito), então a resposta tem de ser a mesma para as duas posições, pois a linha que representa cada uma das posições interseta exatamente os mesmos retângulos.

Sendo assim, vamos calcular a resposta para cada uma destas $2N$ posições usando uma técnica conhecida como sweep line. Primeiro que tudo, é importante notar que podemos olhar para cada retângulo neste problema como um intervalo, visto que como só estamos o caminho percorrido em cada posição inicial é uma linha vertical, se intersetarmos um certo ponto de um retângulo, vamos intersetar todos os pontos acima e a baixo desse ponto (ou seja, todos os que partilham a coordenada y). Assim, sempre que intersetamos um retângulo percorremos a altura completa desse retângulo e por isso basta-nos somar as alturas dos retângulos que são intersetados pela linha da posição inicial para obter a resposta. Podemos então converter cada retângulo num intervalo tendo como extremos os limites na coordenada x do retângulo e associamos-lhe um valor, a altura do retângulo que representa.

Com esta observação, vamos pensar apenas em intervalos e vamos preencher uma lista com $2N$ valores, um por cada extremo de um intervalo (é importante distinguir entre extremos esquerdos e direitos, como iremos ver). São estas posições que consideramos de interesse, ou seja, serão nestas posições que calcularemos a resposta. Para o fazer, primeiro ordenamos a lista de valores que preenchemos. Agora, percorremo-la do início para o fim e usamos a seguinte observação: se para o valor anterior a resposta era $C$ e o valor atual representa um extremo esquerdo de um intervalo de altura $h$, então a posição atual interseta mais um intervalo que a anterior, logo a resposta para esta posição é $C + h$; se para o valor anterior a resposta era $C$ e o valor atual representa um extremo direito de um intervalo de altura $h$, então a posição atual interseta menos um intervalo que a anterior, logo a resposta para esta posição é $C - h$. Com isto, podemos atualizar a resposta à medida que percorremos a lista de posições e vamos guardando a resposta para cada uma.

Nota que é preciso ter algum cuidado com certos casos, por exemplo, se existirem vários intervalos com o mesmo extremo (esquerdo ou direito). A solução é muito parecida, mas requer algum cuidado que deixamos para pensarem como resolver.

Finalmente, para respondermos ao que nos pede o problema, para cada posição inicial pedida temos de encontrar uma posição de interesse com a mesma resposta. Se tivermos as posições de interesse ordenadas, então basta-nos encontrar a posição de interesse de maior valor que é menor que o valor da posição inicial que queremos calcular. Como fizemos na solução anterior, aqui podemos ordenar as posições de interesse e fazer uma pesquisa binária para encontrar a posição que queremos. Como já calculámos a resposta para todas as posições de interesse, agora basta imprimir a resposta que calculámos anteriormente.

Nota que apesar de requerer algumas observações e aplicar algumas técnicas algorítmicas, a solução é muito simples e fácil de implementar (é preciso ter algum cuidado para não errar os detalhes das pesquisas binárias, para evitar erros, em C++ é possível usar funções da linguagem, nomeadamente as funções lower_bound e upper_bound, mas convém saber exatamente o que fazem antes das usar). De facto, a solução oficial em C++ tem menos de 60 linhas de código.

Para calcularmos a resposta para cada posição de interesse temos de ordenar a lista de posições, o que tem um custo temporal de $O(N\log(N))$. Para executar o sweep line basta percorrer a lista de posições, o que tem custo temporal de $O(N)$. Por fim, para calcular a resposta para cada posição inicial, temos de fazer apenas uma pesquisa binária com custo temporal de $O(\log(N))$, o que dá um custo total de $O(Q\log(N))$.

Esta seria uma solução $O(N\log(N) + Q\log(N))$ que daria os 100 pontos.

Soluções alternativas

Existem várias outras soluções possíveis para este problema. Por exemplo, algumas estruturas de dados permitem resolver este tipo de problemas de forma dinâmica. Por exemplo, imaginem que o problema nos dizia que enquanto o Nuno ia tentando posições iniciais, alguns charcos iam secando e outros novos iam aparecendo, ou seja, os retângulos que temos de considerar vão mudando.

A solução ótima que descrevemos não funciona nesta situação. Porém, estruturas de dados mais avançadas (e é importante realçar que são bastante mais avançadas do que a solução ótima descrita) como árvores de segmentos a duas dimensões ou árvores de intervalos. A aplicação destas estruturas de dados ao nosso problema não é direta, mas depois de se perceber bem o funcionamento de qualquer uma, não é difícil adaptá-las ao nosso problema.