842. Torres de Hanói

Olá meus amigos nerds, vocês sabiam que há uma lenda que diz que quando alguém conseguir resolver o problema das torres de Hanói usando 64 discos o mundo acabará? Hoje, vamos descobrir se essa lenda é verdadeira ou não ao resolver o problema 842. Torres de Hanói.

O conhecido quebra-cabeça consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo. O problema consiste em passar todos os discos de um pino para outro qualquer, usando um dos pinos como auxiliar, de maneira que um disco maior nunca fique em cima de outro menor em nenhuma situação.

Na realidade esse problema não nos pede para resolver o desafio das torres de hanói, inclusive ele nos apresenta a solução do mesmo e nos pede para que computemos o número de operações necessárias para solucionar o quebra cabeça.

Hanoi(N, Orig, Dest, Temp)

   se N = 1 então

      mover o menor disco do pino Orig para o pino Dest;

   senão

      Hanoi(N-1, Orig, Temp, Dest);

      mover o N-ésimo menor disco do pino Orig para o pino Dest;

      Hanoi(N-1, Temp, Dest, Orig);

Solução

Do algorítimo acima tiramos a seguinte relação de recorrência:

Hanoi (N) = 2*Hanoi(N-1) + 1

Expandindo a recorrência mais um pouco temos:

Hanoi (N) = 2*(2*Hanoi(N-2) + 1) + 1 = 4*Hanoi(N-2) + 2+1 = 8*Hanoi(N-3) + 4 + 2 + 1

Observe que, após "resolvermos" a expressão acima i vezes ela poderia ser escrita da seguinte forma:

Hanoi(N) = 2^i * Hanoi (N - i) + [sum 2^(x - 1) para x de 1 a i]

quando i == N temos:

Hanoi(N) = 2^N * Hanoi (0) + [sum 2^(x - 1) para x de 1 a N]

Mas Hanoi(0) = 0 já que se não houver peças não precisamos mover nada. Por outro lado [sum 2^(x - 1) para x de 1 a N] = 2^(N-1) - 1. Logo:

Hanoi(N) = 2^(N-1)

É interessante notar, que há uma outra solução bem obvia para o problema: Implementar e instrumentar o algoritmo acima e contar o número de movimentos na força bruta. Como você pode ver, pela ordem de grandeza do número de operações, essa solução certamente seria muito ineficiente e receberia um TLE.

Só por curiosidade, a lenda é verdadeira, se alguém gastasse 1 segundo para mover um disco, 2^64  = 1.8446744e+19 segundos é muito mais tempo que a idade do universo.

Implementação

2844. Você pode dizer 11

Olá meus amigos nerds,  mais uma vez, vamos ver como coisas que aparentemente são fáceis podem se tornar um pouco mais difíceis quando estamos lidando com entradas de tamanho um pouco maior. Para isso, vamos resolver o problema 2844. Você pode dizer 11, que nos pede para verificar se um número é divisível por 11.

Solução

print x%11 == 0

Trivial. Infelizmente não é assim que funciona. A entrada pode conter números de até 1000 dígitos, enquanto um uint64_t tem mais ou menos 18 dígitos. Ai você se lembra, que tem a disposição a sua biblioteca de big int, vai lá copia e cola o código dela e tenta de novo e recebe, como resultado por não ter pensado bem a respeito, um belo de um TLE.

Lição dada é lição aprendida. Sempre tenha cuidado quando o problema envolver entradas grandes o suficiente, pois elas sempre podem trager surpresas.

Nesse momento, é hora de nos lembrarmos daqueles critérios de divisibilidade, que nos permitem saber se um número é divisível por outro sem a necessidade de fazer a conta. E para nossa sorte, o critério de divisibilidade por 11 não só existe, como também é linear no número de bits do número.

Um número é divisível por 11 caso a soma dos algarismos de ordem par menos a soma dos algarismos de ordem ímpar seja divisível por 11. A prova dessa regra é bem simples e envolve aritmética modular.

10 = 11 - 1 <=> 10 == -1 mod 11

qualquer número pode ser escrito como uma soma de potências de 10

 10^n*a_n + 10^(n-1)*a_(n-1) ... + 10*a_1 + a_0

ou tomando essa soma em mod 11

(-1)^n*a_n + (-1)^(n-1)*a_(n-1) ... + (-1)*a_1 + a_0 == 

- a_n + a_(n-1) - ... - a_1 + a_0 == soma dos dígitos pares - soma dos dígitos ímpares

Implementação

1831. f91

Olá meus amigos nerds, hoje vamos brincar de estudar uma função recursiva, já que é isso que o problema 1831. f91 nos pede. Mais especificamente o problema nos fornece uma função recursiva e pede que computemos o resultado.

Solução

