UVA Online Judge 10 000

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour, je souhaite m'inscrire à un concours d'algo (le Google Code Jam) donc je m'entraine sur UVA Online Judge. Je tente donc le premier exercice du module Contest Problems. Je vous laisse lire le sujet, je met en spoiler mon code ainsi que mon entrée.

Mon code (edit : code commenté):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <list>
#include <utility>
#include <map>
#include <string>
#include <vector>
#include <sstream>

using namespace std;

int main(void){
  int caseNumber = 1;
  unsigned int nbNodes;
  cin >> nbNodes;

  ostringstream out;

  while(nbNodes > 0){
      int start;

      cin >> start;
      int first, second;
      // From node to another
      map<int, vector<int>> adjancy;

      // Build the links
      do{
          cin >> first >> second;
          adjancy[first].push_back(second);
      }while(first != 0 && second != 0);


      // Length then node
      list<pair<int, int>> current;
      
      // initialise with the start
      current.push_front(make_pair(0, start));
      pair<int, int> max = *current.begin();


      while(!current.empty()){
          for(list<pair<int, int>>::iterator it = current.begin(); it != current.end(); /* */){

              int count = adjancy.count(it->second);

              // if there's no link from this node we delete it (or save if longer)
              if(count == 0){
                  if(it->first > max.first)
                      max = *it;
                  else if(it->first == max.first)
                      max = (it->second > max.second) ? max:*it;

                  it = current.erase(it);
              }
              else{
                  int size = adjancy[it->second].size();
                  
                  // we add a new pair for each links starting from the node minus 1
                  for(int i = 1; i < size; ++i){
                      current.push_back(make_pair(it->first + 1, adjancy[it->second][i]));
                  }
                  it->first++;
                  it->second = adjancy[it->second].front();
                  ++it;
              }
              
          }
      }

      cout << "Case " << caseNumber << ": The longest path from " << start << " has length " << max.first << " , finishing at " << max.second << "\n";

      ++caseNumber;
      cin >> nbNodes;
  }

  //cout << out.str();
  return 0;
}

Mon entrée (avec 25 noeuds et 32 liaisons) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
25
1
1 15
1 14
2 16
3 18
3 17
3 4
5 15
6 5
6 20
7 5
8 12
9 8
10 21
11 10
12 22
12 23
13 9
14 6
15 2
16 3
16 4
17 19
18 19
19 9
19 13
19 24
20 7
22 11
23 11
23 25
24 13
25 22
0 0
0

Si vous le faites tourner, vous aller voir que c'est assez lent, mais je n'arrive pas à savoir d'où ça vient… Du coup j'en appelle à votre générosité :p.

Édité par Ricocotam

+0 -0
Auteur du sujet

Ca marche ! :)

Le problème : Trouvez le plus long chemin en partant d'un point A

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Je pars du noeud numero A
J'ajoute (0, A) à la liste C des chemins courant où 0 désigne la longueur depuis le départ
et A le numero du noeud courant
J'initialise MAX = (0, A), où MAX désigne le chemin le plus long


Tant que C n'est pas vide
    Pour chaque T = (L, N) de C
        Si (aucun lien ne part de N)
            Si (T(L) > MAX(L))
                MAX = T
            Sinon Si (T(L) == MAX(L))
                Si (T(N) < MAX(N))
                    MAX = T
                FIN Si
            FIN Sinon Si
            On supprime T de C
        FIN Si
        SINON
            S = Nombre de Noeud partant de T
            A = Liste des Noeuds partant de T
            Pour i allant 1 à S - 1
                On ajoute le couple (T(L) + 1, A(i)) à C
            FIN Pour
            T = (T(L + 1), A(1))
        FIN Sinon
    FIN Pour
FIN Tant Que

Mais je pense avoir identifier le problème. J'utilise une liste doublement chainée, je pense qu'une file serait plus adaptée

edit : Même en utilisant une queue cela reste trop lent pour leur test..

Édité par Ricocotam

+0 -0

Salut,

En fait, ça aurait été plus simple si tu avais expliqué l'idée de ton algo dans les grandes lignes (et quelques complexités éventuellement, si tu les connais) plutôt que le pseudo-code qui est finalement quasiment identique à ton code original.

Pour ce qui est de ton algo, sauf erreur, je n'ai pas vu de condition pour arrêter d'ajouter des gens dans ta file autre que « j'ai déjà tous les gens de ma file » ou « rien ne part du nœud courant ». À partir de là, il me semble que rien ne te permet de contrôler le nombre de fois que tu vas passer par un nœud ; on pourrait imaginer un exemple dans lequel tu passes un nombre de fois exponentiel par chaque nœud (exemple d'un DAG avec des nœuds qui se séparent puis se rejoignent, multipliant à chaque fois par 2 le nombre de parcours des nœuds qui suivent).

Est-ce que tu pourrais donc clarifier ton idée d'algo, éventuellement l'expliquer, de manière à comprendre pourquoi il est aussi lent ?

Auteur du sujet

Je crois que tu as mis le doigt sur mon problème !

En fait, je parcours les noeuds un à un. Si plusieurs liens partent de ce noeuds je cré autant de paire qu'il y a de noeud - 1. S'il n'y a pas de liens qui partent, je supprime la paire. Je sauvegarde au fur et a mesure le chemin le plus long

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte