Classement des spammeurs

Oh mon Dieu, ce code.

Bon, sinon, vous avez vu le titre du sujet d'épreuve écrite de Louvain-la-Neuve ?

Non, lien ?

cf Archives Demi-finales 2012 ;)
http://www.prologin.org/archives/2012/demi-finales

Mille millions de mille sabords !
On tombe sur Sherlock Holmes !

@alex3er : J'avais pas vu ! You're doing it right

epsilon012: tu parles du sujet ou de mon classement? Faudrait peut-être que je réduise, surtout que rapport qualité/quantité, je ne dois pas être aussi bien classé :p

@alex3er :
Du classement. Mais, il n'y a pas à réduire, c'est un classement de spammeurs.

@Thomas_94 Quelle horreur ce code ! D'où est-ce que tu le sors ?

D'ailleurs le sujet philosophie est assez marrant, mais il est plus facile que Paris I, non ? (Le coup de Death Note était excellent, ça m'a rappelé la 4e dkoe).

Le sujet mrkrpxzkrmtfrz a l'air intéressant - ça part sur de la cryptographie à clef distribuée ! =)
Au passage, deux questions :

• Existe-t-il une solution en moins de O(nb) (n nombre de parchemins, b nombre de bits / parchemin) pour la question 4 ? (sachant que le nombre de bits est de 1000 maximum, b est donc négligeable)
• Est-ce que l'utilisation d'une classe bitset (style boost) était envisageable ? Parce que ça réduit un bon nombre de questions à néant. (et le stockage est parfaitement envisageable, pour 1000 bits / parchemin)

Deux petites remarques finalement, toujours sur ce sujet (que je n'ai pas eu l'honneur d'affronter - j'ai préférer me faire death noter ... mais la critique est un plaisir de grossier gourmet !) : En fait, à part l'union de N intervalles, qu'y a-t-il de complexe dans les questions 1-5 ? La question 7 mérite-t-elle presque autant de points que la 6 ?

Dans ce sujet, Thomas_94 envoie un lien vers un pastebin public contenant son sessid sur le site.

Qui date certainement et n'est probablement plus valide.

D'ailleurs, je me demande même pourquoi son script a besoin du sessid !

@Ekleog :
Avec un tableau cumulatif, c'est possible de faire un algo en O(n+b) pour trouver pour chaque bit combien de fois il a été dévoilé... Et après si tu utilise un arbre binaire min pour trouver (sur chaque intervalle) quel est le bit qui a été vu le moins grand nombre de fois... Ça doit faire un truc du genre O(n+b+nlogb)

Simon: Pas mal ... Mais ça reste un algorithme valide ? Parce que le bit vu le moins grand nombre de fois n'avance pas beaucoup pour déterminer si on peut retirer un parchemin.
Par ailleurs, quelle serait la complexité pour b parchemins chacun dévoilant un bit différent ? (je n'ai encore jamais utilisé d'arbre binaire min, même si j'en avais déjà entendu parler)

Pour les parchemins de 1000 bits, on peut considérer les bits dévoilés comme un intervalle.
Si je cherche quel est le bit qui a été le moins de fois dévoilé sur l'intervalle [debut;fin] le résultat sera forcement supérieur ou égal à 1.
Si c'est 1 le parchemin est essentiel, si c'est plus il existe un (ou plusieurs) autre(s) parchemin(s) qui recoupe(nt) le parchemin actuel.
Je fais ça n fois, s'il n'y a qu'un seul bit dévoilé par parchemin, la complexité ne devrait pas changer...
Pour l'arbre binaire je stocke pour chaque nœud le minimum entre la valeur du fils droit et celle du fils gauche.
Une requête sur un intervalle demande un nombre de calcul de l'ordre de grandeur de la hauteur de l'arbre soit log(b).

Je crois que j'ai compris comment construire l'arbre : en considérant (1, 5, 2, 2, 4) ça donne

1
2
3
4
5
6
7

1
|  
1       4
|\        
1   2   `-4
|\  \-\    
1 5 2 2 4

Mais, après, comment faire une requête sur [1;3] (donc sur (5, 2, 2)) ?

Avec une fonction récursive comme celle ci ;)

Fonction minimum (noeud, debut, fin)
| droite | gauche | Si [gauche;droite] inclus dans [debut;fin]
| | Retourner noeud.valeur
| Si [gauche;droite] inter [debut;fin] == ensemble vide
| | Retourner +INFINI
| Retourner min (minimum(noeud.fils_droit, debut, fin), minimum(noeud.fils_gauche, debut, fin))

D'accord, merci ! (d'ailleurs, rien n'est sur wikipedia, dommage ...)

C'est sympa de donner des solutions prémâchées...

Ouais... J'hésitais ;)