Mon code est selon moi correct mais il prend trop de temps à être exécuté pour 7 tests sur 22 (les autres étant validés).
Comment puis-je optimiser mon programme ?
Merci d'avance ! 😀
Rien de tel que de faire du camping pour profiter de la nature. Cependant sur Algoréa, les moustiques sont particulièrement pénibles et il faut faire attention à l'endroit où l'on s'installe, si l'on ne veut pas être sans cesse piqué.
Vous disposez d'une carte sur laquelle est indiquée, pour chaque parcelle de terrain, si le nombre de moustiques est supportable ou non. Votre objectif est de trouver le plus grand camping carré évitant les zones à moustiques qu'il est possible de construire.
Limites de temps et de mémoire (C++)
Temps : 0,5 s sur une machine à 1 GHz.
Mémoire : 64 000 ko.
Contraintes
1 <= nbLignes, nbColonnes <= 350
Entrée
Sur la première ligne : deux entiers nbLignes et nbColonnes
Les nbLignes lignes suivantes comportent chacun nbColonnes entiers compris entre 0 et 1 séparés par des espaces. 0 signifie qu'il n'y a pas de moustiques et 1 qu'il y a des moustiques
Sortie
Un unique entier : la taille maximale du côté d'un carré ne comportant que des 0 et dont les bords sont parallèles aux axes.
Si ça peut t'inspirer, ce sujet a déjà été discuté en Python. C'est un problème d'algorithme, pas de codage. https://openclassrooms.com/forum/sujet/france-ioi-installation-du-camping#94244078
Le Tout est souvent plus grand que la somme de ses parties.
Il n'y a pas forcément d'erreur dans ton code. Je n'ai pas tout regardé mais tu devrais avoir 4 boucles imbriquées si je ne me trompe pas? C'est un algorithme de complexité en O(n^4) Bien sûr ce que je propose comme lien parle de Python. Mais je pense que les gens ont bien expliqué la marche à suivre. Tu devrais obtenir un algo de complexité en O(n^2), donc beaucoup plus rapide. Tu devrais pouvoir t'en tirer en ajoutant un tableau de dimension 2 x nbColonnes.
- Edité par PierrotLeFou 8 novembre 2021 à 19:25:35
Le Tout est souvent plus grand que la somme de ses parties.
Python utilise sans doute des fonctions, mais tu n'en auras pas besoin dans le cas présent en C++ Je ne sais pas si tu as compris l'algo du lien que j'ai donné. En gros, on parcours la grille une seule fois et on évalue une grille des maxima en ne tenant compte que de la ligne courante de celle-ci et la ligne précédente seulement. C'est pourquoi je disais que tu n'avais besoin que d'un tableau maxima[2][nbColonnes] Maintenant, si on ne parcours la grille qu'une fois, quelle est l'utilité de la placer dans un ttableau à deux dimensions? Est-ce plus rapide de faire 10000 std:cin suivi de 10000 accès au tableau ou 10000 fois un accès à std::cin suivi d'un accès à la grille? On n'est plus à l'époque des vieux disques où on devait réchauffer le moteur et déplacer les têtes de lecture ... Le flot d'entrée est déjà en grande partie en mémoire. Cela va réduire la mémoire de complexité O(nbLignes*nbColonnes) à O(2*nbColonnes) Tu auras accès à une simple variable plutôt qu'une position dans une grille. Et on peut s'arranger pour que le tableau des maxima soit à une seule dimension. Tout cela va accélérer le processus. Mais le gain le plus important, et de loin, est l'algorithme lui-même.
edit: Tu as inclus trop d'entêtes pour rien: #include <fstream> #include <vector> #include <cctype> #include <algorithm> #include <cmath> #include <string> Dans ce code, tu n'as besoin que de iostream Tu fais: using namespace std; Les experts n'aimeront pas cela. Écris plutôt des choses comme std::cin std::cout std::endl J'ai recodé en C++ l'algorithme que j'avais écrit moi-même en Python en utilisant un tableau (que j'ai appelé S) de dimensions 2 x nbColonnes J'ai fait comme suggéré, je ne place pas les éléments de la grille dans un tableau, mais dans une simple variable. J'évalue la position courante du tableau des maxima à peu près comme je le faisais en Python. Ce tableau est à une seule dimension. Tu n'aurais besoin que de 2*nbColonnes plus quelques variables.
- Edité par PierrotLeFou 9 novembre 2021 à 4:30:25
Le Tout est souvent plus grand que la somme de ses parties.
#include <iostream>
#include <fstream>
#include <vector>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int NbLignes, NbColonnes;
cin >> NbLignes >> NbColonnes;
int Camping[NbLignes][NbColonnes];
On peut écrire ça en C++ standard ? C'est un tableau dont la taille est inconnue à la compilation, je croyais qu'il n'y avait que C99 qui permettait de faire ça.
En C, on appelle ça des VLA pour Variable Length Array (et non Very Large Array telescope ...) J'ai été moi-même surpris que mon code fonctionne. Comme je l'ai dit, je n'ai pas besoin de tableau à deux dimensions pour la grille. Une variable simple suffit parce que je parcours la grille séquenciellement du début à la fin. Par contre, pour mon tableau des maxima, un std::vector devrait fonctionner. On peut utiliser std::resize pour le mettre à la bonne grandeur.
edit: Comment faire un tableau à deux dimensions avec std::vector ? Voici le test que j'ai fait, il faut agrandir toutes les entrées de la seconde dimension. Pas très commode. - #include <iostream> #include <vector> int main(void) { std::vector<std::vector<int>> grille; grille.resize(5); grille[0].resize(4); std::cout << grille.size() << std::endl; // Donne 5 std::cout << grille[0].size() << std::endl; // Donne 4 std::cout << grille[1].size() << std::endl; // Donne 0 }
edit2: J'ai trouvé un meilleur truc: grille.resize(5, std::vector<int>(4));
- Edité par PierrotLeFou 10 novembre 2021 à 3:23:40
Le Tout est souvent plus grand que la somme de ses parties.
Il semble que Cyril a été dévoré par les moustiques ... Voici ma version. Elle fonctionne avec les deux exemples du début. La complexité en temps devrait être O(nbLignes*nbColonnes) La complexité en mémoire est O(2*nbColonnes) Je me suis inspiré du code Python que j'ai écrit et des suggestions de White Crow et PascalOrtiz. On ne fait pas forcément l'optimisation en C++ comme on le fait en Python. Comme je l'ai dit, je n'utilise pas de tableau pour la grille. - // Installation du camping. #include <iostream> #include <vector> int main(void) { int nbLignes, nbColonnes; std::cin >> nbLignes >> nbColonnes; int cote = 0; // Grandeur maximum d'un côté. if(nbLignes <= 0 || nbColonnes <= 0) { std::cout << cote << std::endl; return 0; } std::vector<int> maxima; maxima.resize(2*nbColonnes); int grille; // Chaque élément de la grille. // Lire la première ligne. for(int j = 0; j < nbColonnes; j++) { std::cin >> grille; maxima[j] = 1 - grille; if(grille == 0) cote = 1; } int j0 = 0; // Ligne précédente. int j1 = nbColonnes; // Ligne courante. // Lire les autres lignes. for(int i = 1; i < nbLignes; i++) { std::cin >> grille; // Premier de la ligne. maxima[j1] = 1 - grille; // Reste de la ligne. for(int j = 1; j < nbColonnes; j++) { std::cin >> grille; if(grille == 1) { maxima[j1+j] = 0; } else { int mini = maxima[j0+j-1]; if(maxima[j0+j] < mini) mini = maxima[j0+j]; if(maxima[j1+j-1] < mini) mini = maxima[j1+j-1]; maxima[j1+j] = ++mini; if(mini > cote) cote = mini; } } // Interchanger les deux lignes. j0 = nbColonnes - j0; j1 = nbColonnes - j1; } std::cout << cote << std::endl; return 0; }
Le Tout est souvent plus grand que la somme de ses parties.
Je savais que le code était rapide, mais je ne savais pas s'il y aurait eu un bug caché (un bug pas caché, ça existe?)
XD, par définition, les bugs sont toujours cachés jusqu'à ce que quelqu'un tombe dessus. Certains se trouvent vite, d'autres sont plus subtiles, voir perfides.
Merci beaucoup, vous m'avez aidé à bien comprendre !
Installation du camping
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.