Partage
  • Partager sur Facebook
  • Partager sur Twitter

Optimisation d'algorithme

Aide pour exo sur France-IOI

Sujet résolu
    22 mars 2022 à 3:01:44

    Bonjour. J'en suis à ma 47ème (!) soumission et je n'y arrive toujours pas.

    Je résume l'énoncé de l'exercice (origine):

    En entrée

    Une première ligne contenant deux entiers (séparés par un espace) : N et P. N = Nombre total d'élèves inscrits dans la classe (entre 1 et un milliard); P = Nombre d'élèves qui vont venir en classe aujourd'hui.

    Les P lignes suivantes contiennent chacune un entier: l'identifiant d'un élève qui arrive en cours, c'est-à-dire sa position dans la liste alphabétique des élèves de la classe. On vous garantit que chaque identifiant n'apparaît qu'une fois.

    En sortie

    Vous devez afficher P lignes : à chaque fois qu'un élève arrive, vous devez afficher l'identifiant du premier élève absent. Si tous les élèves inscrits sont présents, vous devez afficher -1.

    Exemple

    entrée :

    10 5
    4
    1
    7
    3
    2

    sortie :

    1
    2
    2
    2
    5

    Voilà ce que j'ai fait de mieux:

    import sys
    
    def main():
    
        max, venus = map(int, sys.stdin.readline().split())
        
        presents = []
        absent = 1
        
        for _ in range(venus):
            
            arrivant = int(sys.stdin.readline())
            max -= 1
            
            if arrivant > absent:
                presents.append(arrivant)
                        
            elif arrivant == absent:
                absent += 1
                if presents:
                    presents.sort()
                    indice = 0
                    l = len(presents)
                    while indice < l and absent == presents[indice]:
                        indice += 1
                        absent += 1
                    del presents[:indice]
            
            if not max:
                absent =- 1
                
            sys.stdout.write(str(absent)+'\n')
            
    main()
    

    Malheureusement, pour 3 tests sur 20 je reçois le message suivant:

    Échec

    Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.

    -
    Edité par Zèbre 22 mars 2022 à 3:05:28

    • Partager sur Facebook
    • Partager sur Twitter
      22 mars 2022 à 7:05:04

      Je n'ai pas pu accéder à ton lien parce que je ne suis pas connecté.
      L'énoncé n'est pas très clair. À la lumière de ton exemple, j'ai écrit ce qui suit.
      Ça fonctionne avec l'exemple. J'ai utilisé les "set" plutôt qu'une liste. Ça devrait être plus rapide:
      -
      max, venus = map(int, input().split())
      absent = 1
      presents = set()
      for _ in range(venus):
          arrivant = int(input())
          presents.add(arrivant)
          while absent in presents:
              absent += 1
          if absent <= max:
              print(absent)
          else:
              print(-1)
      • Partager sur Facebook
      • Partager sur Twitter

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

        22 mars 2022 à 9:38:51

        Merci. Mais ça ne passe que 9 tests sur 20 (même message que moi pour les 11 autres).

        Je reproduis l'énoncé original:

        Ce matin, en arrivant en cours, vous êtes le seul à l'heure : tous vos camarades sont en retard ou absents. Comme d'habitude, après un certain temps, votre professeur va faire l'appel dans l'ordre alphabétique, et va punir très sévèrement le premier élève qui ne répondra pas présent. Il sera plus clément pour les suivants car il aura déjà réussi à déverser sa rage quotidienne sur quelqu'un.

        Les autres élèves arrivent un par un, dans un ordre quelconque. À chaque fois que l'un d'eux arrive, vous vous demandez quel serait l'élève puni, si votre professeur faisait l'appel juste après l'arrivée du nouvel élève.

        Les élèves sont numérotés en fonction de leur position dans l'ordre d'appel. Étant donnée la liste des élèves qui arrivent, votre programme doit calculer, pour chaque nouvel élément de la liste, l'élève ayant l'identifiant le plus petit qui n'est pas présent à ce moment.

        Limites de temps et de mémoire (Python)

        • Temps : 2,5 s sur une machine à 1 GHz.
        • Mémoire : 16 000 ko.

        Contraintes

        • 1 ≤ N ≤ 1 000 000 000, où N est le nombre d'élèves inscrits dans votre classe.
        • 1 ≤ P ≤ 250 000, où P est le nombre d'élèves présents aujourd'hui.
        • 1 ≤ Ei ≤ N, où Ei est l'identifiant d'un élève.
        De plus, on vous garantit que :
        • Dans 20% des fichiers tests, on a N ≤ 1 000 et P ≤ 1 000.
        • Dans 70% des fichiers tests, on a N ≤ 250 000.

        Entrée

        • La première ligne de l'entrée contient deux entiers séparés par un espace : N et P.
        • Les P lignes suivantes contiennent chacune un entier : l'identifiant d'un élève qui arrive en cours, c'est-à-dire sa position dans la liste alphabétique des élèves de la classe. On vous garantit que chaque identifiant n'apparaît qu'une fois.

        Sortie

        Vous devez afficher P lignes : à chaque fois qu'un élève arrive, vous devez afficher l'identifiant du premier élève absent. Si tous les élèves inscrits sont présents, vous devez afficher -1.

        • Partager sur Facebook
        • Partager sur Twitter
          22 mars 2022 à 10:29:02

          Dans le programme de Pierrot, on sait que les élèves de 1 à absent-1 sont arrivés. On peut donc les retirer de l'ensemble présents, ce qui réduit sa taille

          import sys
           
          def main():
          
              max, venus = map(int, input().split())
              absent = 1
              presents = set()
              for _ in range(venus):
                  arrivant = int(input())
                  if arrivant == absent:
                      absent += 1
                      while absent in presents:
                          presents.remove(absent)
                          absent += 1
                  else: 
                      presents.add(arrivant)
                  if absent <= max:
                      print(absent)
                  else:
                      print(-1) 
          

          En bref, l'ensemble des élèves présents est modélisé par l'union de deux trucs disjoints

          • les entiers de 1 à absent -1
          • les éléments du set "présents"
          ---
          dans le programme d'origine, ce qui fout dedans, c'est l'utilisation d'une liste, qui est retriée constamment.  Alors que la recherche dans un set se fait en temps constant.

          -
          Edité par michelbillaud 22 mars 2022 à 10:31:40

          • Partager sur Facebook
          • Partager sur Twitter
            22 mars 2022 à 10:53:18

            Désolé, ça ne passe que 12 tests sur 20.

            Pour 6 tests je reçois:

            Erreur

            Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.

            (même message de lenteur pour les 2 tests restants)

            -
            Edité par Zèbre 22 mars 2022 à 10:59:16

            • Partager sur Facebook
            • Partager sur Twitter
              22 mars 2022 à 14:15:28

              Et le code suivant?
              -
              max, venus = map(int, input().split())
              absent = 1
              presents = set()
              for _ in range(venus):
                  arrivant = int(input())
                  presents.add(arrivant)
                  while absent in presents:
                      presents.remove(absent)
                      absent += 1
                  if absent <= max:
                      print(absent)
                  else:
                      print(-1)
              • Partager sur Facebook
              • Partager sur Twitter

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

                22 mars 2022 à 14:35:49


                  12/20

                Pour 7 tests: Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.

                Pour le 8ème: Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.

                • Partager sur Facebook
                • Partager sur Twitter
                  22 mars 2022 à 15:32:22

                  n, p = map(int, input().split())
                  t, s = set(range(1, n + 1)), set()
                  for _ in range(p):
                      s.add(int(input()))
                      print(min(t - s))
                  • Partager sur Facebook
                  • Partager sur Twitter
                    22 mars 2022 à 16:56:18

                    Si n vaut 1_000_000_000 tu auras un problème de mémoire.
                    Il faut réduire le plus possible la longueur des set/list/dict s'il y a lieu.
                    Il faudrait éviter le parcours de longues séquences.
                    Dans quelle mesure les set et les dict sont rapides aà parcourir?
                    • Partager sur Facebook
                    • Partager sur Twitter

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

                      22 mars 2022 à 16:58:55

                      2 / 20

                      Pour 2 tests: Erreur d'exécution. Voici ce qui a été affiché :

                      Traceback (most recent call last):
                        line 5
                          print(min(t - s))
                      ValueError: min() arg is an empty sequence

                      Pour 2 tests: Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment.

                      Pour tous les autres: Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.

                      • Partager sur Facebook
                      • Partager sur Twitter
                        22 mars 2022 à 17:14:42

                        Nos codes ne dépassent pas la zone des set ou listes, mais la mémoire imposée.
                        Comme je viens de le dire, les ensembles sont trop longs et prennent trop de temps à parcourir.
                        Je cherche encore un truc ...

                        On pourrait faire une recherche dichotomique pour insérer l'arrivant et chercher si l'absent est dans la liste.

                        On pourrait garder le plus petit et le plus grand arrivant. On pourrait ainsi éviter d'ajouter des éléments dans la liste.

                        ...

                        Qui a dit que cet algo était simple?

                        -
                        Edité par PierrotLeFou 22 mars 2022 à 17:44:16

                        • Partager sur Facebook
                        • Partager sur Twitter

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

                          22 mars 2022 à 17:37:36

                          La solution ne serait pas de stocker des elements individuels mais des ranges dès qu'on le peut. Ainsi, plutôt que d'avoir [0,1,2,3,4] on peut directement avoir range(5). L'espace occupé par un range est constant. En outre, il permet aussi d'utiliser in. 

                          -
                          Edité par Nephthys 22 mars 2022 à 17:38:21

                          • Partager sur Facebook
                          • Partager sur Twitter
                            22 mars 2022 à 17:50:01

                            Le problème est qu'on peut avoir plusieurs range dans la liste.
                            Si comme je l'ai dit, on garde le plus petit et le plus grand.
                            L'absent pourrait se trouver dans un de ces range ou entre deux range.
                            Comment mettre à jour ces range de façon efficace?
                            • Partager sur Facebook
                            • Partager sur Twitter

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

                              22 mars 2022 à 18:18:55

                              PierrotLeFou a écrit:

                              Le problème est qu'on peut avoir plusieurs range dans la liste.
                              Si comme je l'ai dit, on garde le plus petit et le plus grand.
                              L'absent pourrait se trouver dans un de ces range ou entre deux range.
                              Comment mettre à jour ces range de façon efficace?


                              Non, mais justement, on ne met que les range pour lesquels tout le monde est là ... sinon ça n'a aucun intérêt. Au début c'est coûteux parce qu'un range prend plus de place en mémoire qu'un int, mais plus il y a d'item moins cela devient coûteux. Si dans la liste on a [range(10, 15), range(16, 18), range(20, 23)] et que 15 apparait, on se retrouve avec [range(10,18), range(20,23)] en fusionnant les deux premiers.

                              -
                              Edité par Nephthys 22 mars 2022 à 18:19:05

                              • Partager sur Facebook
                              • Partager sur Twitter
                                22 mars 2022 à 18:39:54

                                Ça j'avais compris. Mais il y a toujours la contrainte de temps qui semble assez serrée.
                                Et si les range sont ordonnés comme on devrait pouvoir le faire, comment les représente-t-on?
                                par ex: [10, 15, 16, 18, 20, 23] où les positions paires sont les débuts et les positions impaires sont les fins.
                                ou encore [[10, 15], [16, 18], [20, 23]]
                                et [range(10, 16), range(16, 19), range(20, 24)] fonctionne également.
                                Mais la dernière forme est plus difficile à gérer.
                                • Partager sur Facebook
                                • Partager sur Twitter

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

                                  22 mars 2022 à 18:53:40

                                  avec les range, on peut récupérer les valeurs de start et stop: range(10,16).start => 10 (mais ce sont des valeurs en lecture seule)
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    22 mars 2022 à 19:14:04

                                    Un ami me dit qu'il a la solution; selon lui, il y aurait un indice capital dans l'énoncé auquel je n'ai pas fait attention. Pour l'instant je ne vois pas.

                                    Y a-t-il quelque chose à tirer de ces lignes?

                                    De plus, on vous garantit que :

                                    • Dans 20% des fichiers tests, on a N ≤ 1 000 et P ≤ 1 000.
                                    • Dans 70% des fichiers tests, on a N ≤ 250 000.

                                    -
                                    Edité par Zèbre 22 mars 2022 à 19:16:48

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      22 mars 2022 à 21:27:11

                                      Une manière d'optimiser serait-elle en affichant toute (ou une partie) des lignes d'un coup?

                                      Je me souviens que lorsque j'avais fait les exos france-ioi (avec un autre langage), c'était un problème que j'avais eu et qui plombait mon algo en temps.

                                      Dans les 30% de tests, il n'y aurait pas de -1 à afficher aussi. Le -1 est à afficher que lorsque P >= N (qui n'arrive que dans le cas particulier où P = N).

                                      EDIT: Le truc des 250k affichages est faux. C'est juste P affichages quoiqu'il arrive.

                                      -
                                      Edité par KoaTao 22 mars 2022 à 21:39:13

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        23 mars 2022 à 0:51:11

                                        @umfred: merci pour le truc des .start et .stop
                                        L'énoncé dit:
                                        > En sortie
                                        > Vous devez afficher P lignes : à chaque fois qu'un élève arrive, vous devez afficher l'identifiant du premier élève absent.
                                        Que veut dire "à chaque fois qu'un élève arrive"?
                                        Est--ce qu'on laisse supposer qu'on n'a pas besoin d'accumuler ceux qui sont venus?
                                        > Si tous les élèves inscrits sont présents, vous devez afficher -1.
                                        KoaTao a bien précisé que cela n'arrive que si n == p
                                        Mais doit-on afficher -1 dès le début ou après p-1 lignes?

                                        -

                                        Je me ramasse des indices:

                                        Supposons qu'on a une telle liste d'intervalles, le nouvel arrivant ne se trouvera dans aucun intervalle, puisqu'on nous garantit qu'il n'apparaît qu'une fois.

                                        Il se trouvera soit avanrt le premier, soit après le dernier ou entre deux intervalles.

                                        Si l'absent se trouve entre le plus petit et le plus grand, il faudra faire sauter les intervalles des éléments plus petits.

                                        Joyeuse gestion des intervalles. :)

                                        Si on nous accorde 16 000 Ko, on doit bien pouvoir accumuler quelque chose ...

                                        edit:
                                        J'ai codé quelque chose avec les intervalles qui fonctionne avec l'exemple mentionné et je suppose qu'il marchera pour tous les cas.
                                        J'ai choisi de représenter les intervalles tels que les positions paires (0, 2, 4, ...) représentent les bornes inférieures et les positions impaires suivantes représentent les bornes supérieures.
                                        Je ne sais pas si ma fonction insertion est suffisamment efficace.
                                        On ne doit rien retrancher de la liste des intervalles. Je n'enlevais rien de mes set() dans le code précédent.
                                        -
                                        # Recherche dichotomique avec point d'insertion.
                                        def recherche(liste, val):
                                            d = 0
                                            f = len(liste)
                                            while d < f:
                                                m = (d+f) // 2
                                                if liste[m] == val: return m
                                                elif liste[m] > val: f = m
                                                else: d = m+1
                                            return -(d+1)   # Point d'insertion.
                                        # Insertion de la valeur (elle ne peut pas être déjà présente)
                                        # Les intervalles seront disjoints.
                                        def insertion(liste, val):
                                            if len(liste) == 0: liste[:] = [val, val]
                                            elif val < liste[0]: liste[:] = [val, val] + liste
                                            elif val > liste[-1]: liste.extend([val, val])
                                            else:
                                                p = recherche(liste, val)
                                                p = -(p+1)   # Sera forcément négatif.
                                                p = p ^ (p&1)   # Borne inférieure si les bornes sont égales.
                                                if liste[p-1]+2 == liste[p]: liste[p-1:p+1] = []
                                                elif liste[p-1] == val-1: liste[p-1] = val
                                                elif liste[p] == val+1: liste[p] = val
                                                else: liste[p:p+1] = [val, val, liste[p]]
                                        # Code principal.
                                        max, venus = map(int, input().split())
                                        absent = 1
                                        presents = []
                                        for _ in range(venus):
                                            arrivant = int(input())
                                            insertion(presents, arrivant)
                                            p = recherche(presents, absent)
                                            if p < 0:   # On n'est pas sur une borne.
                                                p = -(p+1)    # Point d'insertion    
                                                if p&1:   # Dans un intervalle
                                                    absent = presents[p] + 1    # Suivant de l'intervalle
                                            else:   # On est sur une borne.
                                                absent = presents[p|1] + 1   # Borne supérieure + 1
                                            if absent <= max:
                                                print(absent)
                                            else:
                                                print(-1)

                                        -
                                        Edité par PierrotLeFou 23 mars 2022 à 6:10:40

                                        • Partager sur Facebook
                                        • Partager sur Twitter

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

                                          23 mars 2022 à 12:50:43

                                          Désolé, ça ne passe que 3 tests sur 20.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            23 mars 2022 à 13:03:55

                                            Est-ce que tu as essayé si, comme KoaTao l'a évoqué, en faisant la saisie au début (boucle de saisie), puis en bouclant sur le tableau des saisies ça changeait quelque chose ?
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              23 mars 2022 à 13:57:23

                                              Et pourquoi les tests sont-ils refusés? Est-ce la mémoire ou le temps d'exécution?
                                              Ton ami qui prétend avoir réussi ne t'a donné aucun indice?

                                              Je pourrais bien faire des tests avec un milliard d'éléments, mais je ne serais pas certain de la validité des résultats.

                                              -
                                              Edité par PierrotLeFou 23 mars 2022 à 14:00:17

                                              • Partager sur Facebook
                                              • Partager sur Twitter

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

                                                23 mars 2022 à 15:17:49

                                                Ouf! Ca y est.

                                                Mémoire : 16 000 ko.

                                                *1 ≤ P ≤ 250 000, où P est le nombre d'élèves présents aujourd'hui.

                                                Ce qu'on peut remarquer rapidement dans ce programme c'est qu'on a le droit à suffisamment d'espace mémoire pour stocker 1 million ou plus d'éléments. Donc plutôt que de créer des structures complexes, et d'essayer d'optimiser en taille la mémoire. On peut directement utiliser ce qu'on nous donne. Bien sur on ne peut pas stocker 1 milliards d'éléments, mais sachant que seulement 250 000 élèves seront présent, il nous suffit de stocker 250.000 éléments. On peut donc noter dans un tableau de booléens si un élève (<250.000) est présent ou absent.

                                                [false]*250000

                                                Remplir ce tableau se fait en O(1) Et mettre à jour la position du dernier absent est en O(n) mais ne se recalcule pas à chaque boucle, c'est O(n) sur toute la durée du programme. Donc on obtiens un programme plus rapide qu'un set car on a juste un tableau statique.

                                                (texte de neo-magestik, pour ceux qui l'ont connu, de chez France IOI)


                                                Voilà une solution (merci à neo-magestik qui m'a bien aiguillé):

                                                import sys
                                                def main():
                                                    max, venus = map(int, sys.stdin.readline().split())
                                                    absent = 1
                                                    presents = [False]*250002
                                                    for i in range(1,venus):
                                                        arrivant = int(sys.stdin.readline())
                                                        if arrivant <= 250000: presents[arrivant] = True
                                                        if arrivant == absent:
                                                            while presents[absent]: absent += 1
                                                        sys.stdout.write(str(absent)+'\n')
                                                        
                                                    dernier = int(input())
                                                    if venus == max: absent =- 1
                                                    elif dernier == absent:
                                                        presents[dernier]=True
                                                        while presents[absent]: absent += 1
                                                    sys.stdout.write(str(absent)+'\n')
                                                main()

                                                Et merci à vous tous aussi pour votre soutien et votre implication.

                                                J'ai quand même appris quelques choses intéressantes de vos idées et propositions.

                                                -
                                                Edité par Zèbre 23 mars 2022 à 15:52:43

                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  23 mars 2022 à 16:54:22

                                                  Je croyais que c'était possible d'avoir n=1000000000 et p=250000.
                                                  Moi aussi, j'ai pu expérimenter des trucs intéressants.
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter

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

                                                    23 mars 2022 à 18:08:33

                                                    bah c'est possible, mais tant que l'étudiant n°1 ne sera pas passé, ça sera toujours lui le plus petit absent et au pire, ça sera le 250000-1 qui sera le plus petit
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      24 mars 2022 à 2:14:31

                                                      neo-magestik a écrit:
                                                      > Remplir ce tableau se fait en O(1)
                                                      Désolé, ça se fait en O(p)   (tout de même très rapide)
                                                      >Et mettre à jour la position du dernier absent est en O(n) mais ne se recalcule pas à chaque boucle, c'est O(n) sur toute la durée du programme.
                                                      Mettre à jour la position de l'arrivant se fait en O(1) au pire p fois.
                                                      Et on ne parcours le tableau qu'une fois, soit O(p) pour tout le programme.

                                                      Et absent est augmenté au pire à chaque tour de boucle, donc absent <= 250000+1

                                                      -
                                                      Edité par PierrotLeFou 24 mars 2022 à 2:20:58

                                                      • Partager sur Facebook
                                                      • Partager sur Twitter

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

                                                        26 mars 2022 à 10:29:19

                                                        de ce que j'ai compris, un code dans ce genre là devrait solutionner les limitations matériel et temporel imposés:

                                                        lst =[]
                                                        P = P.sort(reverse=False)
                                                        
                                                        for i in P:
                                                            i -= 1
                                                            if len(P) == N:
                                                               print(-1)
                                                            else:
                                                               lst.append(i)
                                                        # que ce passe t'il si c'est le premier elève de la liste qui est absent: le prof passe sa colère aucun élève?
                                                        voici comme je gère ce cas là:
                                                        if lst[0] == 0:
                                                           lst[0] = None
                                                        else:
                                                            pass

                                                        explication vite fait du code:

                                                        je parcours les élèments de la liste P (liste des élèves présents) que j'ai au préalable trié par ordre croissant

                                                        je vérifie si la longueur de la liste P est élage à la valeur du nb d'éléve inscrit, auquel cas, tt le monde est là et je print -1

                                                        sinon, j'append dans une liste les éléments (éléves) qui précédent ceux présent

                                                        et y a le cas où c'est l'éléve à la position 1 de la liste alphabétique qui est absent...pour pas me retrouver avec un 0, je dis que ça vaut None.

                                                        si vous avez encore des erreur dû au temps d'éxécution, je vous invite à jeter un coup d'oeil sur la méthode invert du package operator (faire un import).

                                                        cela peut être utile surtout si la liste P passé en paramètre est supérieure ou égale 

                                                        Vous pourrez me dire ce qu'il en est.

                                                        merci

                                                        -
                                                        Edité par moimeme10 26 mars 2022 à 11:35:23

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          26 mars 2022 à 23:33:25

                                                          Oui, mais on a évidemment pas l'ensemble des éléments de P, ils arrivent un par un ...

                                                          -
                                                          Edité par Nephthys 26 mars 2022 à 23:33:35

                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            27 mars 2022 à 0:21:26

                                                            On a déjà la solution de neo-magestik

                                                            Elle est très simple et très rapide.

                                                            -
                                                            Edité par PierrotLeFou 27 mars 2022 à 0:25:36

                                                            • Partager sur Facebook
                                                            • Partager sur Twitter

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

                                                              27 mars 2022 à 7:29:38

                                                              Résumé :

                                                              La difficulté : choix de représentation en python pour un ensemble de nombres entre 0 et N où N est assez grand (250000) dans un espace limité.

                                                              On a besoin d'ajouter, enlever, et tester si présent.

                                                              • Un set de valeurs ne le fait pas (espace, trop gros en python)
                                                              • Une liste de valeurs non plus (temps, impliquerait de l'ordonner constamment)

                                                              le choix qui marche : liste de booléens, indicée par les valeurs.

                                                              -
                                                              Edité par michelbillaud 27 mars 2022 à 7:32:21

                                                              • Partager sur Facebook
                                                              • Partager sur Twitter

                                                              Optimisation d'algorithme

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