#1 Exercícios Aleatórios

Vou fazer alguns comentários sobre como resolver alguns exercícios aleatórios, além dos que foram pedidos por alguns usuários na caixa de comentários do meu último post. Os exercícios são:

{soma+=i++} até N – Matemática.
Crianças em uma Grade – Programacão dinâmica.
Digitando no telefone celular – Trie.

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

{soma+=i++} até N – [uri]

Este exercício requer o conhecimento de algumas propriedades da teoria dos números, além de uma boa indução matemática para desvendá-los. O link abaixo mostra um texto (em inglês) explicando uma indução que leva a resolução do exercício:
http://mathpages.com/home/kmath107.htm

Para algumas pessoas (eu incluso) isso pode parecer meio avançado, então vou pular para a parte interessante: “O número de maneiras de se expressar N como uma soma de inteiros consecutivos é igual ao número de divisores ímpares de N”.

Temos agora um problema mais específico, encontrar o número de divisores ímpares. A solucão trivial, testando todos os possíveis divisores de N e checando se são ímpares não é viável, pois o limite para o valor de N é muito alto (0 ≤ N ≤ 9E14); logo, precisamos de uma solução mais eficiente.

Vasculhando um pouco eu descobri que existe uma fórmula para isto. Considere a fatoração prima de N:

N = (2 ^ a) * (p1 ^ b) * (p2 ^ c) * (p3 ^ d) * ...

onde pi são os fatores primos de N diferentes de 2. O número de divisores ímpares de N é igual a:

div_imp = (b+1) * (c+1) * (d+1) * ...

Por exemplo, seja N = 15, sua fatoração prima é 15 = (2^0) * (3^1) * (5^1), pois 15 = 3*5. Logo, b = 1 e c = 1, e o número de divisores ímpares é igual a (1+1)*(1+1) = 4, sendo eles 1, 3, 5 e 15.

Para resolver o exercício precisamos fazer a fatoração prima para descobrir os expoentes desta fatoração. O primeiro passo seria então computar os primos que podem fazer parte da fatoração de N. Como N <= 9E14, precisamos computar apenas os primos até a raiz deste limite, igual a 3E7. Segue um exemplo do algoritmo de crivo, um dos mais utilizados com este propósito em competições:
https://github.com/crbonilha/codes/blob/master/outros/crivo.cpp

Em seguida basta usar os primos computados para fatorar N, e aplicar a fórmula citada acima.

Crianças em uma grade – [uri]

Este exercício pode ser dividido em duas partes: (1) computar a string resultante do passeio das crianças; e (2) descobrir o menor número de remoções, de modo que as strings se tornem iguais.

A parte (1) é trivial, e requer apenas que o caminho percorrido seja simulado de acordo com as instruções. Deve ser dada atenção especial ao caso onde N ou M = 0, pois nesses casos a sequência de instruções não será dada. Eu levei alguns RTE por tentar ler essa string “fantasma”.

Após executar a parte (1) do algoritmo, teremos em mão duas strings A e B, de tamanho N+1 e M+1 respectivamente. Para simplificar, vamos denotar o tamanho das strings apenas como N e M, respectivamente. A tarefa de descobrir o menor número de remoções de forma a tornar as strings iguais é um exemplo clássico de programação dinâmica.

Vamos definir um estado da nossa programação dinâmica. Seja dp[i][j] o menor número de remoções necessárias para que a string A a partir da posicão i e a string B a partir da posicão j sejam iguais.

1. Se i = N e j = M, estamos considerando as strings vazias, logo elas são iguais, e dp[N][M] = 0.
2. Se i = N e j < M, estamos considerando a string A vazia, e a string B de tamanho M-j. Logo, para torná-las iguais, teríamos que remover todos os caracteres de B. Logo, dp[i][j] = M-j.
3. Se i < N e j = M, estamos considerando a string A de tamanho N-i, e a string B vazia. De modo semelhante ao caso acima, teríamos que remoer todos os caracteres de A. Logo, dp[i][j] = N-i.
4. Se i < N e j < M, temos que fazer a string A não-vazia a partir de i se tornar igual a string B não-vazia a partir de j.
4.1 Se os caracteres A[i] e B[j] são iguais, não precisamos removê-los. Logo, podemos recorrer ao estado dp[i+1][j+1].
4.2 Se os caracteres A[i] e B[j] forem diferentes, precisaremos remover um deles. Logo, podemos remover o caractere A[i] e recorrer ao caso dp[i+1][j], ou remover o caractere B[j] e recorrer ao caso dp[i][j+1].

O código abaixo resume os casos acima. O exercício em especial pede para dizermos quantos caracteres de cada string foi removido, então o código abaixo pode parecer um pouco mais confuso do que é:

typedef struct estado {
    int ra; // remocoes em A
    int rb; // remocoes em B
} estado;
estado dp[510][510];

for(int i=n; i>=0; i--) {
    for(int j=m; j>=0; j--) {
        if(i == n and j == m) { // 1.
            dp[i][j].ra = 0;
            dp[i][j].rb = 0;
        } else if(i == n) { // 2.
            dp[i][j].ra = 0;
            dp[i][j].rb = m-j;
        } else if(j == m) { // 3.
            dp[i][j].ra = n-i;
            dp[i][j].rb = 0;
        } else if(A[i] == B[j]) { // 4.1
            dp[i][j].ra = dp[i+1][j+1].ra;
            dp[i][j].rb = dp[i+1][j+1].rb;
        } else { // 4.2
            if(dp[i+1][j].ra+dp[i+1][j].rb <= dp[i][j+1].ra+dp[i][j+1].rb) {
                dp[i][j].ra = dp[i+1][j].ra+1;
                dp[i][j].rb = dp[i+1][j].rb;
            } else {
                dp[i][j].ra = dp[i][j+1].ra;
                dp[i][j].rb = dp[i][j+1].rb+1;
            }
        }
    }
}
 
printf("Case %d: %d %d\n", caso, dp[0][0].ra, dp[0][0].rb);

Digitando no telefone celular – [uri]

Existem algumas estruturas diferentes que resolvem este exercício, mas vou focar na mais simples (na minha opinião), a Trie, que é uma espécie de árvore com algumas propriedades diferentes. Por exemplo, os valores armazenados na Trie não estão necessariamente nos nós, mas sim nos caminhos que são possíveis de percorrer desde a raiz da Trie até as suas folhas. Esta estrutura é muito usada em algoritmos de armazenamento e manipulação de strings, como é o caso deste exercício.

O primeiro passo para resolver o exercício é construir uma Trie baseada nas strings dadas. O segundo passo é adicionar algumas informações extras dentro de cada nó para auxiliar na poda de caminhos. Note que, devido à natureza da estrutura Trie e a similaridade das strings dadas, alguns caminhos entre a raiz e as folhas vão ser compartilhadas por uma ou mais strings.

Se em um nó em particular U, apenas uma string compõe o caminho da raiz até U, as teclas que compõem o caminho entre U e a folha mais próxima vão ser auto-completadas pelo novo sistema do celular. Caso duas ou mais strings tenham composto o caminho entre a raiz até U, temos duas possibilidades: (1) o nó U tem apenas um filho, logo as duas ou mais strings que compõem este caminho tem esse próximo caractere em comum, e o sistema do celular vai completar este caractere automaticamente; (2) o nó U tem dois ou mais filhos, logo as duas ou mais strings que compõem este caminho tem os seus comprimentos restantes distintos, e o usuário precisará pressionar a tecla que leva à string desejada.

Minha proposta então é adicionar duas variáveis a cada nó da Trie: no_cont, e letra_cont. A variável no_cont representa o número de strings que “passaram” por um nó específico, e o letra_cont representa o número de filhos de tal nó.

Para chegar ao resultado final, montamos a nossa Trie com as variáveis citadas, e percorremos a Trie seguindo o caminho de cada string. Toda string deve ter seu primeiro caractere pressionado, então inicialmente incrementamos o valor da resposta final. Começando do nó que representa o primeiro caractere da string em questão, verificamos o valor de no_cont. Se no_cont = 1, então o sistema do celular vai auto-completar o resto da string, e paramos nossa busca. Caso contrário, continuaremos nossa busca. Ainda no nó atual, verificamos o valor de letra_cont. Se letra_cont = 1, então o sistema do celular vai auto-completar o próximo caractere. Caso contrário, precisaremos pressionar um caractere, e incrementamos o resultado final.

Ao final basta dividir o resultado final por N, e imprimir a resposta com duas casas decimais.

typedef struct No {
    No * filho[26];
    int no_cont, letra_cont;
} No;

No * no;
int total = 0, j;
for(int i=0; i<n; i++) {
    no = raiz -> filho[ s[i][0]-'a' ];
    total++;
    for(j=1; j<size[i] && no -> no_cont != 1; j++) {
        if(no -> cont_letra > 1) {
            total++;
        }
        no = no -> filho[ s[i][j]-'a' ];
    }
}
 
printf("%.2lf\n", (double)total/n);

 

Espero que as explicacões tenham ficado claras. Favor deixar comentários abaixo a respeito de sugestões, dúvidas e/ou pedidos de novos exercícios (não vou prometer resolvê-los, mas não custa nada tentar). Até mais 🙂

18 ideias sobre “#1 Exercícios Aleatórios”

  1. Uma solução mais simples para o problema “Crianças em uma Grade” seria exibir a diferença entre o tamanho da string e o tamanho da LCS encontrada, que seria justamente o número mínimo de caracteres a ser excluído em uma string para se tornar na LCS que é a maior subsequência comum entre as duas. Uma outra observação é para o limite do problema que nos permite o uso do algoritmo recursivo 🙂

    1. Muito bem lembrado! Eu não quis citar o LCS porque ele é justamente o contrário do que o exercício pede, e eu não quis confundir muito as coisas, mas ele de fato é mais simples de implementar nesse caso.
      Ao meu ver, a escolha entre o algoritmo iterativo e recursivo depende de dois fatores: programador e exercício. Primeiro, é sempre recomendado implementar da forma que seja mais intuitiva ao programador, de modo a evitar bugs. Segundo, as relacões entre os estados e a natureza de cada forma afeta o desempenho do algoritmo. Quando todos os estados são visitados eu recomendo usar o algoritmo iterativo, para evitar o custo adicional de tempo relacionado à recursão. Porém em alguns casos nem todos os estados precisam ou fazer parte da solucão, logo o algoritmo recursivo, que visita apenas os estados necessários, pode levar menos tempo. Obrigado pela sugestão 🙂

      1. Opa Bonilha, entendi perfeitamente! Quanto ao algoritmo recursivo que citei, esqueci de mencionar que da para ser implementado sem memoization, mas como você disse fica a critério do programador… vlws man

      2. O exercício Crianças em uma grade original do UVa tem casos de teste com N absurdos (visto que o exercício não diz o limite, você deduziu que seria algo menor que 510). Chuto que o N lá chega em torno de 20.000, nem fazendo LCS com espaço otimizado passa no tempo, precisa usar uma modificação no LCS para conseguir passar.

          1. Não havia reparado nos limites altos no UVa. De fato, a abordagem com DP é lenta aqui.

            Você poderia falar mais sobre essa modificacão no LCS?

          2. A solução que eu achei na internet armazena os índices de cada letra da maior string e faz busca binária com eles. Não cheguei a debugar o código ainda pra ver certinho como funciona mas ele é simples:

            http://pastebin.com/Pga4wqPv

            A solução passa com 1,9 segundos no UVa, é bem eficiente.

          3. Bacana. Pelo que eu pesquisei essa é uma técnica em que você converte um problema de LCS para LIS (entre linhas 3 e 7).

            Dependendo de algumas propriedades da string, o problema quando convertido para LIS pode ser resolvido em N * lg M. porém nesse caso essa propriedade não é válida.

            Resumindo, a complexidade desse código é O( N * M * lg M ), mas acho que nenhum caso de teste explora isso ao máximo, do contrário do algoritmo de LCS normal.

            Valew pela dica 🙂

  2. Valeu Cristian, eu até sabia dessa propriedade de como expressar um número como soma de números consecutivos , porém eu estava calculando primos até a metade do número limite aí dava TLE.

  3. obrigado parceiro, me ajudou bastante,. Principalmente na do celular, pois nunca tinha visto essa estrutura na vida ‘-‘. Porém estou recebendo 20% WA nela xD, vou ficar tentando aqui. vlws Bonilha.

    1. Passou aqui :D, tava tentando implementar usando matriz, mas bugava caso tivesse várias palavras com prefixo diferente com a mesma letra em uma posição específica no meio.
      Caso tenha tempo, poderia dar uma olhada nesses problemas como sugestão? 😀
      Junte dois Reinos
      https://www.urionlinejudge.com.br/judge/pt/problems/view/1499
      X-Mart
      https://www.urionlinejudge.com.br/judge/pt/problems/view/1348
      Set
      https://www.urionlinejudge.com.br/judge/pt/ranks/problem/1090/cpp

      Vlw parceiro o/

  4. Cristhian, será que você poderia me dar uma dica sobre como resolver esse exercício de grafos: https://www.urionlinejudge.com.br/judge/pt/problems/view/1711. Seria ele um dijkstra com estados?

    Uma outra coisa, no contest Sigma vc fez um exercício chamado Preso no Castelo. Bem interessante ele, infelizmente não consegui termina-lo a tempo mas gostaria de saber se a minha solução estaria no caminho certo:
    – Inicialmente todos os vértices tem cor cinza;
    – Faço um DFS no vértice inicial:
    http://pastebin.com/MKHGTr8h (depende[u] indica qual vértice depende de u)
    – Por fim verifico se todos os vértices estão pretos.

    Obrigado!!

    1. Opa!! acabei conseguindo o da minhoca, quebrei a cabeça por um bom tempo e acabou dando certo. Só estou curioso pra saber agora como teve um pessoal com um tempo tão baixo no ranking. O método que usei foi encontrar os tamanhos dos ciclos e depois fazer um dijkstra pra cada query. Tentei bastante fazer apenas com um DFS por query porém bateu sempre em WA 10% (conseguia dizer se era possível existir um caminho mas não garantir o menor).

      Tem que ser muito criativo pra fazer alguns exercícios da maratona.

    2. Olá André, perdão pela demora, eu não percebi esse comentário ;P

      Em relacão ao exercício do Castelo, eles ainda não estão disponíveis no URI, mas eu adicionei os casos de teste na página Problem Setter do meu blog ainda hoje. Dá uma checada lá 😉

      Confesso que não sei se sua solucão seria aceita. Eu usei uma BFS modificada.

      1. Obrigado Cristhian, deu certo meu DFS =)
        O único detalhe foi que eu tinha pensado que seria no máximo 1 chave em cada sala (tinha feito com vetor simples), troquei pra list e deu.

    1. O detalhe está naquele espaco em branco entre o ” (aspas) e o %c, na linha 12 (do WA).

      O scanf é meio chato de usar, e eu não vou saber te explicar certinho o porque do erro, mas é ali haha.

Deixe uma resposta

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