[3] Números amigos - Nível de aprendizagem - [Desafios] Discussão - Portugal-a-Programar
By Warrior, February 4, 2008 in [Desafios] Discussão
Discussão sobre o problema 3.
http://www.portugal-a-programar.org/forum/index.php/topic,21890.0.htm
"nos digam quantos pares não ordenados e diferentes de números amigos existem. "
isto significa que (1,9) é diferente de (9,1) ?
Se são pares não ordenados, acho que (1,9) deveria ser igual a (9,1)..
Isso fez-me um pouco de confusão. Nesse caso dá para resolver isto em O( N ), se não me engano.
Eu tenho k sair do pc, vi as soluções apresentadas. A do pcaldeira assume que o limite dos numeros do input é 5000, mas isso não foi especificado. A do skin não conta pares distintos. Falha naquele caso do 1,9,9,1 acho eu (mas isso foi uma olhadela na diagonal).
PS: é possivel saber o limite máximo dos numeros do input?
A do pcaldeira assume que o limite dos numeros do input é 5000, mas isso não foi especificado.
Eu refiro-me ao valor dos números do input e não à quantidade. (talvez não tenha explicado bem :/)
Exactamente, ia agora mesmo dizer isso.
O pcaldeira assume que o tamanho de cada número é < 5000, mas só é dito que são no máximo 5000 números, coisas diferentes.
A do skin falha naquele caso (1,9), (9,1) (são de factos iguais, dava para perceber pelo segundo input) e também conta várias vezes repetidos.
Comecei a colocar restrições e compliquei um bocado demais, se calhar devia estar um patamar acima.
Já agora, a solução que pensei é O(N log N), se existir melhor estou interessado em ver.
Edit: Acho que com uma Trie dá mesmo O(N), mas tenho que pensar melhor, vou almoçar.
Hmm, então eu depois corrijo que agora tenho de almoçar para sair .
Eu fiz agora rápidamente uma solução com 20 linhas em O(N log N). Se soubessemos o limite do tamanho dos números era trivial passar para O( N ). Mesmo assim, com uma hash table consegue-se na mesma sem saber o tal limite.
O 5000 foi um número como podia ter sido outro qualquer, por acaso usei o mesmo para não ter que definir outra constante. Para inputs maiores, basta declarar o array seen[][] com outras dimensões (sim, eu sei que é bastante ineficiente a nível de memória, mas como o limite não foi especificado, não dei grande importância a isso).
Tiveste bem skin xD Brevemente posto aqui em vb.net
5 min e ja posto
Desafio: admitindo que sabes o limite máximo dos números, resolve o exercicio com tempo O(N).
Eu não vou postar já a minha proposta de solução. Acho que devia haver um periodo em que não se pode submeter, senão o pessoal é tentado a olhar para as soluções antes de pensar em resolver os problemas.
Gooden: a tua solução falha no segundo exemplo.
Ok, vou pensar nisso. Agora vou sair, mas quando voltar a casa tento uma solução mais rápida.
Mogers Solved
Pá, a minha solução está trivial e peca por contar duplamente com os pares. Mas uma solução simples para contar os pares certos é dividir o número de pares por 2... fora isso, ainda vou pensar numa solução que verifique e só faça o output dos pares únicos (x,y == y,x)
gooden: a tua solução não está na mesma? acho que continua a contar duplicados...
não... modifiquei a de c# que tava a dar erros
cm assim??? tas a dizer tipo (2,8) e (8,2)
Sim. O 2º exemplo ilustra isso. Experimentaste?
Há MUITAS soluções erradas neste desafio.
A do skin em PHP, (conta os pares vezes demais, pode por exemplo contar (1,9) várias vezes), as do gooden e JoaoRodrigues idem.
Postei agora a minha solução em Python, agradecia comentários
Parece-me correcto, não o mais eficiente possível mas isso já é outro pormenor, para o que era pedido no enunciado (limite de 5000) funciona perfeitamente.
Pois, eu sei disso. Reparei que há uma relação qualquer ali que eu não tou a descortinar... Dicas?
Assim que eu tiver um bocadinho de tempo vou resolver alguns dos problemas e já explico a solução. Se não tivesse 3 frequências esta semana..