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.

Pesquisa do Mestre Pardal - Um recomendador de problemas para o Spoj

Olá meus amigos nerds, para fechar esse ano com chave de ouro, hoje eu trago um grande presente de Natal para vocês.

Você, que resolve problemas de maratona freqüentemente, em algum momento já deve ter se aborrecido por tentar resolver problemas que são muito fáceis ou muito difíceis para o seu nível atual. 

Quando se está treinando para competições, o ideal é resolver problemas que estão um pouco acima do seu nível atual. Problemas muito fáceis não acrescentam quase nada, já os muito difíceis acabam te desmotivando um pouco. 

Infelizmente, no spoj, por exemplo, o único jeito de você saber se um problema está a sua altura é tentando resolve-lo. Assim, na busca por problemas interessantes, você acaba tendo que ler vários problemas inúteis, o que consome considerável tempo. 

Aplicações web que possuem grande quantidade de itens, sendo que apenas alguns poucos são do interesse do usuário (por exemplo o Netflix ou a Amazon) costumas possuir a funcionalidade de um sistema de recomendação para auxiliar o usuário. Pensando nisso e na espereça de contribuir com o aprendizado geral da nação de nerds cientistas da computação, eu decidi construir um recomendador de problemas para o spoj. Você que acompanha o blog regularmente já deve saber disso, já que eu já havia citado isso aqui. 

Hoje eu tenho o prazer de anunciar o Spojrec meu sistema de recomendação de problemas para o spoj.

Como funciona o Spojrec?

Depois de ter testado o recomendador de problemas, você curioso nerd cheio de sede por conhecimento deve estar se perguntando: mas como ele funciona?

Para matar um pouco da sua curiosidade. Vou falar um pouco dos dois algoritmos de recomendação que rodam por traz do spojrec.

O algoritmo de recomendação principal do spojrec usa a seguinte ideia:

a) Usuários de alto nível resolvem problemas difíceis

b) Problemas difíceis só são resolvidos por usuários de alto nível.

Como você deve ter observado, meu jovem padawan, a recorrência acima é circular, para achar os usuários de alto nível eu preciso saber quais são os problemas difíceis e para saber quais são os problemas difíceis eu preciso dos usuários de alto nível. Então como resolver esse problema?

Podemos pensar no problema, como um problema de grafos, onde os usuários e problemas formam um grafo bipartido. Nesse grafo uma aresta representaria uma tentativa acertada de solução e  os vértices seriam os problemas e usuários. Problemas apontados por muitos usuários fortes seriam problemas difíceis, inversamente usuários de alto nível seriam aqueles que conseguiram resolver problemas   difíceis. Como você pode observar a indagação anterior persiste, eu só descrevi o problema de uma forma mais algorítmica.

Mas o que eu ganho em descrever o problema dessa forma. A resposta está em um parente próximo do page rank (o famoso algoritmo responsável pelo surgimento do google). O Hits um algoritmo que é capaz de lidar com essa recorrência circular e atribuir pesos aos problemas e usuários. Em outras palavras, o algoritmo principal do spojrec é o uso do hits aplicado ao grafo descrito acima :)

Pensando também nos iniciantes o spojrec implementa um segundo algoritmo de recomendação, um pouco mais simples que o primeiro. A ideia desse algoritmo é resolver a recorrência acima de uma outra forma. Ele utiliza como medida da dificuldade de um problema o número de usuários que o resolveram corretamente. Na hora de recomendar ele seleciona os problemas mais próximos da média dos 10 problemas mais difíceis que o usuário já resolveu.

Se você ainda está curioso e quiser ver o código fonte, me mande uma mensagem ou deixe um comentário que eu ficarei feliz de compartilha-lo com você.

Bem espero que tenham gostado! Maratonistas usem e abusem dessa nova ferramenta que eu fiz com carinho para vocês! Um feliz Natal e próspero ano novo para todos!

11762. Poodle

E aqui estamos para resolver o segundo problema fácil do dia. E por sinal, um problema bem engraçado, já que ele é uma paródia do google.

O problema 11762. Poodle nos pede para escrever poodle com tantas letras O quantas são as páginas encontradas na busca de uma máquina de busca imaginária chamada poodle (qualquer semelhança é mera coincidência rsrsrs).

Solução

Calcule o número de páginas e imprima o poodle.

Implementação

2928. Ele está impedido

Olá meus amigos nerds, depois de um pequeno hiato estou aqui de volta para resolver mais problemas.

Hoje vamos resolver dois problemas fáceis. O primeiro deles é o problema 2928. Ele está impedido que nos pede para verificar se existe um jogador impedido, sendo que são dadas as posições dos atacantes e defensores.

Solução

Basta achar a posição do penúltimo defensor e comparar essa posição com a posição de cada atacante. Se o atacante estiver mais próximo da linha do gol que o penúltimo defensor ele está impedido.

Implementação