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.

3597. Par ou Ímpar

Olá meus amigos nerds, tenho boas notícias para hoje. Vocês se lembram que eu comentei aqui que eu estava implementando um recomendador de problemas, para facilitar a vida de quem usa o spoj. Pois é, essa semana consegui dar mais um pequeno passo e implementar alguns algoritmos mais simples para fazer isso. E nada melhor do que testar um algoritmo implementando outro, não é verdade? Assim o problema que vamos resolver hoje nos foi sugerido por um dos algoritmos de recomendação que implementei. Não vou falar do recomendador hoje, pois pretendo dissecar esse assunto mais a fundo nas próximas semanas.

O problema de hoje é o 3597. Par ou Ímpar e ele nos pede que ajudemos Joaõzinho e Maria a resolverem a confusão que eles fizeram em uma brincadeira de par ou ímpar. Eles jogaram muitas vezes par ou ímpar e anotaram os resultados em cartões. Em todos os jogos João escolheu ímpar (e, conseqüentemente, Maria escolheu par). Durante os jogos cada jogador escreveu nos cartões quantos dedos ele/ela mostrou, usando uma carta para cada jogo. O objetivo deles era ser capar de re-checar os resultados depois, procurando pelos cartões de cada jogo. Entretanto, no fim do jogo os cartões de cada jogador estavam fora de ordem o que impedia que eles contassem exatamente quantas partidas cada um ganhou.

Mais especificamente, o problema nos pede que dado o conjunto de números escritos nos cartões,  determinar o número mínimo de jogos que Maria certamente ganhou.

Solução

Observe que é impossível saber quantos jogos cada um ganhou exatamente. Entretanto, independente de quantos jogos cada um ganhou o seguinte invariante deve se manter:

jogos_ganhos_maria + jogos_ganhos_joao = n

onde n é o total de jogos disputados.

Como é muito difícil calcular diretamente o número mínimo de jogos que Maria ganhou, vou resolver o problema reverso: calcular qual é o máximo de jogos que João pode ganhar. Esse tipo de abordagem as vezes é bem útil, sendo aplicada em vários problemas de otmização.

Na situação que Maria ganha o mínimo de jogos possíveis, João necessariamente deve ganhar o maior número de jogos possíveis, assim:

min_jogos_ganhos_maria + max_jogos_ganhos_joao = n

ou

min_jogos_ganhos_maria  = n - max_jogos_ganhos_joao


Só um lembrete:
par + par = par
par + ímpar = impar
ímpar + par = impar
ímpar + ímpar = par

Maximizar o número de jogos ganhos é fácil. Lendo o lembrete acima, você provavelmente já matou ou problema. Basta pensar que cada vez que João colocou um número par, Maria colocou um ímpar, e vice versa. Assim:

max_jogos_ganhos_joao = max_casamentos(joao_par, maria_impar) + max_casamentos(joao_impar, maria_par)

max_casamentos(joao_par, maria_impar) é fácil de calcular, e é igual ao mínimo entre joao_par e maria_impar. Assim:

max_jogos_ganhos_joao = min(joao_par, maria_impar) + min(joao_impar, maria_par)

logo

min_jogos_ganhos_maria  = n - min(joao_par, maria_impar) - min(joao_impar, maria_par)

E essa é justamente a solução do problema.

Implementação

1745. Recuperação

Olá meus amigos nerds, hoje estou com preguiça então falarei de um problema fácil. Mentirinha, estou é fazendo um recomendador de problemas para o spoj, em breve falarei mais sobre ele. 

Por incrível que pareça existem dezenas de problemas fáceis no spoj. E o problema 1745. Recuperação é um deles. Nesse problema, é pedido que dado uma lista de inteiros se encontre um inteiro nessa lista tal que ele seja igual a soma dos outros inteiros que o antecedem na lista.

Solução

De forma mais formal queremos um número a[k] tal que:

a[k] = a[1] + a[2] + ... + a[k-1]

Então basta percorrer a lista e testar essa propriedade. É o que o algoritmo abaixo faz:

soma = 0
for cada elemento a[i] da lista
    if  a[i] == soma
        numeroPedido = a[i]
        break;
    soma += a[i]

Basta então imprimir numeroPedido

Implementação

Observe que  numeroPedido deve ser inicializado com um valor inválido (menor que a menor soma possível, ou maior que a maior soma possível), se você usar numeroPedido = -1 (eu fiz isso da primeira vez :P) você vai levar merecidamente um belo de um wrong answer.

2616. Caixeiro-Viajante B

Olá meus amigos nerds, mesmo estando com um pouco de calos nos olhos devido ao jogo de ontem da seleção, estou aqui hoje para resolver um probleminha com vocês.

Hoje vamos falar do problema 2616. Caixeiro-Viajante B que nos pede para traçar a rota de um caixeiro viajante de modo que ele gaste o mínimo possível com passagens de trem para visitar todos os seus clientes. Mais especificamente, o problema só nos pede o valor mínimo gasto com as passagens.

Solução

O primeiro ponto a destacar, é que esse não é o clássico problema do caixeiro viajante, tão estudado quando se fala em problemas NP. Ainda bem, já que isso facilita bastante as coisas.

Como em outros problemas que já resolvemos aqui, vamos pensar em uma modelagem usando grafos. Nesse problema isso é bem simples, as cidades seriam os vértices e as ferrovias as arestas.

O problema nos afirma que há apenas um caminho ligando cada par de cidades, então nosso grafo é, na realidade, uma árvore. Cada cidade em que há um cliente do caixeiro precisa ser visitada, isso significa que cada ferrovia que o caixeiro passar será usada 2 vezes (ida e volta).

A forma de minimizar o gasto com passagens é não percorrer uma ferrovia mais do que uma duas vez (ida e volta), já que há apenas 1 caminho entre qualquer par de cidades. Isso significa que, cada vez que o caixeiro chegar a uma "encruzilhada" que tem caminhos para mais do que uma cidade ele deve visitar a primeira delas, voltar até a encruzilhada e partir dali direto para a próxima cidade. Observe que o que acabei de descrever é simplesmente percorrer o grafo em uma busca em profundidade.

Problema resolvido? Não! Pode haver cidades que não possuem clientes do caixeiro e que não estão no caminho de outras cidades, ou seja, que não precisam ser visitadas, mas que provavelmente seriam contadas caso você fizesse uma busca em profundidade simples. Mas isso é simples de resolver. Para contornar esse pequeno detalhe basta fazer a busca em profundidade primeiro (enraizando a árvore pelo nó que representa a cidade inicial do caixeiro) e ir percorrendo os caminhos das cidades de destino para a raiz (ou seja, fazendo o caminho oposto), marcando as arestas para que elas não sejam contadas novamente.

Implementação