logo Homepage
+  NewbieContest
Username:
Password:
  Voir les messages
Pages: 1 [2] 3 4 ... 36
16  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 05 Avril 2017 à 18:20:10
Bien joué!!

Effectivement il fallait prendre le plus grand nombre de n lettres, nul besoin de se limiter aux chiffres 1 et 0.
La subtilité additionnelle était de trouver "ungogol" au lieu de "milleun".

Le mot de passe aurait donc été:
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

17  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 03 Avril 2017 à 19:07:00
Wahouuu! Bien joué Spaulding! and welcome back!

C'est la bonne idée mais je crois que tu as fait des fautes de frappe/calcul.

Sinon ta logique explique bien comment trouver 1001, mais ce n'est pas la bonne réponse .

Edit: Ah je crois avoir compris ce que tu as fait. C'est presque ça.

18  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 31 Mars 2017 à 00:35:22
Et que encore une fois, c'est très arbitraire comme règle.
19  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 29 Mars 2017 à 15:26:06
Le titre de l'épreuve aurait été "Un deux trois".
20  Général / Defouloir / Re : Algo du soir, Bonsoir ! le: 23 Mars 2017 à 04:42:06
Bien joué à vous trois! Alkanor a donné la bonne approche en premier, mais sans code, et on dirait que pixis avait trouvé avant mais sans finaliser proprement. Enfin bref... C’était bien ça!
Voici l’algo en question, avec une belle illustration:
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

Pour répondre à vos questions sur la complexité spatiale:

>>>> Edit : d'ailleurs par rapport à la complexité spatiale, est-ce qu'on considère que modifier le tableau initial (chaque case) génère une  complexité spatiale O(n) ou bien on reste en O(1) ? (dans le premier cas d'ailleurs le tri serait alors en O(n) spatialement)

Ça dépend: s’il est permis de modifier le tableau donné, vu que tu peux le trier sur place (e.g. quicksort), la complexité spatiale est O(1). Mais dans ce problème je crois qu’il est plus rigoureux de supposer que le tableau donné ne peux être modifié, auquel cas tu dois créer un autre tableau pour sauver la version triée: Ça donne donc une complexité O(N).

>>>> edit : Ah bah oui je peux le faire sans récursion et là c'est O(n) temps et 0(n) espace (sauf que je pense pas avoir compris la complexité espace, ya forcément besoin de O(n) pour une liste de longueur n non ?)

Non, la complexité de ton algo dépend de l’espace additionel que tu génères, le tableau donné ne compte pas. Si à chaque itération tu ne fais que sauver une variable, c’est O(1). Si par contre tu crées un tableau de N éléments, c’est O(N), mais il n’y en a pas besoin ici comme tu as bien vu.
Si O(N) espace était permis, je crois que la solution la plus évidente serait d’avoir un compteur pour chaque nombre qu’on lit, puis de passer à travers tous les compteurs et de voir lequel est le plus grand.
21  Général / Defouloir / Re : Algo du soir, Bonsoir ! le: 12 Mars 2017 à 23:43:44
Rien à voir avec la médiane d'ailleurs.
Cette question n'est vraiment pas si difficile, ça ne devrait pas prendre plus de quelques minutes.
22  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 08 Mars 2017 à 03:25:28
Bien tenté ! Mais je ne considère pas ça comme une alternative valable non plus, le choix des règles est complètement arbitraire, ainsi que la taille du bloc (4) qui est clairement là juste pour trouver le terme 101. Tu le montres toi-même en disant que tu aurais pu modifier les règles pour obtenir 1001.

Tu aurais aussi pu dire "une fois qu'on a un nombre pair de 1, le nombre suivant est 1337".

23  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 07 Mars 2017 à 14:45:35
J'ai bien dit "presque". J'avoue que la réponse de pixis n'est pas mal, ça m'apprendra à faire le malin. Cela dit ça ne répond pas au fait que la suite doit être infinie (ainsi que l'indice).

L'épreuve est loin d'être comparable aux meilleurs épreuves de NC, ça n'est qu'une suite logique après tout, il ne faut pas aller chercher trop loin. C'est d'ailleurs pour ça que je n'ai pas trop insisté pour qu'elle soit publiée. Je ne suis pas d'accord avec l'argument des logiques alternatives, mais je suis plus ou moins d'accord avec le fait qu'on ne veuille plus de suites. Cela dit elle est meilleur que la plupart de celles qui sont déjà là.
24  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 07 Mars 2017 à 01:03:39
Pas mal en effet! J'accepterais presque ça comme solution alternative.
Cela dit tu n'as pas utilisé l'indice. Alors oui techniquement tu n'as pas trouvé 1001, mais tu devrais pouvoir expliquer pourquoi l'indice est là.

Ah, et aurais-je oublié de préciser?: la suite est infinie. Au temps pour moi (/me hides).
25  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 06 Mars 2017 à 18:34:46
Avec quelle logique?
Il faudrait que la "solution alternative" tienne debout pour tous les éléments quand même, et sans considérer tous les premiers comme éléments d'initialisation arbitraire  .
26  Général / Defouloir / Re : Algo du soir, Bonsoir ! le: 06 Mars 2017 à 18:31:16
J'aime bien ton idée, mais on peut faire mieux: O(n) dans le pire des cas!
27  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 06 Mars 2017 à 04:30:44
Voici une épreuve de logique que j’ai proposée il y’a plus d’un an mais qui n’a pas été acceptée car ”trop de solutions alternatives possibles“, et car ”on ne veut plus de suites logiques". Et pourtant, je ne crois pas que les testeurs aient eux-même trouvé de solution alternative .

Si quelqu’un arrive à la résoudre et la trouve sympa, peut-être que ça convaincra les admins de la publier:

Trouvez le nombre suivant dans cette suite:
1, 10, 100, 1000, 101, ?, ...

Indice: La réponse n'est pas 1001.
28  Général / Defouloir / Re : Algo du soir, Bonsoir ! le: 05 Mars 2017 à 02:26:08
Un peu plus compliqué cette fois-ci: On cherche une fonction qui reçoit un array de nombres entiers positifs et retourne le nombre qu’on retrouve le plus de fois dans l’array, s’il y est au moins 50% du temps. Sinon on retourne -1.
Exemple:
input = [1, 5, 3, 2, 3, 10, 3, 3, 3]
output = 3
input = [1, 5, 3, 2, 3, 10, 3, 3, 4]
output = -1
La solution doit être en temps O(n) et espace O(1).
29  Général / Defouloir / Re : Re : Enigme du soir, Bonsoir ! le: 02 Mars 2017 à 12:49:42
Oui j'ai pris un raccourci, basé sur l’intuition (et quelques tests pour m'assurer que ça tenait debout). Je me doutais bien qu'une preuve plus rigoureuse serait reliée à Hamming.

Bravo donc à harvey pour avoir trouvé en premier! (au moins avec la même méthode que moi).
30  Général / Defouloir / Re : Enigme du soir, Bonsoir ! le: 02 Mars 2017 à 04:53:42
La réponse est 20.

Je vous encourage à continuer à chercher. Il n’y a pas besoin de maths avancées du tout!
Voici ma méthode pour les n00bs qui ne trouveront pas seuls:

 
On a q questions et un message de m bits (q=23, m=12 dans notre cas).
On pourra donc générer 2^m messages différents, ce qui n’est pas assez pour représenter toutes les 2^q réponses possibles tant que m<q (12<23).

Cela dit, si on est prêt à tolérer e erreurs, on pourra utiliser le même message pour couvrir plusieurs réponses d’un coup.
Pour e erreurs, chaque réponse est couverte par sum{i=0 à e}{C(q, i)} messages différents.
Par exemple, pour q=4, la réponse 0000 est couverte par:
e=0 -> 0000 (total=C(4,0)=1)
e=1 -> 0000 1000 0100 0010 0001 (total=1+C(4,1)=5)
e=2 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 (total=5+C(4,2)=11)
e=3 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 1110 1101 1011 0111 (total=11+C(4,3)=15)
e=4 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 1110 1101 1011 0111 1111 (total=15+C(4,4)=16)
On s’attend bien sûr à retrouver 2^4=16 pour le cas e=4 (peu importe le message de 4 bits, on n’aura pas plus de 4 erreurs).

Vu la symétrie du problème, il est clair que ces messages sont distribués équitablement à travers les 2^q réponses possibles.
Du coup, pour chaque nombre d'erreurs e, il nous suffit de multiplier le nombre ci-dessus par le nombre de messages que nous pouvons utiliser (2^m),
pour savoir combien de messages on couvrera. Si ce nombre atteint ou dépasse 2^q, on peut garantir le nombre d’erreurs correspondant.
En d'autres mots, on peut supporter e erreurs si l’inégalité suivante est satisfaite:
sum{i=0 à e}{C(q, i)} * 2^m >= 2^q

(Points bonus si quelqu’un arrive à écrire tout ça sous la forme e = ... au lieu d’utiliser une inégalité et de tester les “e” un par un).

Dans l’exemple ci-dessus:
e=0 -> on a besoin de m=4
e=1 -> on a besoin de m=2
e=2 -> on a besoin de m=1
e=3 -> on a besoin de m=0

On peut d’ailleurs confirmer l’exemple de harvey: q=7 e=1 -> m=4
Maintenant pour la question initialement posée, on trouve: q=23 m=12 -> e=3
q-e = 20 questions garanties.


#micdrop
Pages: 1 [2] 3 4 ... 36