Você deve estar se perguntando o que tem de interessante nesse problema. Sim, esse é um problema razoavelmente fácil, mesmo assim tem alguns detalhes legais que podemos explorar. O problema define a seguinte função:

• Se N ≤ 100, então f91 (N) = f91 (f91 (N + 11));
• Se N ≥ 101, então f91 (N) = N - 10

Obviamente se implementarmos essa função já temos o problema resolvido:

f91(n)
    if n > 100 return N-10
    else return f91(f91(N+11))

Agora vamos tentar ser um pouco mais espertos e deduzir analiticamente o resultado dessa recursão. É ai que essa função fica divertida, pois ela sempre retorna 91 para todos os números menores ou iguais a 101. Desenvolvendo a função temos:

f91(n) = f91(f91(n+11)) = f91(f91(f91(f91(n+2*11)))) = f91(f91(f91(f91(f91(f91(n+3*11)))))) =...

Observe que n+11, n+2*11, n+3*11 é uma sequência extritamente crescente. Em algum momento, o valor dessa sequência ultrapassara 100 mas será menor ou igual a 111 (estamos somando 11). Nesse momento começaremos a subitrarir 10 e somar 11 a esse número, ou seja, duas chamadas consecutivas dessa função terão o efeito de somar 1 ao número (que ainda será menor que 100), exemplo:

