Problema B - Viagem Alternativa

Tipo de problema: Árvores/Simulação
Autor do Problema: Pedro Paredes (DCC/FCUP) e Pedro Ribeiro (DCC/FCUP)

Problema:
Dado o tamanho N do TIE Bus e um número de mudanças de passageiros Q, a tua tarefa é descobrir onde fica cada um dos passageiros que entra. Uma mudança é uma entrada de um passageiro para um lugar L, um número escolhido P e um sentido de procura s (o sentido procura representa o sentido para onde esse passageiro se desloca, para depois ou antes de L) ou uma saída do passageiro de um lugar L.

Restrições:
1 ≤ N ≤ 500 000       Número de Lugares
1 ≤ Q ≤ 500 000       Número de Mudanças
1 ≤ L, P ≤ N       Lugar de entrada ou de saída e número de lugares que cada passageiro se desloca

Solução base:
Este problema é um típico problema de simulação onde a solução base é efetivamente efetuar a simulação programaticamente. Assim, bastava implementar um algoritmo que para cada entrada, iterava por todos os lugares a partir de L (tendo atenção ao sentido) e contando o número de lugares ocupados, algo que pode ser feito guardando uma matriz do tamanho do Bus e marcando se cada lugar está ou não ocupado. Para uma saída basta marcar um lugar como ocupado nessa matriz.

A complexidade desta solução é igual ao número de movimentos vezes o número de lugares andados por movimento, como em teoria o número de lugares andado por movimento é no máximo N, esta solução tem uma complexidade de O(Q*N).

Ideia para melhorar:
Para melhorar a solução base é preciso reparar que é necessário arranjar uma estrutura que nos permita reter alguma informação para o cálculo de cada movimento. Notem que esta estrutura terá de resolver o problema do RSQ (Range Sum Query), que é o problema de dado um intervalo, dizer a soma de todos os elementos nesse intervalo, que aqui corresponde ao número de lugares desocupados (para os podermos contar). A complexidade de cálcular cada intervalo terá de ser inferior a O(N) (ou teriamos a mesma complexidade que a solução trivial). É também importante que esta estrutura seja dinâmica, pois após resolver cada intervalo é necessário inserir o novo passageiro no seu lugar, mas também porque é necessário retirar passageiros dos seus lugares (quando o movimento é de saida).

Assumindo que temos esta estrutura, podemos agora apenas primeiro considerar que a temos e resolver o resto do problema. O problema agora é reduzido a encontrar um intervalo de L a N (ou de 1 a L, dependendo do sentido, mas vamos assumir sem perda de generalidade o primeiro) cuja soma dos lugares desocupados seja exatamente P (ou então concluir que não existe). Primeiro podemos ver facilmente se não existem P lugares disponíveis, ou seja, que a resposta seria "Saiu": basta ver se a soma dos lugares desocupados entre L e N é menor que P. Se não for, então existe solução.

Assumindo que existe solução, encontrá-la também tem que ser feito em complexidade inferior a O(N). Podemos tirar partido da ordenação dos lugares, isto é, visto que o número de lugares desocupados nunca diminui, se fixarmos um limite do intervalo e aumentarmos o outro (que é uma maneira de dizer que é uma sequência ordenada). Isto significa que podemos usar a técnica de pesquisa binária na resposta que funcionará da seguinte maneira: consideramos um intervalo (que inicialmente é de L a N) com limites a e b = [a, b]. Consideramos o ponto médio do intervalo (onde: ponto médio = (a + b) / 2). Se no intervalo de a ao ponto médio o número de lugares desocupados é superor ou igual a P, então concluímos que a solução está ou no ponto médio ou antes do ponto médio, o que equivale a encontrar o P-ésimo lugar desocupado no intervalo [a, ponto médio]. Se no intervalo de a ao ponto médio o número de lugares desocupados é inferior a P, então concluimos que a solução está depois do ponto médio, logo isto equivale a encontrar o (P - val)-ésimo lugar (onde val é o número de lugares desocupados no intervalo de a ao ponto médio) no intervalo [ponto médio + 1, b]. Temos a resposta quando chegarmos a um intervalo onde a = b.

Notem que para o caso análogo é necessário mudar um bocadinho os intervalos, mas o método é o mesmo. Falta então a estrutura para resolver a RSQ.

Segment Trees:
Uma Segment Tree (ou "árvore de segmentos") é uma estrutura de dados que guarda um conjunto de dados em intervalos. A estrutura tem uma forma de árvore binária onde cada nó é uma metade do intervalo do seu pai. Assim, pode ser usada para retornar somas de intervalos de valores (como é necessário para o problema). Também permite alterar o valor de um certo elemento dinamicamente. Todas as operações têm complexidade O(lg(N)), que é evidentemente sublinear.

Fenwick Trees:
Uma Fenwick Tree (também chamada de Binary Indexed Tree) é uma estrutura de dados que permite guardar somas acumuladas de um conjunto de elementos (que corresponde ao problema do RSQ) e alterar valores de elementos, ao criar uma árvore que aproveita a forma binária (base 2) de cada número.

Buckets:
Talvez a alternativa mais simples de perceber, mas também a mais ineficiente e talvez mais difícil de implementar, são Buckets (ou "Baldes"). Este método corresponde a dividir o conjunto de elementos em vários conjuntos mais pequenos (chamados de "baldes"), normalmente de tamanho sqrt(N) onde se pre-calcula a sua soma. Assim, para saber a soma num intervalo basta percorrer apenas os baldes e nos limites (porque os extremos do intervalo ficam no meio de um balde cada um), pesquisar linearmente de cada extremo até ao primeiro balde. Alterar valores corresponde a alterar o valor do balde.

Solução Alternativa:
Era possível alterar o algoritmo descrito com pesquisa binária e aproveitar a estrutura da Segment Tree. A ideia era exatamente a mesma, mas utilizar a Segment Tree para dividir os intervalos. Assim, era possível inclusivé alterar logo o valor do lugar para ocupado (que é mais eficiente). Assim, esta solução, apesar de ter a mesma complexidade que a anterior, é ligeiramente mais eficiente em termos de implementação.

Em termos de complexidades finais, as soluções com árvores utilizam RSQ logaritmico (pesquisa e mudança de valores) e como a pesquisa binária também tem tempo logarítmico, a complexidade é de: O(Q*lg(N)^2). No caso de Buckets, como a pesquisa tem complexidade de raíz quadrada e a pesquisa binária mantém-se: O(Q*lg(N)*sqrt(N)).

Ligações interessantes: