Discussion :

[Metogon]

Bonjour, je n'arrive pas à résoudre ce problème.

Mon algo ne passe que 2 test, les autres il est faux et trop lent... Merci d'avance


---------------------


Choisir un manteau pour les vacances est toujours difficile, surtout lorsque l'on ne sait pas encore où l'on part. En effet chaque manteau est adapté à une certaine plage de température et vous aimeriez bien choisir un manteau qui s'adaptera à vos besoins.

Vous voilà dans un vaste magasin de manteaux, un peu perdu dans l'énorme choix proposé. Pour chacun des manteaux du magasin, vous connaissez l'intervalle de température qui lui correspond.

Avec votre logique impassible, vous décidez d'inventer un critère qui vous aidera à choisir votre manteau : Le niveau d'un manteau sera défini comme le nombre d'autres manteaux du magasin dont l'intervalle de température est contenu dans l'intervalle de celui-ci.

Vous décidez de sortir votre ordinateur et d'écrire un programme qui déterminera le niveau maximal que l'on peut trouver.

LIMITES DE TEMPS ET DE MEMOIRE (Langage : Java)

Temps : 0.5s sur une machine à 1Ghz.
Mémoire : 8000 Ko.

CONTRAINTES

1 <= nbManteaux <= 20 000.
0 <= temperature_inf, temperature_sup <= 500 000 000, l'intervalle de température d'un manteau.

ENTRÉE

Sur la première ligne de l'entrée, votre programme lira un unique entier : nbManteaux, le nombre de manteaux du magasin.

Il lira ensuite nbManteaux lignes contenant chacune deux entiers indiquant l'intervalle de température d'un manteau.

SORTIE

Votre programme affichera un unique entier : le niveau maximal d'un manteau.

EXEMPLE

entrée :
8
1 3
2 5
5 8
3 6
2 5
3 8
3 6
3 8

sortie :
4

COMMENTAIRES

Dans l'exemple présenté, les niveaux des manteaux sont, dans l'ordre : 0, 1, 0, 1, 1, 4, 1, 4.

Le résultat à afficher est donc 4.

[thelvin]

Hello,

Et, hum. Et donc, ton algo, quel est-il ?
Nous risquons d'avoir du mal à le corriger sans le voir.

[Metogon]

Dans mon code il y a un objet Manteau et un Temperature.

J'ai fait un tableau de Temperature[] qui est trié.

Code :

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

1
2
3
4
5
6
7
Manteau:
    min, max: Températures minimum et maximum du Manteau
    lvl: Le niveau du manteau
 
Temperature:
    mes: La valeur de la température
    id: L emplacement du Manteau correspondant dans le tableau Manteau[]

Code :

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

1
2
3
4
5
6
7
8
9
Parcourir le tableau de Temperature[] avec i
  temperatureMax <- (récupère la Temperature max du Manteau)
  j <- i
  Tant que la Temperature à l index j est inférieure à temperatureMax
    Si le Manteau de la Temperature à l index j est dans l intervalle i-temperatureMax alors
      incrémenter le niveau du Manteau
    fin si
  fin tant que
C est lent mais plus rapide que de tester chauque combinaison de Manteau.

Code :

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
103
104
105
106
107
108
109
110
111
112
113
114
115
import java.util.Arrays;
 
import java.util.Scanner;
 
public class Main{
 
	public static Manteau[] mants;
 
	public static Temperature[] temps;
 
	public static int nbMants;
 
	public static boolean isMinTemperature(Temperature t){
		return t.mes == mants[t.id].min;
	}
 
	public static void main(final String[] args){
		Scanner s = new Scanner(System.in);
 
		nbMants = s.nextInt();
		mants = new Manteau[nbMants];
		temps = new Temperature[nbMants * 2];
 
		for(int i = 0; i < nbMants; i++){
			int min = s.nextInt(), max = s.nextInt();
 
			mants[i] = new Manteau(min, max);
 
			temps[i * 2] = new Temperature(min, i);
			temps[(i * 2) + 1] = new Temperature(max, i);
		}
 
		Arrays.sort(temps);
 
		// Pour toutes les Temperature
		for(int i = 0; i < nbMants * 2; i++){
			Temperature tI = temps[i];
			Manteau mI = mants[tI.id];
 
			if(isMinTemperature(tI)){
				int j;
				Temperature tJ;
				Manteau mJ;
				// Parcours en arrière
				if(i > 0){
					j = i - 1;
					tJ = temps[j];
					mJ = mants[tJ.id];
 
					while(tI.mes == tJ.mes && i > 0){
						if(isMinTemperature(tJ) && mJ.max <= mI.max){
							mJ.lvl++;
						}
 
						j--;
						if(j >= 0){
							tJ = temps[j];
							mJ = mants[tJ.id];
						}
					}
				}
 
				// Et en avant
				if(i < nbMants * 2){
					j = i + 1;
					tJ = temps[j];
					mJ = mants[tJ.id];
 
					while(tI.mes <= mI.max && j < nbMants * 2){
						if(isMinTemperature(tJ) && mJ.max <= mI.max){
							mJ.lvl++;
						}
 
						j++;
						if(j < nbMants * 2){
							tJ = temps[j];
							mJ = mants[tJ.id];
						}
					}
				}
			}
		}
 
		int lvlMax = 0;
		for(int i = 0; i < nbMants; i++){
			lvlMax = Math.max(lvlMax, mants[i].lvl);
		}
 
		System.out.println(lvlMax + 1);
	}
}
 