f91(99) = f91(f91(99+11) = f91(f91(110)) = f91(100)

Ou seja, por indução f91(n) = f91(n+1) para todo n <= 90. Mas:

f91(100) = f91(f91(111)) = f91(101) = 91

logo f91(n) = 91 para todo n>=90. Para n < 90 temos:

f91(n) = f91(f91(n+11)) = f91(...f91(n+i*11)...)

e como n+i*11 é maior que 90 (basta tomar um i suficientemente grande):

f91(n) = f91(f91(n+11)) = f91(...f91(X > 90)...) = f91(...f91(91)...)

aplicando o fato de que f91(91) = 91 recursivamente temos: f(n) = f91(91) = 91.

Implementação

Agora que já entendemos como funciona a função f91, fica um desafio meu! Como seria definida a função f92? E a função f100000000?

1353. Festa Junina

Olá meus amigos nerds, hoje vamos ajudar o diretor de uma escola a montar uma comissão para realização de sua tradicional festa junina, já que é isso que o problema 1353. Festa Junina nos pede para fazer.

Mais especificamente, dada uma lista de alunos e as relações de ódio entre eles (que triste rsrs), determinar qual é o número máximo de integrantes que a comissão da festa pode ter, se ela for formada pelos alunos da lista.

Solução

Esse é um problema bastante interessante. Uma solução baseada em testar todos os conjuntos de alunos possíveis é bem fácil de ser pensada, entretanto apresenta o problema de o número de partições de um conjunto ser exponencial (2^n). Tentemos então encontrar soluções melhores!

Vamos resolver esse problema usando uma modelagem por grafos. Cada vértice do grafo representa um aluno da lista. Existe uma aresta entre dois vértices, caso um dos alunos que aqueles vértices representam odeio o outro. Em outras palavras, esse grafo representa as relações de ódio entre os alunos. Observe que para uma comissão ser válida não podem haver arestas no grafo que liguem os membros da comissão, ou seja, as comissões válidas são os conjuntos independentes existentes no grafo. Logo o problema se resume a achar o conjunto independente máximo do grafo.

Achar o conjunto independente máximo é o problema dual de achar a clique máxima (um conjunto independente é uma clique (sub grafo completo) no grafo complementar). Mas por que eu estou falando isso? Se você já estudou um pouco de teoria de complexidade, você já deve ter ouvido falar que o problema da clique máxima é NP-completo. Sendo assim, estamos diante de um problema que a melhor solução que conhecemos tem complexidade exponencial.

Assim a ideia que mencionei no primeiro parágrafo apesar de ineficiente é ótima. Observando que o tamanho máximo da entrada é 20 mesmo uma solução assim é capaz de passar no tempo no spoj. O seguinte algoritmo implementa tal ideia:

construa o grafo de relações de odio entre os alunos
tamanhoMaximoGrupo = 0
para cada conjunto de alunos
   Seja S esse conjunto
   para cada a em S
     para cada b em S
        se existe a aresta a->b ou b->a no grafo
          conjunto invalido
   tamanhoMaximoGrupo = max(tamanhoMaximoGrupo, |S|)

Implementação

A solução abaixo utiliza um backtracking para implementar o algoritmo acima. Ela é basicamente, um algoritmo de enumeração de conjuntos.

Uma ideia um pouco mais elaborada é utilizar um bitset para representar os conjuntos. A implementação abaixo é baseada nisso. A ideia é iterar de 1 a 2^n e utilizando a representação binária do iterador como a representação do conjunto. Embora um pouco mais eficiente ela também é mais propícia a erros, já que operações com bits as vezes são traiçoeiras.

11009. O mar não está para peixe

Olá meus amigos nerds, hoje vamos ajudar nossos queridos amigos pescadores a saber qual é a área do mar que suas redes são capazes de cobrir. Já que é isso que o problema 11009. O mar não está para peixe nos pede.

Mais especificamente dadas as dimensões de cada rede e o local onde cada uma delas é jogada desejamos determinar a área do mar que essas redes cobrem.

Solução

Esse é um problema que considero interessante, já que o caso geral dele, que é calcular a área da sobreposição de figuras geométricas arbitrárias, é um problema bastante complexo. Entretanto o problema 11009 é fácil devido a duas restrições:

• As redes são retangulares
• As dimensões das redes são números inteiros

Assim, podemos tratar o mar como um grid, onde cada célula tem área 1. Após isso basta marcar as posições ocupadas pelas redes e depois contar quantos quadradinho de área 1 temos no grid. Essa abordagem tem custo quadrático, mas o tamanho da entrada é pequeno (100) isso é suficiente para que o problema seja aceito.

Implementação

1367. Proteja sua senha

Olá meus amigos nerds! Hoje vamos brincar de decodificar senhas, já que é isso que o problema 1367. Proteja sua senha nos pede para fazer. Mais especificamente, dada uma seqüência de associações entre letras e números, e várias seqüências de letras digitadas pelo cliente do banco para cada uma dessas associações, o problema é determinar qual é a senha do cliente.

Solução

Esse é um problema fácil. Para cada dígito que compõe a senha eu tenho algumas opções, se eu fizer a interseção de todos os conjuntos de opções eu encontro o dígito correto, já que o enunciado me garante que sempre será possível identificar a senha a partir da entrada dada. Uma forma fácil de fazer interseção de conjuntos é utilizando um bitset. Uma operação de and (&) entre dois bitsets faz justamente a interseção dos conjuntos que eles representam.

Implementação

3776. Árvore Genealógica

Olá meus amigos nerds, passado o ano novo é hora de retomarmos nossa rotina de resolver problemas. E para vocês não dizerem que sou um cara mau, irei começar o ano com um problema fácil, porém interessante.

Hoje vamos resolver o problema 3776. Árvore Genealógica, que nos pede para, dada uma árvore genealógica, dizer quem são os parentes mais distantes.

Primeiramente, gostaria de dizer que esse problema é muito semelhante ao 11011. Desafio cartográfico, que foi o primeiro problema resolvido nesse blog. Seria isso uma coincidência de inicio de ano?

Solução

O problema define o grau de parentesco da seguinte maneira:

grau(A, B) = 0, se A = B
grau(A, B) = 1 + min(grau(pai(A), B), grau(A, pai(B))), se A != B

A recursão acima, e o fato de se tratar de uma árvore genealógica, praticamente nos implora para que modelemos esse problema utilizando grafos, onde os vértices são as pessoas e as arestas são uma relação direta de parentesco. 

Se pensarmos bem, a recursão acima nos conta que os dois parentes mais distantes são aqueles que fazem parte das extremidades do diamêtro da árvore. Isso nos conduziria a uma solução muito semelhante a do problema 11011, ou seja duas buscas em profundidade, sendo a segunda feita a partir do vértice mais distante da raiz da primeira busca.

Entretanto, é interessante notar, que o tamanho máximo da entrada é pequeno (1000) o que nos faz pensar que uma solução um pouco menos elaborada (mais força bruta) seja suficiente para resolver o problema. Bem e qual seria essa solução? Hora, para cada par A, B de pessoas calcular seu grau de parentesco e imprimir aquelas que tem o maior grau. Algoritmicamente falando:

Seja pessoas o conjunto de todos os vértices da árvore

maiorGrau = 0

for A in pessoas

  for B in pessoas

    g = grau(A, B)

    maiorGrau = max(g, maiorGrau)

Onde grau(A,B) é descrito pela recursão citada no início do problema. Observe que no caso médio a complexidade de grau(a,b) é logarítmica (altura da árvore), sendo assim meu algoritmo de força bruta tem complexidade de O(n² * log(n)) sendo n o número de pessoas. E isso é bom o suficiente para resolver esse problema. 

Observe, que caso quiséssemos modelar o problema como o diâmetro do grafo, teríamos que tratar o fato de a entrada poder ser uma floresta de árvores (um grafo desconexo). Problema que não existe no caso de uma solução por força bruta. Isso mostra a importância de entendermos os compromissos entre simplicidade e viabilidade (em ralação aos limites de entrada) de nossas soluções.

Implementação

Observem, como eu represento a floresta de árvores como um vetor, armazenando apenas o antecessor de cada nó.

Observem, também, que mesmo minha implementação tendo uma complexidade O(n³) no pior caso, ela ainda assim é aceita no spoj.