Problème 5 : des tests rajoutés ?

Bonjour, Après avoir fini il y a quelques temps les 5 problèmes je reviens dessus afin d'y mettre quelques commentaires et les soumettre. Mais là ... Miracle ... mon code fonctionnel que j'avais soumis ne marche plus sur les 3 derniers tests ... Je ne vois pas comment expliquer cela, à part si les organisateurs ont rajouté des tests afin d'éviter les algos comme le mien (je n'ai pas hardcoder). En tout, si c'est le cas ça aurait été sympa de prévenir par un post sur le site... Sur ce bonsoir :P

Ah oui, désolé. Un post aurait été une bonne idée.

Les tests du problème 5 du QCM étaient résolus par des algorithmes gloutons mais incorrects. On attend une solution plus sophistiquée. Le 15 novembre j'ai rajouté des tests plus durs pour au moins filtrer les solutions les plus simplistes (produire des exemples difficiles semble être aussi difficile ici). Il n'y a aussi plus de tests de performance, vu les contraintes fortes sur la taille de l'entrée.

Désolé encore pour l'embêtement.

Oui en effet j'avais fait un algorithme glouton :P bon bah reste plus qu'à recherche une autre solution

On pourrait pas avoir un exemple d'entré qui ne marche pas avec l'algorithme glouton histoire de pouvoir debugger le programme ?

désolé du double post, mais je me demandais, les gens pris en demi finale reussissent tout les exercice généralement ? Si on peut pas utiliser d'algorithme glouton faut utiliser un algorithme de brute force ? qui testerais toutes les solutions possible ?

Pour les contres-exemples, considère que ça fait partie de l'exercice d'en trouver :-) On donnera bientôt une correction de l'épreuve, et il incluera probablement un tel exemple.

Le fait de donner une entrée (ou un ensemble quelconque d'entrées) pose un autre problème : selon le sens dans lequel on examine le graphe, ou autre détail d'implémentation, un programme pourrait donner la mauvaise réponse tandis qu'un autre donne la bonne réponse tout en étant aussi incorrect. On ne pourra vraisemblablement décrire les cas critiques que partiellement. De plus, avec assez d'heuristiques, il y aura toujours un programme incorrect qui passera pourtant tous les exemples donnés, voire les tests du juge en ligne, juste parce qu'on ne peut pas couvrir tous les cas particuliers.

Tu n'as pas besoin de résoudre tous les problèmes pour avoir une chance de passer en demi. On profite surtout du fait que cette première épreuve se déroule en ligne pour bien te faire chercher et réfléchir, sans pression.

Finalement, je dirai seulement que même si le juge en ligne les rejette, tes soumissions n'iront pas à la poubelle : on les corrigera nous-mêmes pour évaluer ton niveau.