ouais, quadtree, ca ne marche pas tres bien. ici...

ça faisait longtemps que je voulais explorer un truc ac les quadtree car il y a quelques applications sympa pour tout ce qui est 2D... par contre bof bof pour une solution optimale effectivement, je pense que c'est faisable de descendre à 10k avec des patterns mais je vois pas comment passer sous les 5k :o

mon premier run de quadtree etait vers 14000, j'ai laisse tombe une approche purement quadtree rapidement. Je fais un genre de truc hybride maintenant.

mon algo bloque à 2948, je vois qu'Ismael a pas dit son dernier mot il me rattrape petit à petit, il vient de passer la barre des 3000.

une petite astuce pour gagner quelques opérations d'entrée de jeu : boucher les trous de 1 pixels (diagonale pas prise en compte) et ajouter une commande erase en file d'attente. j'ai essayé de boucher les trous de n pixels mais il n'y a que 1 pixel qui est rentable.

Ah ben voila Ismael m'a gratté Il est temps de répliquer

C'est ce que je suis entrain de regarder. Mais tout les trous de 1 ne sont pas rentable je pense.

j'ai essayé les trous de 1 à 50 pixels et il n'y a que 1 qui fait gagner des opérations, à moins de développer un truc local peut-être...

nan, il y en a plusieurs, mais je ne sais pas comment il se combine.

un coup de postprocessing et me voila en 3eme place avec 3151

J'ai pose la question sur le site web aussi. Je ne vois pas de facon simple pour avoir une borne inf raisonnable.

Tcho, j'ai soumis ma solution pour Agar.IA.
1008, 8eme place (Thor3D)

Beaucoup d'effort par rapport à un simple greedy mais peu d'amélioration^^. Bon j'ai un algo à complexité linéaire, je suis content, et je peux maintenant chercher les paramètres optimaux...

Pour ceux que ça intéresse de visualiser la chose, voici une image du domaine + de la solution greedy (qui score 991) :

mmm, ca n'a pas l'air bien difficile ce Agar.IA, il faudrait que j'essaye.

mmm, ca n'a pas l'air bien difficile ce Agar.IA, il faudrait que j'essaye.

Je t'attend au tournant

bluepoint_, c'est souvent la base des algo d'approximation; c'est impressionant comment ca march ebien glouton.

Triple14, oui, il faut que je regarde les details. Mais j'avais plein de variantes pour TSP et VRP quand j'etais en DEA. Et la, ca n'a pas l'air tres different. Donc les memes approches devraient fonctionner.

Les acronymes à 3 lettres ne m'impressionnent pas^^
Non mais c'est vrai que ça ressemble énormément au TSP, et que du coup des algos "tout fait" sont peut-être facilement applicables, ce qui est dommage du point de vue du concours...

Les acronymes à 3 lettres ne m'impressionnent pas^^

Deosle, la force de l'habitude

Non mais c'est vrai que ça ressemble énormément au TSP, et que du coup des algos "tout fait" sont peut-être facilement applicables, ce qui est dommage du point de vue du concours...

Ces problemes ne sortent jamais vraiment de nul part. C'est pour ca que j'ai commence par "art optimal", c'est le seul qui ne me disait rien a priori. Les autres sont des problemes de pavages, des problemes de graphes biparti ou des problemes de clustering

Et en vrai, "art optimal" c'est de la compression d'image, C'est juste que perso, je n'avais jamais vraiment regarder. On vera ce que je ferai le week en prochain (probablement pas le temps de regarder avant)

art optimal, je ne sais pas bien. Ca ressemble a des problemes de compression d'image bitmap sous forme vectoriel.
Voici tes primiives vectoriel, trouve les primitives qui vont produire cette image bitmap. Et parceque le rendering coute cher, trouve le minimum de primitive.

Ismael a dit qu'il avait calculer le minimum snas effacement a 3095. J'aimerait bien savoir comment il a atteint cette conclusion. J'ai pas trouve d'argument clair a ca...

J'en suis à 3103 minimum sans effacement. Je vois comment descendre encore mais je suis pas convaincu que ça donne un optimum pour autant. Je vais tenter voir si ça donne 3095.

J'ai essayé des trucs plus poussés mais pour l'instant, comme le dit _bluepoint la méthode "barbare" fonctionne mieux en moins de temps c'est quand même étonnant.

whiteapplex : tu sais à quoi correspondent les couleurs ? Bêtement l'état du score ?

Ismael a peut-être raison, j'arrive aussi à 3095 au minimum sans erase sur art optimal, sans être certain que c'est le mieux qu'on puisse faire. Par contre après il m'éclate...

whiteapplex j'ai tenté aussi la prédiction sur plusieurs cellules, j'y suis pas arrivé mais c'est clairement une piste à creuser. sinon comme idée peut-être essayer de se diriger en priorité vers les zones à forte densité, et éviter de se retrouver dans une zone vide (une zone qu'on vient de vider en fait...).