Bonjour

Je n'arrive pas à passer en temps cet exercice de France IOI

Limites de temps et de mémoire (Python)

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

Contraintes

Entrée

Sortie

Exemple

entrée :

12 17
1 2 12
1 3 10
2 4 11
2 5 13
3 5 12
3 7 13
4 6 9
5 6 7
6 7 15
6 10 13
6 11 11
7 8 7
8 9 12
8 10 10
9 10 10
10 11 9
11 12 10

sortie :

0 12 10 23 22 29 23 30 42 40 40 50
12 0 22 11 13 20 35 42 43 33 31 41
10 22 0 28 12 19 13 20 32 30 30 40
23 11 28 0 16 9 24 31 32 22 20 30
22 13 12 16 0 7 22 29 30 20 18 28
29 20 19 9 7 0 15 22 23 13 11 21
23 35 13 24 22 15 0 7 19 17 26 36
30 42 20 31 29 22 7 0 12 10 19 29
42 43 32 32 30 23 19 12 0 10 19 29
40 33 30 22 20 13 17 10 10 0 9 19
40 31 30 20 18 11 26 19 19 9 0 10
50 41 40 30 28 21 36 29 29 19 10 0

voici mon code avec l'algorithme de Floyd-Warshall

import sys

def floyd_warshall(n, graph):
    # Initialisation de la matrice des distances
    dist = [[float('inf')] * n for _ in range(n)]
    
    # Distance de chaque intersection à elle-même est 0
    for i in range(n):
        dist[i][i] = 0
    
    # Remplir la matrice avec les distances directes du graphe
    for (u, v, w) in graph:
        dist[u-1][v-1] = w
        dist[v-1][u-1] = w
    
    # Algorithme de Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

def main():
  # Lecture de l'entrée
  # n, a = map(int, input().split())
  n, a = map(int, sys.stdin.readline().split())
  graph = []
  for _ in range(a):
      u, v, l = map(int, input().split())
      graph.append((u, v, l))

  # Appel de la fonction pour obtenir la matrice des plus courts chemins
  distances = floyd_warshall(n, graph)

  # Affichage de la matrice des distances
  for i in range(n):
      # print(" ".join(map(str, distances[i])))
      sys.stdout.write(" ".join(map(str, distances[i])) + "\n")

main()

et en sortie des tests

et je ne vois pas comment faire plus rapide

-
Edité par Duncan4031 14 août 2024 à 23:39:51

Tu fais certains calculs en double:

                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

Ceci:

dist[i][k] + dist[k][j]

Mets le dans une variable.

Ce qui est invariant par rapport à j pourrait être placé avant la boucle dans une autre variable.

dist_ik = dist[i][k]
dist_k = dist[k]   # C'est une ligne (dans la boucle sur k_).
dist_i = dist[i]   # Une autre ligne(boucle sur i).
dist[i][j] pourrait être remplacé par:
dist_i[j]

Si dist[i][k] est infini, il est inutile de faire la boucle sur j car rien ne sera plus grand.

Je ne sais pas si l'utilisation de "array" pourrait accélérer?

Je ne comprend pas pourquoi tu ne génères pas directement la mattrice à partir des données. Tu connais la dimension de ta matrice dès la première ligne (N, A).

Je ne sais pas non plus pourquoi France IOI vous oblige à utiliser sys.stdout.write avec une chaîne.
    print(*distance[i])
serait plus rapide.

Quand tu passes une matrice en paramètre à une fonction, tu n'as pas besoin de la retourner. Petit exemple bête qui marche:
def calcul(a):
    a[1][1] = 2
a = [[0] * 3 for _ in range(3)]
calcul(a)
print(a[1][1])

-
Edité par PierrotLeFou 17 août 2024 à 4:34:15

Bonjour

voici le lien, c'est du niveau 5

https://www.france-ioi.org/algo/task.php?idChapter=539&idTask=255

@PierrotLeFou

je viens de tester ton programme

il réussit 6 tests sur 10

Si je l’intègre à l'intérieur d'une fonction

le test 6 passe de 6.63s à 3.25s, et ton programme passe en plus le test 7

def main():
   # Lecture des paramètre et initialisation du graphe.
   n, a = map(int, input().split())
   graphe = [[float('inf')] * n for _ in range(n)]
   for i in range(n):
       graphe[i][i] = 0
   # Lecture des sentiers et assignation dans le graphe.
   for _ in range(a):
       u, v, w = map(int, input().split())
       graphe[u-1][v-1] = w
       graphe[v-1][u-1] = w
   # Algorithme de Floyd-Warshall.
   infini = float("inf")
   for k in range(n):
       graphe_k = graphe[k]
       for i in range(n):
           graphe_i = graphe[i]
           graphe_ik = graphe_i[k]
           if graphe_ik == infini: continue
           for j in range(n):
               graphe_ikj = graphe_ik + graphe_k[j]
               if graphe_i[j] > graphe_ikj:
                   graphe_i[j] = graphe_ikj
   # Affichage des résultats.
   for i in range(n):
       print(*graphe[i]) 
main()

L'algorithme de Floyd-Warshall a une complexité temporelle en O(n^3).

Dans le pire cas avec n=500, on devra faire 125 millions de tests.

Je me demande si une autre approche ne serait pas préférable.

Il faudrait sans doute regarder du côté de Dijkstra ou Knuth ...

Ça fait peu de sens d'aller plus vite dans une fonction. Je serais curieux de savoir ce que ça donne si on repassait le "même" code 2 ou 3 fois?

-
Edité par PierrotLeFou 19 août 2024 à 19:41:41

Bha j'ai pas accès à l'exo. Je mets mon code ici au cas, à voir si c'est plus rapide dans une fonction:

from sys import stdin

n,a = map(int,input().split())
c = list()
t = [{i:0} for i in range(n)]

for l in stdin.read().splitlines():
    i,j,l = map(int,l.split())
    i,j = i-1,j-1
    t[j][i] = t[i][j] = l
    c.append((i,j))
    
for i,j in c:
    for j2 in t[j]:
        if not j2 in t[i]:
            c.append((i,j2))
            t[j2][i] = t[i][j2] = t[i][j] + t[j][j2]
        else:
            l = t[i][j] + t[j][j2]
            if l<t[i][j2]:
                t[j2][i] = t[i][j2] = l
                
for i in t:
    print(*[y for x,y in sorted(i.items())])

-
Edité par josmiley 19 août 2024 à 20:35:50

Voici ce qu'en dit le correcteur de l'exercice.

Dans ce problème, on vous demande en fait de calculer les longueurs des plus courts chemins entre toutes les paires d'intersections possibles.

Il est bien sûr possible d'appliquer l'algorithme de plus court chemin Dijkstra vu précédemment pour chaque point de départ et de le laisser poursuivre à chaque fois jusqu'à-ce qu'un chemin ait été trouvé pour chaque destination.

