UVa 10635

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

Prince and Princess (http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576)

Problema

Dado duas sequências de inteiros, $P$ e $Q$, encontrar a maior subsequência comum de ambos.

Observações

As sequências podem ter tamanho até $N^2$ (dimensão do tabuleiro). Cada inteiro também pode ir até $N^2$. Todos os inteiros de uma sequência são distintos.

Dicas

  • O problema de achar a maior subsequência comum é muito difundido na literatura. Se não viu, acesse: Longest Common Subsequence.
  • O algoritmo de LCS resolve este problema, porém não passa no tempo limite, já que é quadrático no tamanho das sequências, o que para o nosso caso é $O(N^4)$.
  • Já pensou que o fato das sequências serem constítuidas por inteiros distintos pode nos dar um algoritmo mais eficiênte para calcular LCS?

Solução

A solução fica oculta por padrão. Desencorajamos que você olhe a solução do problema antes de ter tentado.
O fato das sequências $P$ e $Q$ serem formadas por inteiros distintos nos possibilita resolver este problema usando LIS (maior subsequência crescente, ou como preferir, longest increasing subsequence). A maior subsequência comum entre $P$ e $Q$ só pode ser formada por elementos que estejam em $P$ e em $Q$, porém, deve-se respeitar a ordem em que estes elementos aparecem nas sequências. Para isso, podemos fazer uma transformação em $Q$ para $Q'$ utilizando $P$:
  • Se existe um $j$ tal que $q_i = p_j$, então $q'_i = j$. ($q_i \in Q$ e $p_j \in P$).
  • Caso contrário, $q'_i$ não existe em $Q'$.

Exemplo para aplicação com $P = \{1, 7, 5, 4, 8, 3, 9\}$ e $Q = \{1, 4, 3, 5, 6, 2, 8, 9\}$:

  • Como $q_1 = p_1$, então $Q' = \{1\}$.
  • $q_2 = p_4$, então $Q' = \{1, 4\}$.
  • $q_3 = p_6$, então $Q' = \{1, 4, 6\}$.
  • $q_4 = p_3$, então $Q' = \{1, 4, 6, 3\}$.
  • Não existe $p_j$ para $q_5$.
  • Também não existe para $q_6$.
  • $q_7 = p_5$, então $Q' = \{1, 4, 6, 3, 5\}$.
  • $q_8 = p_7$, então $Q' = \{1, 4, 6, 3, 5, 7\}$.

Essa transformação nos diz onde cada elemento de $Q$ aparece em $P$. Assim, uma subsequência crescente de $Q'$ é uma sequência que aparece tanto em $P$ quanto em $Q$, e a maior subsequência crescente é portanto a maior subsequência comum de ambos. No nosso caso de exemplo, uma LIS de $\{1, 4, 6, 3, 5, 7\}$ é $\{1, 4, 5, 7\}$ que é exatamente a subsequência $\{p_1, p_4, p_5, p_7\}=\{1, 4, 8, 9\}$ existente tanto em $P$ como em $Q$.

Implementação

As dicas de implementação ficam ocultas por padrão. Desencorajamos que você as olhe antes de ter tentado.
A implementação da LIS deve ser a que possui custo assintótico $O(n \log n)$ que para o nosso problema resulta em $O(N^2 \log N)$. Usar um std::set facilita a implementação. A transformação pode ser feita em tempo linear usando hash dos números (que são de $1$ a $N^2$).
Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas