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

[phryte]

Bonjour,

Je propose une solution (non optimisée en temps de calcul) sous Matlab. Il y a sûrement une équivalence C.
La solution binaire peut peut-être t'aider.

Code matlab :

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
% Choisir son manteau
% T : Table des manteaux
% Niveaux : Résultat 
%   Niveaux(:,1) = Numéro du manteau
%   Niveaux(:,2) = Niveau maximal du manteau
clear
A=zeros(8,8);
T(1,:)=[1 1 1 0 0 0 0 0];
T(2,:)=[0 1 1 1 1 0 0 0];
T(3,:)=[0 0 0 0 1 1 1 1];
T(4,:)=[0 0 1 1 1 1 0 0];
T(5,:)=[0 1 1 1 1 0 0 0];
T(6,:)=[0 0 1 1 1 1 1 1];
T(7,:)=[0 0 1 1 1 1 0 0];
T(8,:)=[0 0 1 1 1 1 1 1];
Niveaux(:,1)=1:8;
for m=1:8
    c=0;
for n=1:8
    if or(T(m,:),T(n,:))==T(m,:)
       Niveaux(m,2)=c;
       c=c+1;
    end
end
end
display('Résultat : ')
Niveaux

Résultat :
Niveaux =

1 0
2 1
3 0
4 1
5 1
6 4
7 1
8 4

[tbc92]

@phryte,
L'énoncé disait : 0 < temperature_inf < temperature_sup < 500000 ( et a priori, considérons que température_inf et température_sup sont des entiers)
Dans ton algorithme, tu as mis 8 en dur. Mais ce nombre 8 serait à remplacer par 500000. C'est bien ça ?

Et donc on conclue : bof.

[phryte]

Bonjour,

OK pour ta remarque tbc92. J'ai pris seulement l'exemple de la page d'épreuve.

[pseudocode]

Code auto-explicatif

Struct Interval
  int min, max
  int count=0
End Struct

List<Interval> input = {2,6}, {5,7}, {1,4}, {9,10}, ...
List<Interval> stack = empty

Sort(input)

For each E in input
  For each S in stack
    if (S includes E) S.count++
    if (E includes S) E.count++
    if (S.max < E.min) stack.remove(S)
  Next S
  stack.add(E)
Next E

Solution = Max(input.count)

[tbc92]

Voici un algorithme en 2*n* log(n)

manteau est une structure
temperature_mini est un entier
temperature_maxi est un entier
rang_temperature_mini est un entier
rang_temperature_maxi est un entier
amplitude est un entier
fin

Etape 1 : Classer mes manteaux selon temperature_mini
Etape 2 : Calculer rang_temperature_mini pour chaque manteau, en gérant les ex-aequo (0 pour le(s) manteau(x) qui a la température mini la plus basse)
Etape 3 : Classer mes manteaux selon temperature_maxi
Etape 4 : Calculer rang_temperature_maxi pour chaque manteau, en gérant les ex-aequo (0 pour le(s) manteau(x) qui a la température maxi la plus haute)
Etape 5 : Calculer amplitude pour chaque manteau. amplitude = nbre_manteaux - rang_temperature_mini - rang_temperature_maxi
Etape 6 : Le manteau avec l'amplitude la plus grande est le manteau voulu, et pour ce manteau, amplitude est l'indicateur demandé.

Les étapes 4.5.6 sont en fait une et une seule étape ...

[pseudocode]

Etape 5 : Calculer amplitude pour chaque manteau. amplitude = nbre_manteaux - rang_temperature_mini - rang_temperature_maxi
Etape 6 : Le manteau avec l'amplitude la plus grande est le manteau voulu, et pour ce manteau, amplitude est l'indicateur demandé.

