819. Pedágio

Olá meus amigos nerds, hoje vamos ajudar Juquinha a decidir quais cidades ele pode visitar. Já que é isso que o problema 819. Pedágio nos pede para fazer. Mais especificamente, dado um mapa com as cidades e estradas, determinar quais cidades são alcançáveis a partir da cidade em que Juquinha se encontra e que o caminho até elas necessite que sejam pagos no máximo P pedágios.

Solução

O problema quase que implora por uma solução usando-se grafos, onde os vértices representam cidades e as arestas rodovias entre elas. Neste grafo o peso de uma aresta representa o custo do pedágio. Assim sendo o problema se reduz ao cálculo do caminho mínimo entre o vértice que representa a cidade onde Juquinha está e todos os outros vértices do grafo.

O caminho mínimo pode ser calculado facilmente usando-se o algoritmo de dijkstra. Hoje estou com pouco tempo, mas outro dia eu ainda quero discutir mais esse, que é um algoritmo muito clássico.

Assim sendo, para resolver o problema basta calcular o caminho mínimo e a resposta será o conjunto de cidades que estão a menos de P pedágios de distância.

P.S. como todos os pesos das arestas são iguais a 1 eu poderia ter simplesmente feito uma busca em largura para calcular a distância, mas resolvi usar dijkstra para deixar a explicação da solução mais simples :).

Implementação

P.S. Não reparem a feiura do código, mas é que eu resolvi esse problema faz muitos anos e fiquei com preguiça de deixar o código mais bonitinho. Pelo menos, observem que realmente melhoramos quando brincamos continuamente de resolver problemas kkk.

11651. Banda

Olá meus amigos nerds, esquentem seus motores, pois hoje começa o code jam 2015 e é claro que vocês não vão querer perder essa.  E para começar bem o dia, nada melhor do que resolvermos um probleminha, não é mesmo?

Hoje vamos ajudar o Jimmy a montar sua banda, já que é isso que o problema 11651. Banda nos pede para fazer. Mais expecificamente, dada uma lista de músicos e suas respectivas afinidades e deseja-se escolher três dentre esses músicos de modo a maximizar a afinidade deles.

Solução

O problema é bem simples. Podemos modelar os músicos como sendo vértices de um grafo, desse modo as arestas do grafo representariam a afinidade entre o par de músicos representados pelos vértices. Agora basta percorrermos esse grafo e encontrarmos a trinca de músicos com a maior soma das afinidades. O seguinte algoritmo faz isso:

maxScore = -1

for i in vertices_grafo

    for j in vertices_adjacentes[i]

        for k in vertices_adjacentes[j]

            score = afinidade[i][j] + afinidade[i][k] + afinidade[j][k]

            if score > maxScore

                maxScore = score

                trio = (i, j, k)

O algoritmo acima é O(n^3), onde n é o número de vértices, mas como a entrada é pequena esse algoritmo é suficiente para resolver o problema e passar no tempo.

Implementação

17384. Desfile dos Patos

Olá meus amigos nerds, depois de um bom hiato, devido a eu ter me mudado e ficado algum tempo sem internet :(, estamos de volta para resolver mais problemas.

Mas para compensar hoje vamos resolver um tipo de problema que eu gosto muito: um problema que a solução fácil, não é suficientemente boa, nos forçando a ir além e fazer melhor.

Hoje vamos verificar qual a cor que mais aparece durante um desfile de patos. Já que é isso que o problema 17384. Desfile dos Patos nos pede. Mais especificamente, dada uma fila de patos, em que cada pato tem uma plumagem de cor diferente, determinar qual é a cor majoritária dentre as cores da plumagem dos patos, isto é, a cor que aparece em mais da metade das plumagens.

Solução

Apesar da aparente simplicidade esse problema é bem difícil. Ele possuí um limite de tempo muito apertado, e isso faz com que algo que geralmente não é muito importante, quando tratamos de complexidade de algoritmos, se tornar relevante, as constantes.

Vocês já devem ter percebido que um simples mapa resolve o problema, isto é armazene contadores para cada cor e no final verifique qual cor majoritária. Se implementarmos o mapa como um hash, esse algoritmo é linear. Além disso, ele tem complexidade ótima, já que não é possível resolver esse problema sem analisar cada elemento da lista.

Entretanto o algoritmo acima não é eficiente o suficiente para resolvermos esse problema. Quem diria, um hash não é eficiente o suficiente para resolve-lo! Depois de muito pensar (e até achar que quem inseriu o problema cometeu algum equivoco no time limit), observamos que o problema tem uma característica especial, a cor mais frequente é majoritária, isso é ela tem mais aparições na lista que a soma de todas as outras cores. Isso nos permite abrir mão do hash e usar um único contador para verificar qual é a cor majoritária.

A ideia é a seguinte, se do número de aparições da cor majoritária subtrairmos o número de aparições de cada uma das outras cores, esse resultado é necessariamente maior que 0. Assim, podemos usar um algoritmo guloso para contar a diferença entre o número de aparições da cor majoritária para as outras cores. Podemos iniciar nossa contagem com qualquer cor, já que ao final necessariamente a cor majoritária tem elementos o suficiente para "cancelar" com cada um dos elementos das outras cores. O algoritmo abaixo vai verificando qual a cor majoritária até a 0-ésima posição do vetor, 1-ésima posição, ..., n-ésima, etc

corMajoritaria = 0
cnt = 0
for cor in corPatos
    if cnt == 0
       corMajoritaria = cor
    if cor == corMajoritaria
        cnt++
    else
        cnt--

O algorítmo acima é mais eficiente que um hash, pois não tem que pagar o custo de iterar sobre todos os elementos do hash ao final para verificar qual é o que tem o maior contador.

Implementação

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.