Bonjour,

Je suis en train d'essayer de progresser et d'améliorer mon Python après quelques années sans pratiquer sur France ioi. J'ai réussi à faire le niveau 4 quasiment en entier, il ne me reste que cet exo pour passer au niveau 5. 

En voici l'énoncé :

Limites de temps et de mémoire (C++)

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

Contraintes

Entrée

Sortie

##Entrée des données du problème    
from sys import setrecursionlimit
MAX_VALEURS=200*2000
setrecursionlimit(MAX_VALEURS + 50)#pour éviter que cela ne boucle indéfiniment
nbarbre,nbquestion = map(int,input().split())
tableau_arbre=[]
for i in range(nbarbre):
    coordX,coordY,longueur=map(int,input().split())
    tableau_arbre+=[[coordX,coordY,longueur,False]]
reservoir=tableau_arbre #car on va modifier les attributs False en True a chaque passage dans la boucle



    
##Fonction main = fonction marquer       
   
def fonction_marquer(arbre_demande):

    compteur=0
        
        
        
    compteur=ProcedureDFS(tableau_arbre,arbre_demande)
    print(compteur)
    
##Fonction de parcours en profondeur
def ProcedureDFS(tableau_arbre,arbre_demande): 
    global compteur
   
    tableau_arbre[arbre_demande][3]=True
    
    compteur+=1
   
    for V in range(nbarbre):
        distance_euclidienne=((tableau_arbre[arbre_demande][0]-tableau_arbre[V][0])^2+(tableau_arbre[arbre_demande][1]-tableau_arbre[V][1])^2)
        longueur_au_carre=tableau_arbre[arbre_demande][2]^2
       
        if not tableau_arbre[V][3] and distance_euclidienne<=longueur_au_carre:
            ProcedureDFS(tableau_arbre, V)  
    return compteur
#Exécution du script

for i in range(nbquestion):
    compteur=0
    arbre_demande=int(input())
    fonction_marquer(arbre_demande)
    tableau_arbre=reservoir

-
Edité par Tym35scky 31 mars 2020 à 15:30:54

Bonjour, merci beaucoup pour ce lien.

J'ai donc modifié mon script en prenant en compte ce que j'avais compris dans vos posts. J'ai donc utilisé un DFS récursif puis itératif et j'ai convertis les données de l’exercice en liste d'adjacence. Cela réussit l'exemple et passe un test en Python sur France ioi. Pour le reste c'est trop lent.

Je vous mets mon code à la fin.

Comme je n'ai pas de formation en informatique avancée (je fais des mesures hydrologiques) je me permets de vous poser des questions que vous trouverez peut-être idiotes :

Pour la partie algorithme de parcours :

Comme je disais j'ai utilisé un DFS itératif mais vous avez proposé d'utiliser l'algorithme de Tarjan pour chercher les composantes fortement connexes. Est ce que c'est vraiment nécessaire ? Python possède dans ses packages la fonction tarjan() mais je n'arrive pas vraiment à voir quelle est la stucture de données à lui rentrer puisque je n'ai pas le script, en tout cas pas de liste ni de liste de liste.

Aussi j'ai demandé de l'aide dans le forum de France ioi mais à aucun moment ils ne me parlent de cet algorithme. Donc je me demandais si ma complexité temporelle trop grande n'était pas due au fait que j'utilise des listes de listes. 

Vous avez dit que :

C'est d'ailleurs ce qui se passe avec la liste de listes, on ne fait jamais un G[i][j] qui est (relativement) lent (__getitem__ a un coût).

Donc je me demandais quoi utiliser à la place pour appeler G[i][j] sans faire un __getitem__ ?

##Creation du graphe 
nbarbre,nbquestion = map(int,input().split())
tableau_arbre=[]
for i in range(nbarbre):
    coordX,coordY,longeur=map(int,input().split())
    tableau_arbre+=[[coordX,coordY,longeur]]
Graphe_arbre=[[] for i in range(nbarbre)]
for l in range(nbarbre):
    for k in range(nbarbre):
        distance_euclidienne=(tableau_arbre[l][0]-tableau_arbre[k][0])**2+(tableau_arbre[l][1]-tableau_arbre[k][1])**2
        
        longueur_au_carre=(tableau_arbre[l][2])**2
        
        if distance_euclidienne<=longueur_au_carre:
            Graphe_arbre[l]+=[(k)]

##DFS sur ce graphe 
def dfs_iterative(graph, start):
    stack, path = [start], []

    while stack:
        vertex = stack.pop()
        if vertex in path:
            continue
        path.append(vertex)
        for neighbor in graph[vertex]:
            stack.append(neighbor)

    return len(path)
   




         
## Execution du script
for i in range(nbquestion):
    arbre_demande=int(input())
    visited = []
    taille=dfs_iterative(Graphe_arbre, arbre_demande)
    print(taille)

Bonne journée

Voila le lien 

http://www.france-ioi.org/algo/task.php?idChapter=535&idTask=1011

Pour le moment je ne passe qu'un test sur 12 

Les intervenants du forum m'ont donné quelques indices : utiliser un tableau de booléen et prendre en compte le fait que l'on fasse 2000 requêtes pour 200 arbres donc je vais essayer de stocker mes réponses dans une liste. Normalement cela devrait suffire. J'ai un peu de travail donc je ferais cela surement demain.

Bonne soirée !

Tym35scky a écrit:

http://www.france-ioi.org/algo/task.php?idChapter=535&idTask=1011

Salut, comme c'est le niveau 4 je pense qu'il faut que tu sois sur un compte qui y a accès (peut-être as-tu plusieurs compte sur France ioi). Sinon il est dans la rubrique Graphe implicite du niveau 4 et c'est le dernier de la liste.

Bref ce n'est pas grave si tu n'y a pas accès car j'ai réussi à avancer sur ce problème et j'y suis au stade où seul le test n1 ne passe pas. Tu avais émis l'idée d'aller chercher des composantes fortement connexes grâce à l'algorithme de Tarjan donc je suis allée le chercher dans le module de Python correspondant. J'arrive à en extraire les partitions correspondant aux composantes fortement connexes mais j'ai un problème de logique dans le marquage des points que j'ai visité (et donc qui ne nécessite par de tester l'algorithme à priori)

(Je mets le code à la fin pour illustrer)

Explication : Je commence par chercher si l'arbre qu'on me propose est dans une partition d'arbre fortement connexe. Si oui je note comme visitée toute la partition. Puis je recherche dans tous les voisins de cet arbre ceux qui ne sont pas visités et je recommence la procédure à partir d'eux. 

Le problème c'est que en fonction d'où je pars il y aura des arbres qui ne seront pas marqués comme visités alors qu'en réalité ils le devraient. En effet, la partition fortement connexe étant déjà marquée comme true je n'aurai pas accès aux arbres qui sont juste connexes et pas fortement connexe. C'est dommage parce en fait ça me permet d'avoir le test numéro 1 qui fonctionne.

Donc ma question est : comment utiliser ces composantes sans devoir aller vérifier si les voisins de chacune d'entre elles ont été visités ou pas ? (j'ai mis la fonction dfs modifiée qui fait ça après) Parce que pour le coup c'est trop lent.

Code utilisé : (les 137 premières lignes c'est juste le copié collé du module tarjan de python car france ioi ne l'a pas de base)

from collections import namedtuple
__all__ = ['tarjan',
           'tarjan_iter',
           'tarjan_recursive']
""" Context used to implement the algorithm without recursion in @tarjan
    and @tarjan_iter """
TarjanContext = namedtuple('TarjanContext',
                                ['g',           # the graph
                                 'S',           # The main stack of the alg.
                                 'S_set',       # == set(S) for performance
                                 'index',       # { v : <index of v> }
                                 'lowlink',     # { v : <lowlink of v> }
                                 'T',           # stack to replace recursion
                                 'ret'])        # return code
def _tarjan_head(ctx, v):
        """ Used by @tarjan and @tarjan_iter.  This is the head of the
            main iteration """
        ctx.index[v] = len(ctx.index)
        ctx.lowlink[v] = ctx.index[v]
        ctx.S.append(v)
        ctx.S_set.add(v)
        it = iter(ctx.g.get(v, ()))
        ctx.T.append((it,False,v,None))
def _tarjan_body(ctx, it, v):
        """ Used by @tarjan and @tarjan_iter.  This is the body of the
            main iteration """
        for w in it:
                if w not in ctx.index:
                        ctx.T.append((it,True,v,w))
                        _tarjan_head(ctx, w)
                        return
                if w in ctx.S_set:
                        ctx.lowlink[v] = min(ctx.lowlink[v], ctx.index[w])
        if ctx.lowlink[v] == ctx.index[v]:
                scc = []
                w = None
                while v != w:
                        w = ctx.S.pop()
                        scc.append(w)
                        ctx.S_set.remove(w)
                ctx.ret.append(scc)
def tarjan_iter(g):
        """ Returns the strongly connected components of the graph @g
            in a topological order.
                @g is the graph represented as a dictionary
                        { <vertex> : <successors of vertex> }.
            This function does not recurse.  It returns an iterator. """
        ctx = TarjanContext(
                g = g,
                S = [],
                S_set = set(),
                index = {},
                lowlink = {},
                T = [],
                ret = [])
        main_iter = iter(g)
        while True:
                try:
                        v = next(main_iter)
                except StopIteration:
                        return
                if v not in ctx.index:
                        _tarjan_head(ctx, v)
                while ctx.T:
                        it, inside, v, w = ctx.T.pop()
                        if inside:
                                ctx.lowlink[v] = min(ctx.lowlink[w],
                                                        ctx.lowlink[v])
                        _tarjan_body(ctx, it, v)
                        if ctx.ret:
                                assert len(ctx.ret) == 1
                                yield ctx.ret.pop()
def tarjan(g):
        """ Returns the strongly connected components of the graph @g
            in a topological order.
                @g is the graph represented as a dictionary
                        { <vertex> : <successors of vertex> }.
        
            This function does not recurse. """
        ctx = TarjanContext(
                g = g,
                S = [],
                S_set = set(),
                index = {},
                lowlink = {},
                T = [],
                ret = [])
        main_iter = iter(g)
        while True:
                try:
                        v = next(main_iter)
                except StopIteration:
                        return ctx.ret
                if v not in ctx.index:
                        _tarjan_head(ctx, v)
                while ctx.T:
                        it, inside, v, w = ctx.T.pop()
                        if inside:
                                ctx.lowlink[v] = min(ctx.lowlink[w],
                                                        ctx.lowlink[v])
                        _tarjan_body(ctx, it, v)
def tarjan_recursive(g):
        """ Returns the strongly connected components of the graph @g
            in a topological order.
                @g is the graph represented as a dictionary
                        { <vertex> : <successors of vertex> }.
                        
            This function recurses --- large graphs may cause a stack
            overflow. """
        S = []
        S_set = set()
        index = {}
        lowlink = {}
        ret = []
        def visit(v):
                index[v] = len(index)
                lowlink[v] = index[v]
                S.append(v)
                S_set.add(v)
                for w in g.get(v,()):
                        if w not in index:
                                visit(w)
                                lowlink[v] = min(lowlink[w], lowlink[v])
                        elif w in S_set:
                                lowlink[v] = min(lowlink[v], index[w])
                if lowlink[v] == index[v]:
                        scc = []
                        w = None
                        while v != w:
                                w = S.pop()
                                scc.append(w)
                                S_set.remove(w)
                        ret.append(scc)
        for v in g:
                if not v in index:
                        visit(v)
        return ret
import sys
input=sys.stdin.readline
def main():
    #Creation du graphe
    nbarbre,nbquestion = map(int,input().split())
    tableau_arbre=[]
    for i in range(nbarbre):
        coordX,coordY,longeur=map(int,input().split())
        tableau_arbre+=[[coordX,coordY,longeur]]
    Graphe_arbre=[[] for i in range(nbarbre)]
    for l in range(nbarbre):
        for k in range(nbarbre):
            distance_euclidienne=(tableau_arbre[l][0]-tableau_arbre[k][0])**2+(tableau_arbre[l][1]-     tableau_arbre[k][1])**2
        
            longueur_au_carre=(tableau_arbre[l][2])**2
        
            if distance_euclidienne<=longueur_au_carre:
                Graphe_arbre[l]+=[(k)]
    #creation du dictonnaire
    dico={}
    for i in range(len(Graphe_arbre)):
        dico[i]=Graphe_arbre[i]
    
    #utilisation du dico dans l'algorithme de tarjan
    
    composante_fortement_connexe=tarjan(dico)
    #DFS sur ce graphe en utilisant les résultats de tarjan
    def dfs(G,arbre,visite):
        #visite[arbre]=True #mark the traversed node
        for l in range(len(composante_fortement_connexe)):
            if arbre in composante_fortement_connexe[l]:
                for k in composante_fortement_connexe[l]:
                    visite[k]=True
            
        
        
        for neighbour_nodes in G[arbre]: #take a neighbouring node
            if not visite[neighbour_nodes]: #condition to check whether the neighbour node is already visited
                
                dfs(G,neighbour_nodes,visite) #recursively traverse the neighbouring node
        
        return visite
    Liste_question_posee=[False]*nbarbre
    Stockage_des_reponses=[[] for i in range(nbarbre)]
         
    # Execution du script
    for i in range(nbquestion):
        arbre_demande=int(input())
        if Liste_question_posee[arbre_demande]:
            
            print(Stockage_des_reponses[arbre_demande])
        
            
        else:
            visite = [False]*nbarbre
            
            taille=dfs(Graphe_arbre, arbre_demande,visite)
            compteur=0
            for i in range(nbarbre):
                if visite[i]:
                    compteur+=1
            print(compteur)
            Stockage_des_reponses[arbre_demande]=compteur
            Liste_question_posee[arbre_demande]=True
      
        
main()

fonction dfs modifiée:

 def dfs(G,arbre,visite):
        #visite[arbre]=True #mark the traversed node 
        for l in range(len(composante_fortement_connexe)):
            if arbre in composante_fortement_connexe[l]:
                for k in composante_fortement_connexe[l]:
                    visite[k]=True
                for connexe in composante_fortement_connexe[l]:
                    for neighbour_nodes in G[connexe]: #take a neighbouring node 
                        if not visite[neighbour_nodes]: #condition to check whether the neighbour node is already visited
                
                            dfs(G,neighbour_nodes,visite) #recursively traverse the neighbouring node
            
        
        return visite

-
Edité par Tym35scky 5 avril 2020 à 12:31:55

-
Edité par PascalOrtiz 5 avril 2020 à 16:00:33

ClovisPa a écrit:

Bonjour, désolé de reparler de ce sujet 3 ans plus tard, mais j'ai un problème sur cet exercice.

J'ai donc exécuté le code évoqué plus haut, mais pour les tests 1 et 3, l'évaluateur affiche ceci : Votre programme a dépassé la limite de temps : il est trop lent ou bien boucle indéfiniment. - Score total : 83%

Je ne comprends pas pourquoi cela arrive pour ceux-ci, et pas pour les autres. Si vous pouviez me donner la solution, ce serait parfait !

Bonne journée, 

Clovis

Je pense avoir expliqué le problème dans ce message. 

EDIT On peut accéder et tester le problème ici. L'algo attendu est un bête DFS mais ça ne passera pas en Python (ça passera en C++, cf. leur corrigé). Avec l'algo de Tarjan (optimal et bien plus compliqué à écrire), ça passe en Python, temps maximal en 0.24 s au test n°1. Il faut leur dire de ne pas mettre le même temps à C++ et Python (je leur ai dit, sans réaction de leur part).

Le code suivant implémente l'algo naïf (celui attendu) et passe 11 tests sur 12 :

def dfs(G,i):
    visited=[0]*len(G)

    visited[i] = True
    to_visit = [i]
    while to_visit:
        u = to_visit.pop()
        for v in G[u]:
            if not visited[v]:
                visited[v] = True
                to_visit.append(v)
    return sum(visited)

def build_graph(L):
    n=len(L)
    G=[[] for _ in range(n)]
    for i in range(n):
        xA, yA, rA=L[i]  
        for j in range(n):
            if i!=j:
                xB, yB, _=L[j]
                dd=(xA-xB)**2+(yA-yB)**2
                if dd<=rA*rA:
                    G[i].append(j)

    return G

def capture():
    N, M=map(int, input().split())
  
    L=[tuple(int(z) for z in input().split()) for i in range(N)]
    queries=[int(input()) for _ in range(M)]
    return L, queries
def solve():
    L, queries=capture()
    n=len(L)
    G=build_graph(L)
    C=[dfs(G,i) for i in range(n)]
    for i in queries:
        print(C[i])


solve()

-
Edité par PascalOrtiz 14 février 2023 à 18:24:55