11646. Olimpíadas

Olá meus amigos nerds! Vendo os problemas que nós já resolvemos aqui no blog, nesses seis meses, descobri que não tínhamos resolvido sequer um único problema de ordenação. E como ordenação é um dos temas mais importantes e úteis de computação resolvi fazer esse post para amenizar nossa falha.

Hoje vamos falar de olimpíadas, já que o problema 11646. Olimpíadas trata, justamente, disso. Nossa tarefa é, dada a informação dos países que receberam medalhas, gerar a classificação dos países na competição. Nesta tarefa, os países serão identificados por números inteiros. O melhor colocado deve ser o país que conseguiu o maior número de medalhas de ouro. Se houver empate entre países no número de medalhas de ouro, o melhor colocado entre esses é o país que conseguiu o maior número de medalhas de prata. Se houver empate também no número de medalhas de prata, o melhor colocado entre esses é o país que recebeu o maior número de medalhas de bronze. Se ainda assim houver empate entre dois países, o melhor classificado é o que tem o menor número de identificação.

Solução

Esse é um típico problema de ordenação, basta ordenar os países de acordo com a regra dada e pronto. O único cuidado que devemos ter é usar um algoritmo de ordenação rápido, isto é, um algoritmo com complexidade O(n*log n) para não recebermos um TLE.

Esse problema não teria graça nenhuma, caso não falássemos um pouco sobre os algoritmos de ordenação. Sendo assim decidi explicar um pouco sobre o Quicksort (principal e mais rápido algoritmo de ordenação para a maioria dos problemas de ordenação).

O Quicksort é um algoritmo de divisão e conquista. Sua estratégia consiste em rearranjar os elementos de modo que os elementos "menores" que um dado elemento, chamado pivô, precedam esse elemento, enquanto os elementos "maiores" que o pivô o sucedam. Em seguida o Quicksort ordena recursivamente as duas sublistas definidas pelo pivô e as extremidades do array.

De forma mais algorítmica:

1. Escolha um elemento da lista, denominado pivô;
2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Essa operação é denominada partição;
3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

O Quicksort é um algoritmo tão famoso que nós deveríamos, não só entende-lo, como também, ser capazes de implementá-lo. Se você nunca tentou implementar o Quicksort, eu o convidaria a tentar.

Uma boa referência, não só a respeito de ordenação, mas também de algoritmos e estruturas de dados de um modo geral é o livro do Cormem. Se você quer se aprofundar um pouco no assunto, eu recomendaria a leitura do capítulo 2 desse livro.

Implementação

Observe como o problema fica simples usando o sort da lib algorithm :)

Dica Nerd - A Arte do Debuging

Olá meus amigos nerds, gostaram do pequeno desafio de debugging que eu deixei em minha última postagem? Segue ai a solução:

Vocês provavelmente não tiveram dificuldades e não devem ter gastado mais do que 5 minutos para resolver o desafio. Mesmo assim, hoje vou deixar uma dica bastante útil a esse respeito. A Udacity tem um excelente curso sobre debugging (e o melhor, ele é gratuito). Eu mesmo já fiz o curso e achei que ele me foi muito útil. O curso  começa bem básico, mas vai aumentando sua profundidade chegando a falar de algumas técnicas avançadas de debugging como por exemplo o delta debugging. Se você tentou e teve dificuldade em resolver o desafio da última postagem, esse curso pode ser muito útil para você. O Udacity, se você não sabe, é uma plataforma de educação online que oferece cursos de qualidade em várias áreas do conhecimento. Vale a pena conferir!

1824. Monitorando a Amazônia

Olá meus amigos nerds, vocês acharam que essa semana não ia ter um probleminha? Se sim, se enganaram! Eu queria ter postado esse probleminha na quarta, mas vocês hão de convir comigo que seria uma pena perder os jogos dos dois melhores times do Brasil da atualidade... Deixando de papo furado, que a diversão comece!

Hoje vamos resolver o problema 1824. Monitorando a Amazônia, que nos pede para verificar se é possível enviar uma mensagem de uma estação de comunicação central para todas as outras estações de comunicação espalhadas pela amazônia. Sendo que, cada estação se comunica apenas com as duas estações mais próximas a ela.

Solução

Conceitualmente esse não é um problema difícil. Se pensarmos a rede de comunicação como sendo um grafo (direcionado), basta verificarmos se todos os vértices são alcançáveis, a partir do vértice que representa a estação central. Isso pode ser feito, facilmente, usando-se uma busca em profundidade. 

Note que, o problema pede apenas para verificar se é possível enviar uma mensagem a partir da estação central. Caso se pedisse para verificar a viabilidade da comunicação entre qualquer par de estações, o problema seria um pouco mais complexo. Nesse caso teríamos que verificar se o grafo possuía apenas um componente fortemente conectado, o que poderia ser feito usando-se o algoritmo de Tarjan.

O seguinte algoritmo resolve o problema

calcule a distância entre cada par de estações
Seja G um grafo onde os vértices representam as estações
para cada estação
    Sejam a e b as estações mais próximas a est
    adicione a aresta est -> a a G
    adicione a aresta est -> b a G
faça uma busca em profundidade a partir do vértice que representa a estação principal marcando todos os vertices visitados
if todos os vértices foram marcados
    print "All stations are reachable."
else
    print "There are stations that are unreachable."

Implementação

Observe que evitamos o uso de números de ponto flutuante trabalhando com o quadrado da distância. Em alguns problemas isso pode ser bem útil.

Observe ainda, que abrimos mão de alguma elegância no código em favor de não armazenar as distâncias entre cada par de estações. Sendo assim vou aproveitar e deixar um pequeno desafio para você: o código abaixo contém 2 bugs, quanto tempo você levaria para encontrá-los?

Obs: Caso você tenha dificuldade em encontrar os bugs use o diff :)

1747. Números de Dinostratus

Olá meus amigos nerds, hoje irei falar de um problema bastante divertido, principalmente se você gosta de coincidências arqueológicas.

Existe uma classe de números conhecidos como números de Dinostratus, que aparecem em várias ruínas antigas. No problema 1747. Números de Dinostratus, iremos aprender a identificar se um número é ou não é um número de Dinostratus.

Mais especificamente, um número n é um número de Dinostratus se existe uma matriz M de dimensão 3 x 3 formada por 9 inteiros distintos com a propriedade que para toda posição (i,j) com i=1,...,3 e j=1,...,3 da matriz o elemento mi,j é múltiplo dos seus vizinhos mi-1,j, mi-1,j-1 e mi,j-1 (quando existirem) e  m3,3 = n.

Um exemplo de um número de Dinostratus é 36 pois:

1   2   4

3   6   12

9   18  36

Solução

O exemplo acima nos dá uma pista de como resolver o problema. Observe que, todos os números dá matriz devem ser necessariamente formados por fatores primos de n (ex: m(3,3)=36 tem que ser múltiplo de  m(2,2)=6 que por sua vez deve ser múltiplo de m(2,1)=3 e m(1,2)=2). Observe ainda que:

|2^0 * 3^0 =1   |  2^1 * 3^0 =2   |  2^2 * 3^0 =4  |

|2^0 * 3^1 =3   |  2^1 * 3^1 =6   |  2^2 * 3^1 =12 |

|2^0 * 3^2 =9   |  2^1 * 3^2 =18  |  2^2 * 3^2 =36 |

Vamos então tentar a seguinte hipótese: a solução do problema depende de alguma propriedade relacionada ao número de fatores primos de n. Se isso é verdade então é possível classificar um número como sendo de Dinostratus baseado no número de fatores primos. 

Bem, já sabemos que se temos 2 fatores primos e ambos tem expoente igual a dois então n é um número de Dinostratus. Ex: 36 = 4 * 9 = 2^2 * 3^2  (observe que eu poderia trocar o 2 e o 3 por outros números e mesmo assim a propriedade da matriz formar um número de Dinostratus se manteria, experiente para ver)

O que eu vou fazer agora é estabelecer se n é um número de Dinostratus quando n tem 1, 2, 3, 4, 5 ... fatores distintos, farei isso através de exemplos.

n tem 1 fator distinto

ex: 256 = 2^8

1  2   4

8  32 128

16 64 256

Então o expoente do fator tem que ser >= 8

n tem 2 fatores 

do número 36 já sabemos que ambos os fatores tem que ter expoente mair ou igual a 2, por outro lado

96 = 32 * 3 = 2^5 * 3 também é um número de Dinostratus.

1  2  4

3 12 24

6 48 96

Então se um dos expoentes for maior ou igual a 5 n também será um número de Dinostratus.

n tem 3 fatores 

ex: 60 = 4 * 3 * 5 = 2^2 * 3 * 5 = 60

1  2  4

3  6  12

15 30 60

Então o expoente de pelo menos um fator tem que ser >= 2.

n tem 4 ou mais fatores

ex: 210 = 2 * 3 * 5 * 7

1  2  14

3  6  42

15 30 210

Então n sempre será um número de Dinostratus.

Do exposto acima retiramos o seguinte algoritmo

fatore n

if n tem 4 ou mais fatores responda sim

if n tem 3 fatores e um deles tem expoente maior que 1 responda sim

if n tem 2 fatores e um deles tem expoente maior que 4 responda sim

if n tem 2 fatores e ambos tem expoente maior que 1 responda sim

if n tem 1 fatores e um deles tem expoente maior que 7 responda sim

else responda não

Implementação

1737. Mesa da Sra Montagny!

Olá meus amigos nerds, enquanto alguém não inventar um remédio mágico para garganta inflamada (minha garganta agradeceria) vamos resolver mais problemas.

O problema de hoje é o 1737. Mesa da Sra Montagny! e nele vamos ajudar a sra Montagny a decidir se é possível dispor todos os seus convidados numa mesa de forma que cada convidado tenha todos os seus amigos no lado oposto da mesa.

Solução

Como não vejo a hora de me deitar para descansar vou resolver problema de forma bem rápida. O problema nos fornece as relações de amizade dos convidados, isso sugere fortemente que a utilização de grafos é uma boa ideia para o problema.

Para que seja possível dispor os convidados, não pode haver um convidado que possua amigos dos dois lados da mesa. Se pensarmos os lados da mesa como conjuntos de vértices, qual tipo de grafo tem essa propriedade? Grafos bipartidos. Então o problema nos pede para identificar se o grafo é bipartido. Caso o grafo formado pelas relações de amizade seja bipartido, a sra Montagny poderá dispor seus convidados na mesa, caso contrário não.

Identificar se um grafo é bipartido é fácil. Basta fazer uma busca em profundidade, marcando os vértices de um dos conjuntos de uma cor e os do outro conjunto com outra. Caso eu encontre um vértice que deveria ter uma cor mas ele tem outra então o grafo não é bipartido, caso contrário ele é.

P.S. prometo que semana que vem falo de um problema mais interessante, mas hoje minha garganta me pede para fazer outras coisas rsrs

Implementação

6291. Problem

Olá meus amigos nerds, vocês devem estar se perguntando o que eu estou fazendo aqui agora, já que eu já postei um problema hoje. É que eu vi um problema tão legal que eu não consegui me segurar.

O problema em questão é o seguinte 6291. Problem e o legal nele é que ele não tem enunciado! Você conseguira resolve-lo?

Solução

Olhe bem para a entrada e tente encontrar algum padrão. Dê uma de Mcgiver e improvise! Tenho certeza que você conseguirá matar a charada. Esse problema é tão divertido que eu vou esconder a solução para não perder a graça...

9002. Bingo!

Olá meus amigos nerds, ainda não é hoje que vou apresentar a vocês meu recomendador de problemas (quero melhorar o algoritmo de recomendação um pouco mais primeiro). Mesmo assim, hoje vou resolver um outro problema que foi recomendado por ele.

Hoje vamos brincar de bingo, já que é isso que o problema 9002. Bingo! nos pede. Albert, Charles e Mary (ACM rsrs) resolveram criar um novo tipo de bingo, nesse jogo são sorteadas, com reposição, duas bolas e o número sorteado é a diferença absoluta desses números. Como ACM não são bons de matemática eles nos pediram para verificar se dado um conjunto de bolas é possível se sortear todos os números.

Solução

Ao ler esse problema pensei que ele poderia ser interessante, mas ao olhar os limites da entrada fiquei decepicionado (n <= 90), ou seja, qualquer algoritmo de força bruta seria bom o suficiente.

Resolver esse problema usando força bruta é trivial. O seguinte algoritmo (com complexidade O(n^2)) faz isso:

para cada par (x, y) de bolas
    compute a diferença entre x e y
    armazene essa diferença

verifique se os números de 0 a N estão no conjunto das diferenças armazenadas

Implementação

Essa dica é meio trivial, mas vai lá assim mesmo: Observe como eu usei o vetor possiveisDiffs para armazenar todas as diferenças de modo mais eficiente.