#4 Exercícios Aleatórios

Neste post vou comentar sobre os seguintes exercícios:

Gerar Números Aleatórios – Simulação
Jogo da Memória – Grafos, Lowest Common Ancestor

O segundo exercício estava disponível na Modalidade Programação, Nível 1, Fase 2 da OBI 2014.

Como de costume, eu recomendo que vocês tentem resolver o exercício acima antes de ler a solução abaixo. Assim suas teorias podem ser comparadas/contrastadas com as minhas, e isso pode ajudar no aprendizado.

Gerar Números Aleatórios – [uri]

Para gerar os números aleatórios basta aplicar a sequência de instruções dada no enunciado. Descobrir a “quantidade de números aleatórios gerados” é o mesmo que descobrir quantos números podem ser gerados até que um número gerado apareça duas vezes na sequência, formando um ciclo.

Para tratar os números repetidos, podemos declarar um vetor de booleanos que diz se um determinado número já apareceu na sequência ou não, e atualizá-lo ao decorrer do algoritmo.

Para gerar novos números, podemos dividir o processo em três partes:
(1) Elevar o número ao quadrado;
(2) Mover todos os dígitos duas posições à direita.
(3) Ignorar todos os dígitos com exceção dos quatro dígitos da direita (que eram os quatro dígitos centrais antes do passo 2).

O código final ficaria assim:

memset(visi, false, sizeof(visi)); // #include <string.h>
while(!visi[n]) {
    visi[n] = true;

    n *= n;      // (1)
    n /= 100;    // (2)
    n %= 10000;  // (3)

    cont++;
}

Jogo da Memória – [enunciado][juri]

Este exercício é um exemplo clássico do problema Lowest Common Ancestor (Menor Ancestral Comum) em grafos. Existem diversos algoritmos e reduções que podem ser aplicadas a esse tipo de problema, como vocês podem ler nesta página da [wikipédia] e neste artigo bem completo do [topcoder].

O motivo do uso deste algoritmo é o seguinte: precisamos calcular a distância entre dois nós N/2 vezes. O valor elevado de N e a quantidade de cálculos impossibilitam o uso de algoritmos tais como DFS, BFS, Floyd-Warshall, Dijkstra, entre outros.

O fato que ajuda na resolução deste exercício é que o grafo dado é uma árvore. Essa propridade é muito útil, e sabemos disso pois o enunciado nos diz:  “de modo que para qualquer par de cartas (A, B) existe uma e apenas uma sequência de cartas distintas que leva de A até B”.

O algoritmo de Lowest Common Ancestor nos diz qual o vértice C mais longe da raiz que faz parte do caminho entre os vértices A e B e a raiz. Estando dois vértices no mesmo caminho entre eles e a raiz é fácil calcular sua distância, e sabendo-se a distância entre A e C, e B e C, fica fácil calcular a distância entre A e B (nosso objetivo). Isso tudo pode ser calculado em tempo linear, como será descrito em seguida.

Eu vou mostrar duas abordagens aqui. Uma trivial que tem complexidade O(N*H), mas que leva TLE nos últimos casos de teste da OBI, e uma segunda abordagem não trivial com complexidade O(N*raiz(H)), e que recebe AC dentro do tempo limite em todos os casos de teste.

Construindo a árvore

O primeiro passo para se utilizar o algoritmo de LCA (Lowest Common Ancestor) é transformar nosso grafo em uma árvore explícita, declarando um nó como a raiz (escolheremos sempre o vértice 1, por simplicidade), encontrando o nível de profundidade de cada nó da árvore (sua distância até a raiz) e o pai de cada nó (o nó imediatamente acima deste). Visualmente o objetivo é fazer uma “transformação” do grafo da esquerda para a árvore da direita a seguir:

image1

image3

Podemos fazer isso com uma Depth First Search (Busca em Profundidade), que ficaria da seguinte maneira:

// main
monta_arvore(1, 1, 0);
...

// funcao
void monta_arvore(int u, int p, int l) {
    pai[u] = p;
    nivel[u] = l;

    for(int i=0; i<(int)adj[u].size(); i++) {
        int v = adj[u][i];

        if(!pai[v]) {
            monta_arvore(v, u, l+1);
        }
    }
}
Aplicando o LCA (trivial)

Dados dois nós A e B, precisamos descobrir qual o nó C que: (1) está no caminho entre os nós A e B e a raiz e; (2) está o mais longe da raiz. Por exemplo, no caso da imagem acima,
LCA(3, 7) = 2,
LCA(4, 7) = 7,
LCA(5, 8) = 6,
etc.

Dado que sabemos o pai de cada nó, podemos simular o caminho entre A e B até a raiz, e o momento em que esses caminhos se cruzarem será o momento em que encontramos o LCA.

Podemos também tirar vantagem do fato de que sabemos o nível de cada nó, e simular o caminho entre A e B até a raiz em uma velocidade que torne compatível que os dois se encontrem em uma intersecção. Eis o código:

int lca(int a, int b) {
    while(a != b) {
        if(nivel[a] > nivel[b]) {
            a = pai[a];
        } else {
            b = pai[b];
        }
    }
    return a;
}

No fim podemos concluir que a distância entre A e B é igual à distância entre A e C mais a distância entre B e C.

Eis uma imagem para exemplificar a execução do algoritmo quando chamado em lca(3, 7) = 2. Os números em verde significam a ordem em que a busca é executada:

image2

Eis o código trivial completo:
https://github.com/crbonilha/codes/blob/master/aleatorios/jogo_da_memoria_1.cpp

Aplicando o LCA (otimização)

Uma das maneiras de otimizar o algoritmo de LCA é pré-processar “segmentos” de caminhos. Seja H o nível mais alto da árvore (o nível da folha mais longe da raiz), iremos dividir nossa árvore em raiz(H) segmentos. Todos os nós de um dado segmento vão ter um ponteiro para o nó mais acima daquele segmento.

Essa divisão diminui o número de nós visitados em uma busca no algoritmo de LCA. Em vez de percorrer o caminho completo entre um dado nó e o seu destino, tal caminho vai ser reduzido pois em dados momentos ele vai “ignorar” segmentos que não são importantes para o resultado final.

Vamos pegar como exemplo novamente a árvore da imagem acima. O tamanho do segmento será igual a raiz(H), ou seja, raiz(5), que é igual a 2. Logo, teremos segmentos de tamanho 2 na árvore. Todos os nós agora terão um ponteiro para o primeiro nó acima deles que é múltiplo de 2, sem contar com ele mesmo. Vamos chamar esse ponteiro de super_pai. Idealmente esse vetor seria preenchido como se segue:

image5
image4

Para pré-processar esse vetor podemos implementar outra DFS, como a seguir:

// main
monta_super_pai(1, 1);
...

// funcao
void monta_super_pai(int u, int p) {
    super_pai[u] = p;

    if(nivel[u]%segmento == 0) {
        p = u;
    }

    for(int i=0; i<(int)adj[u].size(); i++) {
        int v = adj[u][i];

        if(!super_pai[v]) {
            monta_super_pai(v, p);
        }
    }
}

Em seguida modificamos o código de LCA para tirar vantagem do nosso novo vetor. O algoritmo agora dá “pulos” pelos segmentos até que os dois nós em questão estejam no mesmo segmento. A partir desse ponto, o trecho trivial é executado:

int lca_2(int a, int b) {
    while(super_pai[a] != super_pai[b]) {
        if(nivel[a] > nivel[b]) {
            a = super_pai[a];
        } else {
            b = super_pai[b];
        }
    }
    while(a != b) {
        if(nivel[a] > nivel[b]) {
            a = pai[a];
        } else {
            b = pai[b];
        }
    }
    return a;
}

Eis o código completo:
https://github.com/crbonilha/codes/blob/master/aleatorios/jogo_da_memoria_2.cpp

 

Qualquer dúvida, sugestão ou crítica, favor deixar um comentário abaixo 😉

9 ideias sobre “#4 Exercícios Aleatórios”

  1. Olá Cristhian,

    Será que você poderia dar umas dicas sobre o exercício ‘Letras’ da maratona regional desse ano?
    https://www.urionlinejudge.com.br/judge/pt/problems/view/1714

    Entradas e saídas aqui:
    http://maratona.ime.usp.br/vagas14.html

    Tentei fazer com DFS + backtracking e apesar de chegar na resposta correta, o tempo fica muito alto (já estava esperando por isso). Pensei em tentar fazer por BFS guardando o estado/distancia e percorrendo com base no que estiver mais próximo de chegar no fim. Será que o caminho é esse ou estou fazendo tudo errado? kkk.

    Obrigado.

    1. Você está no caminho certo: BFS com estado/distância.
      Mas em vez de calcular o estado conforme a BFS é executada eu optaria pela estratégia de definir um estado antes da BFS comecar. Esse estado agiria como um conjunto de “regras”, dizendo quais letras em quais cases podem ser visitados. Como há no máximo 10 letras, há no máximo 2^10 estados, que é um valor razoavelmente baixo.
      Depois de executar 2^10 BFS’s, imprima como resultado aquela que lhe traz a menor distância.

  2. Olá Cristhian,

    Obrigado pela resposta, vou tentar implementar. Só estou com dúvida agora em como representar o estado, visto que o mesmo é um ‘vetor’. Bitmask seria eficiente nesse caso? Nunca estudei esse método mas lembro de um exercício que você comenta sobre ele.

    1. Há, consegui fazer =)

      Demorei um pouco pra entender a ”forma” do problema mas consegui. Nossa, a sua dica deixou a solução muito mais simples do que eu estava pensando em fazer… acabei utilizando uns bitwises simples para verificar as adjacências em cada estado e antes de começar o BFS eu verifico se aquele estado é viável ( compatível com a ultima casa e com a primeira). Esse exercício me lembrou um pouco de outro chamado Babel (também é da maratona, cuja solução parece muito pior do que é na verdade).

      Obrigado pela dica!!

    1. Hum, boa pergunta. Esse exercício é meio difícil.
      Quando eu não faco idéia da solucão eu tento entrar em contato com o autor, pra pegar alguma dica. Por algum motivo o nome do autor não está exposto ali, mas quem sabe mandando um e-mail pro pessoal do URI você descubre.

  3. Ótimo texto Bonilha, estava a dias tentando resolver esse algoritmo usando uma DFS simples, mas sempre tomava TLE kkkk.
    O bom, que além de conseguir accepted, lá no URI, aprendi sobre o LCA, coisa que não conhecia !
    vlw 😀

  4. Bonilha eu nem sei como agradecer ! Você é incrivel ! Muito obrigado pela explicação tem me ajudado muito !!

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *