PKU 1631 - Bridging signals

Autor da análise: Atol

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

gabrielrcp 06 Jun 2009 13:48

Nossa, nunca tinha pensado em usar a idéia da BIT pra calcular o máximo de intervalos do tipo [1, n], legal! :)

Eu implementei a idéia da árvore de intervalos durante a prova, mas passou MUITO emcima no tempo. Eu acho que devo ter feito alguma besteira, mas não consigo achar.
Vou posta-la, se alguém puder me fazer alguma crítica, eu agradeço. Eu estou especialmente desconfiado da função que devolve o máximo de um intervalo.

#define MAX 40010
 
struct no{
  int a, b;
  int v;
  struct no *e;
  struct no *d;
};
 
no *tree;
int conta_no;
no _nos[3*MAX];
 
no *novo()
{
  return &_nos[conta_no++];
}
 
void monta()
{
  no *at, *bt, *ct;
  conta_no = 0;
  queue<no *> Q;
  for(int i = 0; i < n; i++){
    at = novo();
    at->a = at->b = i;
    at->v = 0;
    at->e = at->d = NULL;
    Q.push(at);
  }
 
  while(1){
    at = Q.front(); Q.pop();
    if(Q.empty()){
      tree = at;
      return;
    }
    bt = Q.front(); Q.pop();
    ct = novo();
    ct->a = min(at->a, bt->a);
    ct->b = max(at->b, bt->b);
    ct->v = 0;
    ct->e = at;
    ct->d = bt;
    Q.push(ct);
  }
}
 
// devolve o maximo da arvore no intervalo [a, b]
int maximo(int a, int b, no *arv)
{
  if(arv == NULL)
    return 0;
  if(b < arv->a || a > arv->b)
    return 0;
  if(a <= arv->a && b >= arv->b)
    return arv->v;
 
  return max(maximo(a, b, arv->e), maximo(a, b, arv->d));
}
 
// insere o valor x no indice i de arv
void insere(int x, int i, no *arv)
{
  if(arv == NULL)
    return;
 
  if(arv->a <= i && i <= arv->b){
    arv->v = max(x, arv->v);
    insere(x, i, arv->e);
    insere(x, i, arv->d);
  }
}

Re:

Atol 06 Jun 2009 14:08

Humm… eu acho que a minha árvore ficou mais eficiente porque eu não passei nada além do essencial nas consultas e updates da árvore. Os paramêtros que se mantinham constantes, como 'início' e 'fim' na busca, eu guardava numa variável global antes da chamada. assim como o 'x' e o 'i' na sua função insere.

Talvez tenha sido só isso mesmo.

Re:

gabrielrcp 06 Jun 2009 14:24

Só perguntar que eu paro para pensar melhor, já achei a besteira.

O erro era na função que monta a árvore. Suponha que n=7. Eu começo montando folhas 0, 1, 2, 3, 4, 5, 6. Depois eu monto intervalos [0,1], [2,3], [4,5], aí vou fazer um intervalo [0, 6], depois um [2, 5] e por último o pai de todos sera [0,6] (de novo).

Quando percebi isso, acho até espantoso que tenha passado.

Acertei a função, montando a árvore de maneira recursiva mais normal, e agora passou em 300MS, bem melhor!

Valeu!

Last edited on 06 Jun 2009 14:25 by gabrielrcp Show more

Re:

raphael_ribas 06 Jun 2009 18:04

Interessante como a bit functiona nesse caso, os intervalos pedidos sempre são de 0 até alguma posição, certo?
Acho que vc poderia simplificar a árvore de intervalos para levar isso em conta e transforma a busca
em uma função iterativa. Talvez fique com o mesmo desempenho que a bit.
Bom, eu to começando a ver que a árvore de intervalos e BIT são basicamente a mesma coisa.
Você pode usar uma árvore de intervalos como se fosse uma BIT para guardar a soma dos intervalos.
Apropósito, a primeira vez que li sobre a BIT eu implementei de um jeito deferente que tinha mais
cara da árvpre de intervalos só que implicita no vetor. Eu fazia uma busca binária no vetor e usava o
"meio" como a raiz do intervalo em questão. Para quem tiver curiosidade aí segue o código.

#define MAX_ELEMENTS 100
int soma[MAX_ELEMENTS];
int bit_tam;

void init(int N) {
    bit_tam = N;
    memset(soma, 0, sizeof(soma[0])*bit_tam);
}

/* O(lg bit_tam) */
void add(int p, int amount) {
    int inicio=0, fim = bit_tam-1, meio;
    while(inicio <= fim) {
        meio = (inicio + fim) / 2;
        if(p <= meio) {
            soma[meio] += amount;
            fim = meio - 1;
        } else {
            inicio = meio + 1;
        }
    }
}

/* O(lg bit_tam)
 * soma do intervalo [0,p] */
int get(int p) {
    int inicio=0, fim = bit_tam-1, meio, ret = 0;
    while(inicio <= fim) {
        meio = (inicio + fim) / 2;
        if(p < meio) {
            fim = meio - 1;
        } else {
            ret += soma[meio];
            inicio = meio + 1;
        }
    }
    return ret;
}

/* O(lg bit_tam)
 * menor p tal que get(p)>=amount */
int find(int amount) {
    int inicio=0, fim = bit_tam-1, meio, ultimo = bit_tam-1;
    while(inicio <= fim) {
        meio = (inicio + fim) / 2;
        if(soma[meio] < amount) {
            amount -= soma[meio];
            inicio = meio + 1;
        } else {
            ultimo = meio;
            fim = meio - 1;
        }
    }
    return ultimo;
}

Patience Sorting

Marchetti 11 Jun 2009 05:23

Olha que negócio muito legal!!
Facílimo de implementar e bem eficiente =D.
lá vai o link:
http://en.wikipedia.org/wiki/Patience_sorting

Re: Patience Sorting

Marchetti 11 Jun 2009 05:25

Tenho a impressão agora que é a mesma coisa que o Atol disse… Mas ainda é bonitinho…

Re: Patience Sorting

Wanderley 11 Jun 2009 20:02

Olha este link:

http://www-stat.stanford.edu/~cgates/PERSI/papers/Longest.pdf