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.