PKU 1631 - Bridging signals

Autor da análise: AtolAtol

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1631

Resumo

Dada um sequência de n números, 1 <= n <= 40000, encontrar o tamanho de uma subsequência
crescente máxima.

Solução

A primeira idéia para este exercício, seria fazer um LCS entre a sequência dada, e uma sequência 1,2,…,n.
O problema é que o LCS consome tempo O($n^2$).

Bom, então temos pelo menos 3 maneiras de conseguir um algoritmo $n\log n$ :

  1. Algoritmo clássico de LIS (longest increasing subsequence). (110 ms).
  2. Árvore de intervalos. (330 ms).
  3. BIT. (110 ms).

Solução usando BIT

Na função read, basta pegar o máximo valor acumulado nos "filhos" :

int read(int x) {
    int r = 0;
    while(x > 0) { r = max(r, bit[x]);     x -= (x&-x); }
    return r;
}

Na função update, basta atualizar todos os "pais" com o valor devolvido pelo read + 1 :

void update(int x, int val) {
    while(x < M) { bit[x] = max(bit[x], val);    x += (x&-x);}
}

E pronto!

Solução usando árvore de intervalos

Inicializar a árvore com valores 0.
Agora, para cada elemento X da sequência, basta realizar uma busca pelo valor máximo
no intervalo (1,X-1).

Depois, dar um update na árvore com o valor máximo do intervalo + 1.

Isso significa que, para cada elemento que estamos tentando adicionar na nossa sequência cresente máxima,
nós pegamos a maior sequência crescente que termina em algum elemento menor do que X, e adicionamos X
à sequência, atualizando seu valor na árvore.

Solução usando o algoritmo clássico

O algoritmo clássico para esse problema é muito semelhante.
O algoritmo é guloso, como os outros, então, suponha que para os elementos lidos até então, temos
uma sequência cresente máxima (considerando apenas os valores já lidos) $a1, a2,...,a_k$.

Ao tentarmos inserir um novo valor X à nossa sequência, podemos simplestemte sobrescrever o valor
$a_i$ , onde $a_{i-1} < X$ , e $a_i > X$. ( Aqui entra o $log(n)$, usando busca binária. )
Caso $X > a_k$, podemos adicioná-lo ao fim da sequência.

Com isso, nossa sequência "deixa" de ser crescente, mas nos ajuda a fazê-la crescer ao passo que lemos o resto da
entrada, pois deixamos os valores da sequência sempre os menores possíveis.

Mas apesar de que a sequência $a1,...,ak$ tenha deixado de ser crescente ( pois na verdade só estamos nos importando
com o tamanho dela neste exercício), ela ainda está lá, e ainda vale a propriedade de ser crescente.
Pois ao sobrescrever um valor, estamos apenas tentando melhorar a sequência, mas caso não consigamos, é porque aquela era a melhor sequência mesmo.

Ficou meio estranho… esse algoritmo é simples, mas difícil de explicar assim…

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License