Je pense avoir une solution pour le problème 5 mais malheureusement je ne comprends pas du tout comment est évaluée la quantité de mémoire utilisée.
Premièrement, je ne comprends pas où se situe la limite. Pour le problème 4 par exemple on nous impose une limite de 20mo, sauf que... je suis passé avec 32mo. Mieux encore, sur le problème 1 la limite est à 1mo, mais je suis passé avec 7mio. Or je ne stocke rien, si ce n'est les inputs, donc j'en déduis que ces 7mio ne viennent pas de mon programme. Mais d'où viennent-ils ?! Sur le problème 1, vous ne semblez pas les prendre en compte pour évaluer la quantité de mémoire utilisée. Mais, 7mio en ne stockant rien, c'est beaucoup, surtout pour un prgm de 10 lignes. Revenons sur le pb4, certains instances passent avec 2mo, soit nettement moins que pour le problème 1, pourquoi ?! Si 7mio est le minimum, sans rien stocker, comment je peux tomber à 2mo ?!
Venons en au problème, sur le problème 5 je passe les 5 premières instances avec 4,5mo, mais sur la 6ème le test échoue car trop de mémoire est utilisée et il m'indique 914Kio, soit très loin de la limite. Soit, j'en déduis qu'il est incapable de donner la mémoire utilisée, mais qu'il s'arrête quand même. Sauf que le truc c'est que j'ai tout essayé pour prendre le moins de place possible. Je commence par prendre le graphe en input, puis je fais ce que j'ai à faire dessus, puis je le supprime en libérant la mémoire, puis enfin je prends les requêtes en les traitants une par une. Je ne peux pas prendre moins de mémoire, je ne fais que sauvegarder le graphe, en listes d'adjacences; et 5 autres tableaux d'entiers de taille n (typiquement le tableau signaux). Il m'est impossible de prendre moins de place, et le j'ai demandé au Garbage Collector de Caml de m'indiquer combien de mémoire il utilisait, et nous sommes très loin des 20mo. Je vois pas où est-ce que je prends trop de place. Alors j'ai essayé de changer de structures, quitte à sacrifier le temps j'ai essayé d'utiliser un type moins lourd pour mon graphe (Au lieu de d'ensemble d'entiers via Set.Make, n'utiliser que des simples List), et là surprise : je ne passe même plus le premier test pour faute de mémoire. Ça n'a plus aucun sens, pourquoi est-ce qu'en sacrifiant le temps pour la place, je prends encore plus de mémoire. Non seulement j'en prends plus, mais pas qu'un peu, puisqu'avant j'utilisais 4mio et maintenant je dépasse les 30 ?!
En bref, comment en utilisant uniquement 5 tableaux d'entiers de taille N, et un graphe en liste d'adjacence de N sommets et M arête (donc en utilisant N + 2*M case de mémoire), je ne passe pas ?! J'ai toujours laissé passer les calculs très bizarres de la mémoire (cf ce que j'ai dit sur le problème 1), mais là ça n'a plus aucun sens.
Dernière interrogation, pour éviter de me prendre toujours plus de pénalités (à -256 points...) je me suis mis à tester mon prgm pour la problème 5, dans le testeur du problème 4 (en changeant juste les inputs), et il m'indique au plus 17Mio dans la dernière version (celle où je sacrifie la complexité en temps avec des List et non des Set) et 22 si j'utilise des Set (ce qui est prévisible). Mais pourquoi sur le problème 5, c'est l'inverse ?! Est ce qu'avoir plus de calculs (moins bonne complexité en temps) demande plus de mémoire ?!
Êtes vous sûr d'avoir mis la "véritable" (cf ce que j'ai dit sur le pb1) limite de mémoire à 20Mo pour le problème 5 en Ocaml?
Bon courage et merci d'avance si vous réussissez à m'aider.