L'algorithme Dijkstra a une complexité en temps de A*log(A), où A est le nombre d'arêtes du graphe (on peut aussi l'implémenter en N², mais c'est moins intéressant ici. Si on l'applique pour chaque point de départ, on obtient un algorithme de complexité N*A*log(A), soit de l'ordre de 500*5000*13 opérations en pire cas, donc 32 500 000. Avec l'implémentation de Dijkstra en N², on obtient une complexité totale de N³, soit de l'ordre de 500³ opérations, ou 125 000 000.

Dans le cas où l'on a un nombre important d'arcs par rapport au nombre de nœuds, il existe un algorithme très court qui permet de calculer tous les plus courts chemins et qui peut être plus rapide. Il s'agit de l'algorithme de Floyd-Warshall, dont la complexité est de N³. Le nombre d'itérations est plus important que pour N dijkstra (avec la première implémentation), mais son implémentation demande tellement peu d'instructions qu'il est plus rapide en pratique.

Cet algorithme nécessite de travailler avec la représentation par matrice d'adjacence et demande donc d'utiliser un tableau de N*N, dans lequel on stocke toutes les distances entre intersections. On initialise le tableau avec les distances fournies par les arcs pour les nœuds qui sont reliés directement, et avec une valeur "infinie" pour les autres. Pour les langages qui ne permettent pas de gérer des valeurs infinies, on se contentera de prendre la valeur maximale du type de données que l'on utilise.

Le principe de l'algorithme se base sur la relation suivante :

Le plus court chemin pour aller de source à dest est soit l'arc allant directement de source à dest, soit un chemin passant par un nœud intermédiaire inter. Le chemin du deuxième cas consiste alors en le plus court chemin de source à inter, suivi du plus court chemin de inter à dest.

Il s'agit d'une définition récursive, où pour déterminer le plus court chemin entre deux points, on essaie le chemin direct et les chemins passant par chaque nœud intermédiaire possible. On peut l'écrire directement en C++ :

int dist[MAX_NB_NOEUDS][MAX_NB_NOEUDS];

int PlusCourtChemin(int source, int dest)
{
   int minDistance = dist[source][dest];
   for (int inter = 0; inter < nbNoeuds; inter++)
      if ((inter != source) && (inter != dest)
      {
         int curDistance = PlusCourtChemin(source, inter) + PlusCourtChemin(inter, dest);
         minDistance = min(minDistance, curDistance);
      }
   return minDistance;
}

Si l'on se contente de l'écrire de cette manière, on tombe cependant dans une récursion infinie : pour calculer le plus court chemin de source à dest, on a besoin du plus court chemin entre source et inter, qui lui-même nécessite de connaître le plus court chemin de source à dest.

Pour éviter cette boucle infinie, il faut commencer par réécrire notre fonction récursive d'une autre manière, en lui passant 3 paramètres : le point de départ, le point d'arrivée et le plus grand index de point intermédiaire que l'on a le droit d'utiliser pour aller du départ à l'arrivée.

Le plus court chemin de source à dest n'utilisant que des points intermédiaires dont l'index ne dépasse pas inter correspond nécessairement à l'un des trois cas suivants :

• on utilise l'arc reliant directement source à dest.
• on passe par inter, en prenant le plus court chemin de source à inter puis le plus court chemin de inter à dest.
• on ne passe pas par inter, donc on prend le plus court chemin de source à dest n'utilisant que des points intermédiaires dont l'index ne dépasse pas inter-1.

On a toujours une fonction récursive, mais comme le point intermédiaire décrémente à chaque appel imbriqué, on est maintenant certain de ne pas tomber dans une boucle infinie : la récursion s'arrête lorsque inter atteint 0. Pour éviter de tester pour chaque valeur de inter la possibilité consistant à prendre directement l'arête source-dest, on ne fait le test que lorsque inter a atteint la valeur 0, c'est à dire que l'on ne peut plus du tout prendre d'arc intermédiaire.

Pour calculer le plus court chemin entre deux points source et dest, on appelle donc la fonction suivante, avec nbNoeuds comme valeur pour inter.

int distance[MAX_NOEUDS][MAX_NOEUDS];

int PlusCourtChemin(int source, int dest, int inter)
{
   if (inter == 0)
      return distance[source][dest];

   int distance1 = plusCourtChemin(source, inter, inter - 1) + plusCourtChemin(inter, dest, inter - 1);
   int distance2 = plusCourtChemin(source, dest, inter - 1);
   return min(distance1, distance2);
}

Cette fonction n'est plus infinie mais reste tout de même extrêmement lente : chaque appel à la fonction avec inter > 0, génère trois appels récursifs. Le nombre total d'appels à la fonction est donc de l'ordre de 3^N, ce qui est énorme.

Notre fonction a trois paramètres, dont chacun peut prendre nbNoeuds valeurs possibles. Au total, il y a donc au maximum nbNoeuds³ manières possibles d'appeler la fonction. Lors des 3^nbNoeuds appels décrits plus haut, une très grande partie correspond à des calculs déjà effectués. On peut donc éviter de les refaire, en stockant dans un tableau les résultats déjà calculés. On utilise un tableau à 3 dimensions, chaque dimension correspondant à un paramètre de la fonction. Le tableau contient la valeur -1 lorsque le calcul n'a jamais été fait. Il s'agit de ce que l'on appelle un algorithme dynamique.

int distance[MAX_NB_NOEUDS][MAX_NB_NOEUDS];
int dejaCalcule[MAX_NB_NOEUDS][MAX_NB_NOEUDS][MAX_NB_NOEUDS];

int plusCourtChemin(int source, int dest, int inter)
{
   if (inter == 0)
      return distance[source][dest];

   if (dejaCalcule[source][dest][inter] != -1)
      return dejaCalcule[source][dest][inter];

   int distance1 = plusCourtChemin(source, inter, inter - 1) + plusCourtChemin(inter, dest, inter - 1);
   int distance2 = plusCourtChemin(source, dest, inter - 1);
   int distanceMin = min(distance1, distance2);

   dejaCalcule[source][dest][inter] = distanceMin;
   return distanceMin;
}

Cette version est beaucoup plus rapide que la précédente, mais a un gros inconvénient : elle utilise une grande quantité de mémoire : nbNoeuds³ entiers, soit près de 4Go pour 1000 nœuds.

Toute cette mémoire n'est cependant pas nécessaire, si l'on remarque que pour calculer les valeurs des cases dont la troisième coordonnée est inter, on a uniquement besoin de connaître les résultats correspondant à des cases dont la troisième coordonnée est inter - 1 : chacun des trois appels récursifs se fait avec cette valeur comme troisième paramètre.

En utilisant cette propriété, on peut ainsi commencer par calculer toutes les cases dont la troisième coordonnée est 0, puis toutes les cases dont la troisième coordonnée est 1, etc. A tout moment, on n'a alors besoin de garder en mémoire que les valeurs des cases pour la troisième coordonnée précédente, et celles de la valeur courante.

Pour profiter de cette propriété, il faut donc commencer par écrire la solution de manière itérative, pour que les calculs soient faits valeur de inter par valeur de inter :

for (int inter = 0; inter < nbNoeuds; inter++)
   for (int dest = 0; dest < nbNoeuds; dest++)
      for (int source = 0; source < nbNoeuds; source++)
      {
          if (inter == 0)
             dejaCalcule[source][dest][0] = distance[source][inter] + distance[inter][dest];
          else
          {
             int dist1 = dejaCalcule[source][dest][inter - 1];
             int dist2 = dejaCalcule[source][inter][inter - 1] + dejaCalcule[inter][dest][inter - 1];
             dejaCalcule[source][dest][inter] = min(dist1, dist2);
          }
      }

Comme on n'a maintenant besoin que des cases de deux valeurs différentes de inter à tout moment, on peut utiliser un modulo 2 et réduire la troisième dimension à deux valeurs :

int dejaCalcule[MAX_NB_NOEUDS][MAX_NB_NOEUDS][2];

for (int C = 0; C < nbNoeuds; C++)
   for (int dest = 0; dest < nbNoeuds; dest++)
      for (int source = 0; source < nbNoeuds; source++)
      {
          if (inter == 0)
             dejaCalcule[source][dest][0] = distance[source][inter] + distance[inter][dest];
          else
          {
             int dist1 = dejaCalcule[source][dest][(inter - 1) % 2];
             int dist2 = dejaCalcule[source][inter][(inter - 1) % 2] + 
                         dejaCalcule[C][dest][(inter - 1) % 2];
             dejaCalcule[source][dest][inter % 2] = min(dist1, dist2);
          }
      }

On a alors un algorithme de complexité nbNoeuds³ en temps, et nbNoeuds² en mémoire.

Cet algorithme peut cependant être encore simplifié, si l'on stocke dans la même case le résultat pour inter, et le résultat pour inter - 1. En effet, on peut remarquer que pour les mêmes valeurs de source et de dest, la valeur pour le paramètre inter est toujours inférieure ou égale à la valeur pour C - 1. Si au lieu de stocker la valeur pour le paramètre inter dans une case séparée, on se contente d'écraser la valeur pour inter - 1, la valeur peut changer et ne plus représenter ce qui correspond aux paramètres source, dest et inter - 1, mais c'est toujours une distance possible de chemin entre source et dest qui ne peut être que meilleure. En écrasant la valeur au lieu de stocker séparément, on ne change donc pas le résultat final de l'algorithme.

Ceci permet de travailler directement dans le tableau distance, qu'il est alors inutile de recopier au départ :

for (int inter = 0; inter < nbNoeuds; inter++)
   for (int dest = 0; dest < nbNoeuds; dest++)
      for (int source = 0; source < nbNoeuds; source++)
          distance[source][dest] = min(distance[source][dest],
                               distance[source][inter] + distance[inter][dest]);

On n'a alors plus que trois boucles imbriquées, contenant une seule instruction. On obtient donc une manière très simple et très courte d'implémenter l'algorithme de Floyd-Warshall.

@josmiley

voici le résultat

0 12 10 23 22 29 23 30 42 40 40 50
12 0 25 11 13 20 35 42 43 33 31 41
10 25 0 28 12 19 13 20 32 30 30 40
23 11 28 0 16 9 24 31 32 22 20 30
22 13 12 16 0 7 22 29 30 20 18 28
29 20 19 9 7 0 15 22 23 13 11 21
23 35 13 24 22 15 0 7 19 17 26 36
30 42 20 31 29 22 7 0 12 10 19 29
42 43 32 32 30 23 19 12 0 10 19 29
40 33 30 22 20 13 17 10 10 0 9 19
40 31 30 20 18 11 26 19 19 9 0 10
50 41 40 30 28 21 36 29 29 19 10 0

0 12 10 23 22 29 23 30 42 40 40 50
12 0 22 11 13 20 35 42 43 33 31 41
10 22 0 28 12 19 13 20 32 30 30 40
23 11 28 0 16 9 24 31 32 22 20 30
22 13 12 16 0 7 22 29 30 20 18 28
29 20 19 9 7 0 15 22 23 13 11 21
23 35 13 24 22 15 0 7 19 17 26 36
30 42 20 31 29 22 7 0 12 10 19 29
42 43 32 32 30 23 19 12 0 10 19 29
40 33 30 22 20 13 17 10 10 0 9 19
40 31 30 20 18 11 26 19 19 9 0 10
50 41 40 30 28 21 36 29 29 19 10 0

-
Edité par Duncan4031 19 août 2024 à 20:54:05

effectivement, là ça devrait être bon, mais vu les extend je doute que ça passe niveau mémoire.

from sys import stdin

n,a = map(int,input().split())
c = list()
t = [{i:0} for i in range(n)]

for l in stdin.read().splitlines():
    i,j,l = map(int,l.split())
    i,j = i-1,j-1
    t[j][i] = t[i][j] = l
    c.extend(((i,j),(j,i)))
    
for i,j in c:
    for j2 in t[j]:
        if not j2 in t[i]:
            c.extend(((i,j2),(j2,i)))
            t[j2][i] = t[i][j2] = t[i][j] + t[j][j2]
        else:
            l = t[i][j] + t[j][j2]
            if l<t[i][j2]:
                t[j2][i] = t[i][j2] = l
                
for i in t:
    print(*[y for x,y in sorted(i.items())])

-
Edité par josmiley 19 août 2024 à 21:31:46

@josmiley

j'ai mis ton code dans une fonction car ça va plus vite

from sys import stdin

def main():
   n,a = map(int,input().split())
   c = list()
   t = [{i:0} for i in range(n)]
    
   for l in stdin.read().splitlines():
       i,j,l = map(int,l.split())
       i,j = i-1,j-1
       t[j][i] = t[i][j] = l
       c.extend(((i,j),(j,i)))
        
   for i,j in c:
       for j2 in t[j]:
           if not j2 in t[i]:
               c.extend(((i,j2),(j2,i)))
               t[j2][i] = t[i][j2] = t[i][j] + t[j][j2]
           else:
               l = t[i][j] + t[j][j2]
               if l<t[i][j2]:
                   t[j2][i] = t[i][j2] = l
                    
   for i in t:
       print(*[y for x,y in sorted(i.items())])
main()

explications de France IOI

def dedans(nbFois):
   for numFois in range(nbFois):
      print("Dedans")
nbFois = int(input())
for numFois in range(nbFois):
   print("Dehors")
   dedans(numFois)

def dedans(nbFois):
   for numFois in range(nbFois):
      print("Dedans")
 
def main():
   nbFois = int(input())
   for numFois in range(nbFois):
      print("Dehors")
      dedans(numFois)
 
main()

-
Edité par Duncan4031 19 août 2024 à 23:42:21

Je suppose que la version récursive décrite ci-haut serait encore plus longue.

Faudrait peut-être que je l'essaie en Rust.

Mon idée d'essayer les "array" ne semble pas bonne d'après les petits tests que j'ai fait.

Je vais gratter mes trois neurones pour essayer de trouver autre chose ...

j'ai l'impression que vous calculez l'ensemble de la matrice, alors qu'il suffirait d'en calculer que la moitié vue qu'elle est symétrique selon la diagonale [i,i]

ou je me trompe?

Elle est bien symétrique (vérifié par le programme lui-même), mais le calcul ne semble pas symétrique.

À suivre ...

edit:

Il semble que ça marche. C'est un peu moins optimisé, mais si on divise par deux le nombre de calculs, on devrait sauver beaucoup.

Et on ne fait pas de calcul pour la diagonale.

J'ai pris ma version sans fonction, mais la modification est facile.
Voici mon nouveau code:
-
# Lecture des paramètre et initialisation du graphe.
n, a = map(int, input().split())
graphe = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    graphe[i][i] = 0
# Lecture des sentiers et assignation dans le graphe.
for _ in range(a):
    u, v, w = map(int, input().split())
    graphe[u-1][v-1] = w
    graphe[v-1][u-1] = w
# Algorithme de Floyd-Warshall.
infini = float("inf")
for k in range(n):
    graphe_k = graphe[k]
    for i in range(n):
        graphe_i = graphe[i]
        graphe_ik = graphe_i[k]
        if graphe_ik == infini: continue
        for j in range(i+1,n):
            graphe_ikj = graphe_ik + graphe_k[j]
            if graphe_i[j] > graphe_ikj:
                graphe_i[j] = graphe_ikj
                graphe[j][i] = graphe_ikj
# Affichage des résultats.
for i in range(n):
    print(*graphe[i])
"""
for i in range(n):
    for j in range(i+1, n):
        if graphe[i][j] != graphe[j][i]: print(f"g[{i}]={graphe[i][j]}, g[{j}]={graphe[j][i]}")
"""

-
Edité par PierrotLeFou 27 août 2024 à 14:50:37

en l'ayant intégré dans une fonction

import sys

def main():
   # Lecture des paramètre et initialisation du graphe.
   n, a = map(int, input().split())
   graphe = [[float('inf')] * n for _ in range(n)]
   for i in range(n):
       graphe[i][i] = 0
   # Lecture des sentiers et assignation dans le graphe.
   for _ in range(a):
       #u, v, w = map(int, input().split())
       u, v, w = map(int,sys.stdin.readline().split())
       graphe[u-1][v-1] = w
       graphe[v-1][u-1] = w
   # Algorithme de Floyd-Warshall.
   infini = float("inf")
   for k in range(n):
       graphe_k = graphe[k]
       for i in range(n):
           graphe_i = graphe[i]
           graphe_ik = graphe_i[k]
           if graphe_ik == infini: continue
           for j in range(i+1,n):
               graphe_ikj = graphe_ik + graphe_k[j]
               if graphe_i[j] > graphe_ikj:
                   graphe_i[j] = graphe_ikj
                   graphe[j][i] = graphe_ikj
   # Affichage des résultats.
   for i in range(n):
       print(*graphe[i])
main()
"""
for i in range(n):
    for j in range(i+1, n):
        if graphe[i][j] != graphe[j][i]: print(f"g[{i}]={graphe[i][j]}, g[{j}]={graphe[j][i]}")
"""

voici le résultat des tests

ce qui est étonnant c'est au test 7 à 3.35s loin des 10s max et d'un coup au test 8 le programme est trop long ce qui veut dire qu'il dépasse les 10s