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.

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

3830. Soma

Olá meus amigos nerds, como é costume, estou aqui hoje para resolver nosso problema da semana. Infelizmente, o problema que vamos resolver é muito fácil, mas como nosso objetivo é resolver todos os problemas do spoj isso não importa muito. Não é mesmo?

Hoje vamos somar números, já que é isso que o problemas 3830. Soma nos pede para fazer. Mais especificamente, esse problema nos pede que, dada uma lista de N inteiros, encontre a soma de todos eles.

Fácil não, um simples for resolve...

Vamos brincar um pouco mais?  Será que é possível resolver esse problema se a tecla + do seu computador estivesse estragada? Certamente que sim, e é o que eu vou mostrar agora.

Modelagem

O segredo para resolver esse problema é lembrar que soma e subtração podem ser feitas usando se operações lógicas. Vamos dividir o nosso problema de somar em dois problemas:

1. Somar sem considerar o vai 1
2. Calcular e somar o vai 1

Vamos tentar somar dois números de 1 bit sem considerar o vai 1. Sejam a e b esses números:

a     b     a+b sem vai 1
1     1              0
1     0              1
0     1              1
0     0              0

É possível perceber que o resultado a+b é igual a 1 quando ou exclusivamente a ou ou exclusivamente b forem 1. Assim a soma sem se considerar o vai 1 pode ser feita como a xor b.

Calcular o vai 1 pode ser feito da mesma forma:

a     b     vai 1
1     1       1
1     0       0
0     1       0
0     0       0

Ou seja o vai 1 pode ser representado como a and b.

Pronto agora é só somar o a+b sem vai 1 com o vai 1. Opa, mas voltamos ao mesmo problema de antes. Para contornar esse empecilho, podemos usar recursão, como feito no pseudocódigo abaixo.

soma_recursivo(a, b)
    if (b == 0) return a //condição de parada
    somaSemVai1 = a xor b
    vai1 = a and b
    vai1 = vai1<<1 //o vai 1 sempre deve ser somado ao próximo bit
    return soma_recursivo(somaSemVai1, vai1)

Implementação