Jolly Jumpers

URL

https://www.thehuxley.com/problem/103

Comentários

Primeira solução: Dicionários

Como este problema foi apresentado na seção de dicionário, vou apresentar primeiro uma solução utilizando essa estrutura.

Esse é um exemplo de problema que pode se tornar bem simples se você escolher uma estrutura de dados adequada. Nesse caso, optei por utilizar um map para resolver parte do problema em O(1) e problema todo em O(n). Ou seja, ainda na leitura da entrada já dá pra você desenhar a solução.

(ps.: em C++, esses tempos são diferentes, pois bisonhamente o map não é implementado como uma hashtable. Discuti mais sobre isso aqui.)

Precisamos de uma forma de computar as diferenças entre os valores da sequência, guardar essas diferenças, ter certeza que você não guardou diferenças repetidas, garantir que você só guardou as diferenças que importam e pronto .. problema solucionado :-)

Vamos por partes.

Para computar os valores das diferenças, você pode criar duas variáveis e ir a cada nova variável lida, você calcula a diferença com a anterior. Depois atualiza a anterior.

Uma vez com a diferença em mãos, precisamos guardá-la para verificar depois se preenchemos todo o conjunto de diferenças de 1 até n-1, como pede o problema. Minha primeira ideia foi usar um Set, pois essa estrutura não armazena valores repetidos. Porém, normalmente os Sets são implementados como árvores de busca binárias (em c++ isso é verdade). Assim, a inserção em um Set seria feita em O(log n), o que já é bom. Mas então pensei em usar um Map que faz a inserção e a busca em O(1) e também não permite valores repetidos. Assim, para cada valor da diferença, eu adiciono no Map tanto como chave e valor:

my_map[diff]=diff;

A lógica foi que se eu inserisse todas as diferenças nesse map, ao final, bastava saber o tamanho do map para ver quantas diferenças distintas eu tinha. Se esse valor fosse igual a n-1, então eu teria um jolly jumper.

Aí, lembrei de um detalhe. Se eu fizesse isso, diferenças maiores também iriam ser colocados no Map. Por exemplo:

3 1 7 3

Essa entrada, seria considerada um jolly, pois o map teria dois valores: 6 e 4. E o seu tamanho seria igual a n-1. Esse problema ocorreu porque inseri diferenças maiores ou iguais a n, o que de fato, não interessam ao problema. Assim, resolvi isso fazendo um if antes de adicionar ao map:

if (diff <n )

{

my_map[diff]=diff;

}

Pronto. Agora com o map preenchido, basta saber se ao final o seu tamanho é igual a n-1.

Tudo isso feito em O(n)

Segunda solução: bit array

Um array de bits é uma estrutura usada para representar elementos que possuem dois estados. Geralmente o 1 indica a presença e o 0 a ausência. Mais precisamente, segue a definição de bit array encontrada na wikipedia:

"A bit array is a mapping from some domain (almost always a range of integers) to values in the set {0, 1}. The values can be interpreted as dark/light, absent/present, locked/unlocked, valid/invalid, et cetera. The point is that there are only two possible values, so they can be stored in one bit. The array can be viewed as a subset of the domain (e.g. {0, 1, 2, ..., n−1}), where a 1 bit indicates a number in the set and a 0 bit a number not in the set. This set data structure uses about n/w words of space, where w is the number of bits in each machine word. Whether the least significant bit or the most significant bit indicates the smallest-index number is largely irrelevant, but the former tends to be preferred."

A implementação de um bit array, usa uma variável inteira para representar a quantidade de bits de um inteiro, geralmente 32. Ou seja, cada posição do seu array de inteiros é usada para guardar informações de 32 elementos, onda cada um pode ser 0 ou 1. Veja mais detalhes aqui: http://www.mathcs.emory.edu/~cheung/Courses/255/Syllabus/1-C-intro/bit-array.html

Mas no nosso Jolly Jumper, espaço não é problema. Então para simplificar a implementação, utilizei a ideia de um array de bits só que com um array de "short", onde cada elemento do array pode ser 0 ou 1.

A lógica foi a seguinte:

Se são dados n números e você precisa encontrar todas as diferenças entre 1 e n-1, então, a gente não pode perder nenhuma diferença, ou seja, se existir uma única diferença fora desse intervalo, então o máximo de diferenças válidas que poderíamos conseguir, seria n-2, o que já não tornaria a sequência jolly. A mesma coisa para o caso onde a gente encontre uma diferença que já aconteceu antes.

Então para guardar as diferenças que já aconteçeram, resolvi usar o bit array. Nesse caso, como o maior n é 3000. Criei um array de 3000 elementos, inicialmente todo vazio. Se a diferença entre 2 números for 5, por exemplo, eu seto a posição 5 do array pra 1. Assim, fica mais fácil saber se aquela diferença já apareceu antes.

Ler o primeiro número (prev)

Ler o segundo número (next)

Calcula a diferença (diff)

se a diferença for maior que n-1, então significa que não é Jolly

se a diferença já apareceu antes, então não é Jolly

Caso contrário, leia o próximo número

e continua

Se conseguir ler todos os números e passar nos testes acima, então é Jolly

:-)

Tente fazer a sua implementação assim. Se quiser, pode olhar a minha implementação lá no repositório: https://github.com/r0drigopaes/pa/blob/master/jolly_bitarray.cpp

De qualquer forma, fiz também a implementação usando um array de bits verdadeiro: https://github.com/r0drigopaes/pa/blob/master/jolly_bitarray_real.cpp