Bravo bluepoint, en effet on avait pas remarqué que le problème consistait juste à trouver un élément du noyau d'une matrice. Désolé pour cette erreur ! On espère que les autres problèmes (à part Pokémon) sont de bons problèmes

N'hésitez surtout pas si vous avez des idées de problèmes. Toute la difficulté est de trouver des problèmes qui permettent d'obtenir une répartition des scores bien étalée, et en essayant de pas se gourrer comme ici ^^

Ils ont l'air de dire ici : http://math.stackexchange.com/questions/361046/minimum-distance-of-a-binary-linear-code que c'est difficile. Il faudrait rendre le problème amusant !

Sinon on a mis de côté les 2 problèmes où la solution optimale avait été trouvée, les scores ne comptant pas dans le classement.

Ah oui tu as raison ! Tu recommandes quels paramètres ?

Les gens vont perdre leurs scores du coup, j'espère qu'ils seront pas trop déçus.

:p ok je modifierai demain du coup, faudra qu'on en parle avec l'ami avec qui je crée le site

Bon, j'ai envoye mon papier. Peut etre que je vais regarder le probleme de l'image ce week end.

Super merci beaucoup c'est éclairant !

Une nouvelle version du problème est disponible ici : http://primers.xyz/6

n = 1000, k = 500, avec 300 interrupteurs indépendants

J'ai l'impression que c'est pas équivalent, mais ça a quand même l'air NP-dur non ?

En termes de codes linéaires ça revient à trouver un codeword de poids maximal, problème qui a l'air assez peu documenté.

C'est bien NP-complet ! (https://books.google.fr/books?id=s0RsCQAAQBAJ&pg=PA106&lpg=PA106&dq=codeword+of+maximal+weight&source=bl&ots=c1wBgVIldn&sig=1LAVVDilldHA6Hh2bijzhrwjI5w&hl=fr&sa=X&ved=0CDMQ6AEwAmoVChMIkq3zz6_JyAIVCJwaCh1TOgQA#v=onepage&q=codeword%20of%20maximal%20weight&f=false)

Ne pas changer l'énoncé est plus pratique :p et c'est moins perturbant pour tous ceux ayant déjà joué sur ce problème

[edit] Mmm quelqu'un a fait 1000...

Théoriquement il est très peu probable que le vecteur unitaire soit atteignable, et de même pour les vecteurs proches de celui-ci.

J'ai enlevé les 200 interrupteurs liés, pour ne garder qu'une famille libre de 300 interrupteurs, et on dirait que le problème est résolu.

Ça reste mystérieux pour moi, je ne comprends pas comment ajouter des interrupteurs liés peut rendre le problème plus facile. Il se peut que le problème vienne du code de génération de l'input, mais j'ai pourtant revérifié plusieurs fois !

Le plus simple pour generer des instances difficile est d'ecrire la reduction depuis un autre probleme et de choisir les reductions des instances qui sont connues pour etre difficile. (Ca serait encore mieux de prendre des problemes avec des "gap preserving reductions" pour aussi garder les prppriete sur les problemes d'optimization associes)

Si tu cherches des problemes rigolo, il y a aussi les problemes d'organisation de competition sportive qui peuvent etre rigolote (et qui sont ridiculement difficile).

bluepoint, le papier est sur des histoires d'evaluation de performance d'algo de graph sur GPU et cluster.

Ahah, je viens de faire ma premier soumission au probleme "art optimal". J'ai fait 84784 C'etait surtout pour verifier que je faisais mes IOs comme il faut.

whiteapplex, yep. Il faut bien tester tes IO a un moment donne! Je commence facil et on verra les trucs bizarre a faire.
Je ne vois pas bien quel genre de bornes inferieur on peut utiliser ici.

Tu as pris quel pseudo sur le siteweb?

bon, un petit coup de greedy et ca descend a 3350.

bon, j'ai travaille hier sur le probleme art optimal. Et punaise, ca devient difficile.

J'ai essayer des methodes constructives et je suis descendu a 3251. C'est un peu deprimant quand on voit que mon premier algo non naif faisait 35xx. Ca pourrait bien etre le moment de passer a des methodes plus bourines.
deux pistes:
-bruteforer les petites instances.
-des methodes d'optimisation locales.

Je m'en sort pas avec l'output à renvoyer, et pourtant quand je reconstruis ma sortie j'ai bien la même image qu'en entrée >.<

Si la solution n'est pas bonne, le site de soumission te donne les coordonne de 1 pixel qui n'est pas bien colorie. Tu as essayer de tracer ca ?

Donne un exemple de ta sortie pour voir.

oui, j'ai : l'image est mal peinte en 416,0
sauf que c'est écrit en dur "FILL,416,0,1" dans mon output et image[416][0] = "#" dans l'input
mais bon par contre je viens de remarquer que j'ai un bug :p

heu, non, 416,0 c'est vide. Tu as inverser les lignes et les colonnes je pense.

art oui je sens que c'est ça >.<
FILL,10,0,1 pour moi ça prenait la 11e ligne, 1er caractère (avec les indices qui commencent à 1)

double-post: effectivement c'était ça ! J'y ai passé l'après-midi mais ça m'a permit de développer un quad-tree basique en TDD (chose que je n'avais pas assez expérimenté) en python
Assez ludique la réponse du site, par contre j'ai du boulot, je commence à 18k instructions