Problème du choix de manteau (IOI)
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:
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
Problème du choix du manteau
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:
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
