Partage
  • Partager sur Facebook
  • Partager sur Twitter

Installation du camping

Installation du camping - France IOI

Sujet résolu
    7 novembre 2021 à 22:31:02

    Bonjour, 

    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 <= nbLignesnbColonnes <= 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.

    Exemples

    Exemple 1

    entrée :

    6 7
    1 0 0 1 0 0 1
    0 0 0 0 0 0 0
    1 0 0 0 0 0 0
    0 0 0 0 0 0 0
    0 1 0 0 0 0 1
    1 0 0 0 1 0 1

    sortie :

    4

    Exemple 2

    entrée :

    5 7
    0 0 0 1 1 1 1
    0 0 0 1 1 1 1
    0 0 0 1 1 1 1
    1 1 1 1 1 0 0
    1 1 1 1 1 0 0

    sortie :

    3
    Voici mon code : 
    #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];
    
       for (int i = 0; i < NbLignes; ++i)
       {
          for (int j = 0; j < NbColonnes; ++j)
          {
             cin >> Camping[i][j];
          }
       }
    
       int conteur = 0;
       int Max = 0;
       for (int i = 0; i < NbLignes - conteur + 1; ++i)
       {
          for (int j = 0; j < NbColonnes - conteur + 1; ++j)
          {
    
    
             if (Camping[i][j] == 0){
                bool stop = false;
                int j2 = j;
                int i2 = i;
                conteur = 1;
                while (Camping[i2][j2] != 1)
                   {  
                      for (int z = i; z <= i2; ++z)
                      {
                         for (int y = j; y <= j2; ++y)
                         {
                            if (Camping[z][y] != 0){
                               stop = true;
                            }
                         }
                      }
                   if (stop)
                         break;
                   if (j2+1 > NbColonnes || i2+1 > NbLignes)
                      break;
                   j2++;
                   i2++;
                   conteur++;
                }
             }
             if (conteur > Max)
                Max = conteur;
          }
       }
       cout << Max - 1;
    }
    
    
     
    • Partager sur Facebook
    • Partager sur Twitter
      8 novembre 2021 à 2:20:44

      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
      • Partager sur Facebook
      • Partager sur Twitter

      Le Tout est souvent plus grand que la somme de ses parties.

        8 novembre 2021 à 18:53:06

        Merci de votre réponse, 

        Cependant, je n'arrive pas à comprendre ma possible erreur ou en tout cas de voir là où je dois changer mon code...

        • Partager sur Facebook
        • Partager sur Twitter
          8 novembre 2021 à 19:23:45

          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

          • Partager sur Facebook
          • Partager sur Twitter

          Le Tout est souvent plus grand que la somme de ses parties.

            8 novembre 2021 à 20:48:39

            En utilisant des fonctions alors ?

            Et sans tableaux multidimensionnels ?

            -
            Edité par CyrilZ 8 novembre 2021 à 20:49:09

            • Partager sur Facebook
            • Partager sur Twitter
              9 novembre 2021 à 1:41:26

              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

              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                9 novembre 2021 à 22:16:27

                CyrilZ a écrit:

                #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.

                • Partager sur Facebook
                • Partager sur Twitter
                  9 novembre 2021 à 22:54:54

                  Normalement non, mais gcc l'accepte (warning avec l'option -pedantic).
                  • Partager sur Facebook
                  • Partager sur Twitter
                    9 novembre 2021 à 23:25:10

                    rouIoude a écrit:

                    Normalement non, mais gcc l'accepte (warning avec l'option -pedantic).

                    J'avais compilé avec g++ -std=c++14 -Wall et sans aucun warning. Donc il faut pedantic, merci de l'info.
                    • Partager sur Facebook
                    • Partager sur Twitter
                      10 novembre 2021 à 0:57:52

                      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

                      • Partager sur Facebook
                      • Partager sur Twitter

                      Le Tout est souvent plus grand que la somme de ses parties.

                        11 novembre 2021 à 1:34:32

                        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;
                        }
                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          11 novembre 2021 à 10:18:38

                          Ton code passe tous les tests (22 tests) Pierrot. Bravo !
                          • Partager sur Facebook
                          • Partager sur Twitter
                            11 novembre 2021 à 16:52:18

                            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?)
                            • Partager sur Facebook
                            • Partager sur Twitter

                            Le Tout est souvent plus grand que la somme de ses parties.

                              11 novembre 2021 à 19:49:58

                              PierrotLeFou a écrit:

                              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.
                              • Partager sur Facebook
                              • Partager sur Twitter
                                12 novembre 2021 à 1:36:12

                                Ma parenthèse n'était pas sérieuse. Je n'en suis tout de même pas à mon premier programme.

                                C'est seulement parce que je ne sais pas comment accéder au site et faire les tests moi-même.

                                -
                                Edité par PierrotLeFou 12 novembre 2021 à 7:10:03

                                • Partager sur Facebook
                                • Partager sur Twitter

                                Le Tout est souvent plus grand que la somme de ses parties.

                                  12 novembre 2021 à 17:45:58

                                  Merci beaucoup, vous m'avez aidé à bien comprendre !
                                  • Partager sur Facebook
                                  • Partager sur Twitter

                                  Installation du camping

                                  × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                  • Editeur
                                  • Markdown