Discussion :

[Asphator]

Bonjour,

Je suis bloqué sur une épreuve d'algorithmie

Contrairement à d'autres épreuves, celle-ci n'a pas de section d'aide spécifique, raison pour laquelle je me permets de poster ici.

En terme de complexité, je ne pense pas pouvoir vraiment l'améliorer et ce n'est pas mon objectif. Je passe les derniers tests (les plus "consommateurs") sans aucun soucis (moins de 0.06s).
En revanche, il retourne un résultat faux dans certains cas et je n'ai pas accès aux traces de debug pour savoir quels sont ces cas. Les cas lors desquels il plante comportent plus de 1000 entrées, c'est tout ce que je sais.
Peut-être pouvez-vous m'aider dans mon analyse pour savoir à quel endroit mon algo se plante et quels cas de figures j'ai omis ou mal implémenté?
(je précise, une code avec la solution ne m'intéresse pas, c'est vraiment comprendre ce qui est mauvais dans mon algo qui m'importe)

Résumé:
- input:
--- 1ère ligne: N, un nombre d'intervalles
--- N lignes suivantes: X et Y séparés par un espace, respectivement borne minimale et maximale de l'intervalle
- output:
--- le plus grand nombre d'intervalles contenus dans un seul et même autre

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// --- Algorithm ----
// We sort coats by 'min' then by 'max'. Once sorted, we just have to iterate once through them.
// c: number of previous elements with same 'min'
// r: reference -> last largest item. if x>r.x && y>r.y, we switch ref
// s: sum -> equals c if new ref, else is incremented
// max: equals the biggest 's'
// You can add the line below at the end of the FOR loop for debug:
//        cout << c << " : " << r << " : " << s << " : " << max << endl;
// --- Example ------
// >> Input:
// 12
// 2 6
// 5 7
// 1 4
// 9 10
// 6 10
// 4 9
// 5 6
// 5 6
// 2 9
// 5 9
// 2 3
// 6 8
// >> Expected output:
// 8
// >> Description:
// Coat   c   r    s  max
// ----- --- ---- --- ---      0  1  2  3  4  5  6  7  8  9  10
// {1;4}  0 : 0  : 0 : 0       .  |========|  .  .  .  .  .  .
// {2;3}  0 : 0  : 1 : 0       .  .  |==|  .  .  .  .  .  .  .
// {2;6}  1 : 2  : 1 : 1       .  .  |===========|  .  .  .  .
// {2;9}  2 : 3  : 2 : 1       .  .  |====================|  .
// {4;9}  0 : 3  : 3 : 1       .  .  .  .  |==============|  .
// {5;6}  0 : 3  : 4 : 1       .  .  .  .  .  |==|  .  .  .  .
// {5;6}  1 : 3  : 5 : 1       .  .  .  .  .  |==|  .  .  .  .
// {5;7}  2 : 3  : 6 : 1       .  .  .  .  .  |=====|  .  .  .
// {5;9}  3 : 3  : 7 : 1       .  .  .  .  .  |===========|  .
// {6;8}  0 : 3  : 8 : 1       .  .  .  .  .  .  |=====|  .  .
// {6;10} 1 : 10 : 1 : 8       .  .  .  .  .  .  |===========|
// {9;10} 0 : 10 : 2 : 8       .  .  .  .  .  .  .  .  .  |==|
// ----------------------
// Result: 8
 
struct Coat {
   int min;
   int max;
 
   bool operator<(const Coat& c) const {
      return (min<c.min || (min==c.min && max<c.max));
   }
};
 
int main() {
   int nbCoats, c=0, r=0, s=0, max=0;
   vector<Coat> stock(0);
 
   // --- Get inputs
   cin >> nbCoats;
 
   for (int i=0; i<nbCoats; ++i) {
      Coat c;     
      cin >> c.min;
      cin >> c.max;    
      stock.push_back(c);
   }
 
   // sort by 'min', then by 'max'
   sort(stock.begin(), stock.end());
 
   // --- Analyze stock
   for (int i=1; i<nbCoats; ++i) {
      if (stock[i].min == stock[i-1].min) {
         ++c;
         if (stock[i].max > stock[r].max) {
            if (s > max) {
               max = s;
            }
            r=i;
            s=c;
         } else {
            ++s;
         }
      } else {
         c=0;
         if (stock[i].max <= stock[r].max) {
            ++s;
         } else {
            if (s > max) {
               max = s;
            }
            r=i;
            s=c;
         }
      }
   }
   if (s > max) {
      max=s;
   }
 
   // --- Display result
   cout << max;
}

Merci à ceux qui se pencheront sur le problème
Cordialement

[tbc92]

Au début de ton algorithme, tu commences par un tri sur min, max ...
C'est bizarre. En triant sur min, on a l'impression que tu veux mettre en début de ta liste les manteaux avec la plus forte amplitude, mais en triant sur max, on a l'impression que tu veux mettre en fin de ta liste les manteaux avec la plus forte amplitude.
Un tri sur (min, -max) serait plus cohérent

Et pour être honnête, j'aurais même calculé l'amplitude max-min pour chaque manteau, et j'aurais fait un tri sur cette colonne. Là, on aurait eu une bonne base pour travailler.

[pseudocode]

J'ai l'impression que ton algo à un scope trop limité: le dernier "grand" intervalle rencontré devient la nouvelle référence "r", et les anciens "grands" intervalles son oubliés par l'algo.

Ce qui pose problème si les futurs "petits" intervalles sont toujours inclus dans le premier "grand" intervalle.

0  1  2  3  4  5  6  7  8  9  10
|==============|  .  .  .  .  . 
.  |==|  .  .  .  .  .  .  .  . 
.  |==|  .  .  .  .  .  .  .  . 
.  |==============|  .  .  .  . 
.  .  |==|  .  .  .  .  .  .  . 
.  .  |==|  .  .  .  .  .  .  . 
.  .  |==============|  .  .  . 
.  .  .  |==|  .  .  .  .  .  . 
.  .  .  |==|  .  .  .  .  .  . 
.  .  .  |==============|  .  . 
.  .  .  .  |==|  .  .  .  .  . 
.  .  .  .  |==|  .  .  .  .  . 

[Asphator]

Effectivement, sur le dernier exemple, c'est flagrant.
Soit je dois modifier le fond de mon algo, soit si j'en garde le principe, je dois gérer une liste de références qui restes actifs tant que leur borne max est supérieure à la borne min en cours..
Je vais revoir ça, ça me débloque pour le moment.
Merci à vous

[pseudocode]

Effectivement, tu peux créer une pile des références visibles. Lors du parcourir de ta liste triée, tu mets à jour tous les éléments présents dans la pile, en supprimant de la pile ceux qui ne sont plus atteignables.

Toute ressemblance avec un garbage-colllector ne serait peut-être pas si fortuite que cela.

[anapurna]

salut

Quand on lit l'énoncé c'est pourtant claire ^^
je crois que tu t'est compliqué la vie avec tes conditions

je pense qu'il faut que tu test tout tes éléments par rapport à la référence

pour moi le premier test devrait être

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
    if (stock[i].min == stock[r].min)  // dans la première boucle r=0 dans les suivante on compare avec la reference
    { ++c; } // number of previous elements with same 'min'
    else 
    { c=0; }

ensuite ton changement de référence la tu ne respecte pas ce qu'il te disent dans l’énonce

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
   if ((stock[i].min > stock[r].min) && (stock[i].max > stock[r].max))  // switch ref
   {  r = i;  // new ref
      s = c;  // sum -> equals c if new ref 
               // en fait c=0 car le test précédent n'est pas vrai 
   }
   else
     s++; //else is incremented

et au final de ta boucle quelque soit la référence

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
  if (s > max) 
    max = s;  // max: equals the biggest 's'

mes deux cents