Partage
  • Partager sur Facebook
  • Partager sur Twitter

FRANCE IOI : Optimiser une recherche

Collage d'affiche

Sujet résolu
    14 janvier 2020 à 12:06:22

    Bonjour, j'ai actuellement un probleme pour resoudre un exercice  de France IOI, ma recherche est trop lente.

    Voici l'enonce :

    Des affiches rectangulaires sont collées les unes après les autres sur un mur. Toutes les affiches ont la même largeur. On vous donne la hauteur Hi de chacune de ces affiches, dans l'ordre dans lequel elles sont collées. Le coin supérieur gauche de chaque affiche est toujours placé exactement sur le coin supérieur gauche du mur, et ce dernier est toujours plus grand que les affiches. Régulièrement, entre deux collages d'affiches, on vous demande d'indiquer combien d'affiches, parmi celles déjà collées, sont au moins en partie visibles, c'est à dire qu'une surface non nulle n'a été recouverte par aucune affiche collée depuis.

    Limites de temps et de mémoire (Python)

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

    Contraintes

    • 1 <= nbRequetes <= 100 000, où nbRequetes est le nombre de requêtes, une requête pouvant correspondre au collage d'une affiche ou bien à une question sur le nombre d'affiches visibles.
    • 1 <= hauteuri <= 1 000 000, où hauteuri est la hauteur d'une affiche

    Entrée

    La première ligne de l'entrée est constituée d'un unique entier :nbRequetes

    Chacune des nbRequetes lignes suivantes commence par un caractère pouvant être 'Q' ou 'C'. Un caractère 'Q' correspond à la question : "Combien d'affiches sont actuellement visibles?". Un caractère 'C' est suivi d'un entier hauteur et correspond au collage d'une affiche de hauteur hauteur.

    Sortie

    La sortie de votre programme doit correspondre aux réponses aux questions données en entrée, dans l'ordre dans lequel elles apparaissent.

    Et voici ma réponse, mais trop lente :

    from bisect import bisect_right
    def search(alist, item):
        i = bisect_right(alist, item)
        return i
    requetes = int(input())
    tab = []
    for i in range(requetes):
       requete = input()
       if requete == "Q":
          print (len(tab))
       else :
          taille = int(requete[2:])
          if len(tab) == 0 :
             tab.append(taille)
          else :
             index_affiche = search(tab, taille)
             if index_affiche == len(tab):
                tab = [taille]
             else :
                tab.insert(index_affiche, taille)
                tab = tab[index_affiche:]

    je ne comprends pas comment optimiser mieux ce programme, quelqu'un pourrait me donner un indice s'il vous plait? J'ai déjà tenté de faire ma propre recherche dichotomique mais c’était trop lent, alors j'en ai pris une d'une library qui je suppose est déjà optimisée, mais malgré tout je suis trop lent... Merci :)

    • Partager sur Facebook
    • Partager sur Twitter
      14 janvier 2020 à 14:29:01

      Je pense que la bisect vous fait perdre plus de temps qu'autre chose.

      ls = []
      for _ in range(int(input())):
          s = input()
          if s == "Q":
              print(len(ls))
          else:
              h = int(s.split()[-1])
              for i, n in enumerate(ls):
                  if h >= n:
                      # Affectation par slicing (remplace toutes les valeurs
                      # du slice par celles de la nouvelle liste)
                      ls[i:] = [h]
                      break
              else: # if not break:
                  ls.append(h)

      Ça devrait être suffisant pour passer largement en-dessous de la limite des 2 secondes.

      Edit: correction et commentaires.

      -
      Edité par TryCatch1 14 janvier 2020 à 14:48:23

      • Partager sur Facebook
      • Partager sur Twitter
        14 janvier 2020 à 14:38:34

        Juste au cas où : j'ai été obligé d'utiliser sys.stdin.readline() à la place de input() pour passer les perfs
        • Partager sur Facebook
        • Partager sur Twitter
          14 janvier 2020 à 16:51:12

          TryCatch Merci pour ta reponse, mais ta solution n'est pas assez rapide :/, meme en ajoutant l'aide de linekioubeur. 

          Par contre linekioubeur j'ai teste ta solution sur mon premier jet de code et ca marche! Merci ^^

          import sys
          requetes = int(input())
          tab = []
          for i in range(requetes):
             requete=sys.stdin.readline()
             if requete == "Q\n":
                print (len(tab))
             else :
                taille = int(requete[2:])
                while len(tab) !=0 and tab[-1]<= taille:
                   del tab[-1]
                tab.append(taille)



          • Partager sur Facebook
          • Partager sur Twitter
            14 janvier 2020 à 21:55:44

            HugoCarpentier1 a écrit:

            import sys
            requetes = int(input())
            tab = []
            for i in range(requetes):
               requete=sys.stdin.readline()
               if requete == "Q\n":
                  print (len(tab))
               else :
                  taille = int(requete[2:])
                  while len(tab) !=0 and tab[-1]<= taille:
                     del tab[-1]
                  tab.append(taille)



            Et tu passes tous les tests de performance avec ce code ?
            • Partager sur Facebook
            • Partager sur Twitter
              15 janvier 2020 à 10:20:02

              Oui, il a une complexite O(2N), ce qui est suffisant pour passer les tests de performances ^^.

              Mon second algorithme (la recherche dichotomque) avait une complexité O(N(log(n)) qui était trop longue

              -
              Edité par HugoCarpentier1 15 janvier 2020 à 10:21:38

              • Partager sur Facebook
              • Partager sur Twitter

              FRANCE IOI : Optimiser une recherche

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