0  1  2  3  4  5  6  7  8  9  10
|=====|  .  .  .  .  .  .  .  .  --> MinRank=0, MaxRank=2, amplitude=10-2=8
.  |==========================|  --> MinRank=1, MaxRank=0, amplitude=10-1=9
.  |=====|  .  .  .  .  .  .  .  --> MinRank=1, MaxRank=1, amplitude=10-2=8
|==|  .  .  .  .  .  .  .  .  .  --> MinRank=0, MaxRank=3, amplitude=10-3=7
|==|  .  .  .  .  .  .  .  .  .  --> ...
|==|  .  .  .  .  .  .  .  .  .
|==|  .  .  .  .  .  .  .  .  .
|==|  .  .  .  .  .  .  .  .  .
|==|  .  .  .  .  .  .  .  .  .
|==|  .  .  .  .  .  .  .  .  .

[tbc92]

Non Pseudocode,
Peut-être que uand je dis 'avec gestion des ex-aequo', ce n'est pas assez clair.
Ici, sur la colonne 'temp-mini', il y a 7 manteaux avec température_mini = 0.
Sans gestion des ex-aequo, ces 7 manteaux auraient les rangs de 0 à 6 ; avec gestion des ex-aequo, ils ont tous les 7 le rang 0. Ok là dessus.

Mais pour les suivants :
2 manteaux ont pour température-mini 1.
Sans gestion des ex-aequo, ces 2 manteaux auraient les rangs 7 et 8 ; avec gestion des ex-aequo, ils ont tous les 2 le rang 7. Mais pas tous les 2 le rang 1 comme tu l'écris.

En d'autres mots :

Code :

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

1
2
3
4
5
6
rang = 0
tableau[0].rang = 0
Pour i = 1 a n-1
  si tableau[i].temperature  > tableau[i-1].temperature alors rang = i
  tableau[i].rang = rang
fin

[pseudocode]

Sans gestion des ex-aequo, ces 2 manteaux auraient les rangs 7 et 8 ; avec gestion des ex-aequo, ils ont tous les 2 le rang 7. Mais pas tous les 2 le rang 1 comme tu l'écris.

Ah.. ok.

Tes invariants sont:
* Pour un Intervalle K, le "MinRank" donne le nombre d'intervalles qui commencent strictement avant K (et donc ne sont pas inclus dans K)
* Pour un Intervalle K, le "MaxRank" donne le nombre d'intervalles qui finissent strictement après K (et donc ne sont pas inclus dans K non plus).

=> La valeur "Total-MinRank-MaxRank" approxime le nombre d'intervalles qui ne sont pas exclus = le nombre d'intervalles inclus => la solution du problème.

Je dis "approxime" car dans le cas d'un intervalle inclus dans un autre, on supprime deux fois l'intervalle englobant (il commence avant ET il termine après).
Par contre, cette valeur est exacte si l'intervalle n'est PAS inclus dans un autre.

Et dans le cas du problème actuel, comme on s'intéresse à l'intervalle le plus englobant, la valeur est exacte.

[tbc92]

Tout à fait, tu as parfaitement expliqué pourquoi ça marche sur ce manteau là, et pas forcément sur les autres.

[dividee]

Une variante de cet algo, en Python:

Code python :

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

1
2
3
4
5
6
7
8
9
10
11
import sys
n = int(sys.stdin.readline())
M = [tuple(map(int, sys.stdin.readline().split())) for i in range(n)]
 
M.sort(key=lambda m:(m[0],-m[1]))
Rmin = {m:i for i,m in reversed(list(enumerate(M)))}
 
M.sort(key=lambda m:(m[1],-m[0]))
Rmax = {m:i for i,m in enumerate(M)}
 
print(max(Rmax[m]-Rmin[m] for m in M))

Rmin(m) = le nombre de manteaux qui commencent avant m, ou qui commencent à la même température que m mais ne sont pas inclus dans m (ce deuxième nombre devant être 0 pour le manteau recherché).
Rmax(m) = le nombre de manteaux qui se terminent avant la fin de m, ou qui se terminent à la même température que m et sont inclus dans m.

Rmax(m) - Rmin(m) est le nombre de manteaux contenus dans m, ssi m n'est contenu dans aucun autre manteau (sauf des doublons), ou inférieur sinon.