Comentario OBI 2023 – Terceira Fase – P1 – Problema “Dominó Nlogônico”

Comentário por Henrique Vianna

Conhecimento prévio necessário:

• Explorando a STL – Stack

Nesse exercicio, dada uma lista de $N$ dominós, deve-se computar para cada um quantos outros dominós ele derruba, seja diretamente ou indiretamente. Um dominó $i$ atinge um outro dominó $j$ de forma direta se, e somente se, $x[i] + h[i] \geq x[j]$.

Intuitivamente, faz sentido calcularmos as respostas para cada um dos dominós em ordem decrescente (de $N$ a $1$), uma vez que um dado dominó só pode afetar aqueles que estão para a sua direita. Para nos auxiliar nessa tarefa, faremos uso de uma stack chamada de ativos, que guardará os índices dos dominós ainda não derrubados. Ademais, seja $f[i]$ o número de dominós que o dominó $i$ derruba. Então, tendo já calculado $f[j]$ para $f[i] = 1 + \sum_{j \in ativos}f[j]$, se $x[i] + h[i] \geq x[j]$.

Perceba que se o dominó atual derrubar um dado dominó $j$ de ativos, então deve-se remover $j$ da stack. Ao acabarmos de processarmos o dominó $i$, devemos inseri-lo em ativos e avançar para o dominó $i - 1$. Perceba que, uma vez que inserimos e retiramos um dado dominó da nossa stack uma única vez, a complexidade de nosso algoritmo é $\mathcal{O}(N)$.  Ao final, basta imprimirmos $f[i]$ para $1 \leq i \leq N$.

Clique aqui para conferir o código.