class Manteau{
 
	public int min, max, lvl = 0;
 
	public Manteau(int min, int max){
		this.min = min;
		this.max = max;
	}
}
 
class Temperature implements Comparable<Temperature>{
 
	public int mes, id;
 
	public Temperature(int mes, int id){
		this.mes = mes;
		this.id = id;
	}
 
	public int compareTo(Temperature o){
		return new Integer(mes).compareTo(new Integer(o.mes));
	}
}

[Tr0n33]

La solution intuitive est simple : parcourir l'ensemble des intervalles et calculer pour chacun d'entre eux le nombre d'intervalles qu'ils contiennent (soit O(n²)). En fait l'important c'est la notion d'intervalles dans ce problème.

L'objectif est de parcourir une liste d'intervalles et de dénombrer les inclusions (nombre max d'intervalles contenues dans celui qu'on regarde). Grosso modo, j'aurais plutôt utilisé une seule structure de ce style : ([1,3], [2,5], [3,5]...). De mon souvenir la complexité de l'algorithme devrait être en O(n *log n) (Vous me direz le pif, vieille habitude des exercices de l'université sans doute).

Notons les intervalles I(k) = [Tmin(k), Tmax(k)] (qui sont l'intervalle de température d'un manteau).
Tous ces intervalles sont contenues dans une liste/tableau de tous les manteaux.

1- On trie la liste des intervalles par température minimale Tmin(k) croissante et en cas d'égalité par température Tmax(k) max décroissante.
2- On parcourt la liste (des manteaux) et on enregistre la position p(1, k) de chaque intervalle.
3- On trie de nouveau la liste mais par température maximaml Tmax(k) décroissante et en cas d'égalité par température Tmin(k) croissante.
4- On parcourt alors cette liste et on enregistre la position p(2,k) de chaque intervalle.

Bilan : Le nombre d'intervalles max inclus dans un autre est alors... argmax(k) = (NbManteau - p(1,k) - p(2,k) - 1) pour k compris entre 1 et NbManteau. Pour la première position dans la liste p(i,k) = 0 par convention. On affecte alors à chaque numéro de manteau k, le nombre maximal d'inclusion.

Est ce que c'est cela que tu indiques avec tes parcours avant/arriere ?



Après pour l'optimisation purement Java : les déclarations de variables peuvent être positionnées en dehors des boucles (cela évite de réinstancier la donnée à chaque itération, le gain est colossale sur des grosses boucles; le compilateur n'effectuant pas cette optim même en Java 7). Il y a d'autres astuces mais cela fait très longtemps, je pense que le compilateur Java est suffisamment optimisé pour les astuces de comparaison avec 0 et d'écritures. Je suppose que l'optimisation voulu concerne surtout la complexité.

Je ne sais pas si j'ai bon, ça fait vraiment longtemps que je n'ai plus fait d'algorithmie ^^. Pour ton algorithme, j'essaie de le faire tourner et de te faire une réponse rapidement.

[thelvin]

Hello,

je dois dire que je me triture l'esprit pour imaginer un algorithme qui marche et qui ne fasse pas du O(n²). Peut-être en triant par taille d'abord...
Et je me triture aussi la tête pour comprendre comment sont censés marcher les algorithmes que je vois là. J'aurais bien aimé une description je dois dire -_-°.


Du coup pour l'instant je ne peux rebondir que là-dessus :

Après pour l'optimisation purement Java : les déclarations de variables peuvent être positionnées en dehors des boucles (cela évite de réinstancier la donnée à chaque itération, le gain est colossale sur des grosses boucles; le compilateur n'effectuant pas cette optim même en Java 7).

Hmm non, en Java il n'y a (ré)instanciation que quand il y a un new. L'endroit où on déclare une variable ne change rien à l'exécution, et n'est qu'un outil de développement pour s'organiser. Au contraire une variable devrait être déclarée au plus profond possible pour limiter sa portée aux seuls endroits où elle a un sens.
Je ne vois pas où tu as imaginé ce "gain colossal" ni de quelle optimisation on serait en train de parler.

[Metogon]

Mon algo en O(n²) est foutu je pense.

La limite du sujet étant à 20 000 manteau il tourne à 400 000 000 itérations !

Ce qui est beaucoup trop pour les 0.5 secondes sur une machine à 1GHz.

J'ai maximum quelques millions seulement d'itération disponibles avec ce temps...

PS: Il me viens une idée. Je l'écris pour ne pas l'oublier demain et au cas où ça inspirerait quelqu'un... Et si on triais les manteau en fonction de la différence de temperature (tempMax - tempMin) ?

Ou... Si on ne triais rien du tout ??

Car après tout le tri prends déjà O(n log n) ?


Je vous laisse sur ces deux idées là pour ce soir, je m'y remettrais demain...