Problème sur un excercice d'algorithmie

Version imprimable

13/06/2015, 19h03
Metogon

Problème sur un excercice d'algorithmie

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 :) :D

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

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.
14/06/2015, 17h15
thelvin

Hello,

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

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

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

Code:

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:

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:

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));
	}
}

16/06/2015, 16h38
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.
16/06/2015, 18h08
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 :

Citation:

Envoyé par Tr0n33

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.
16/06/2015, 23h28
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...:sleep:
17/06/2015, 11h34
Tr0n33

Citation:

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.

Oula !!! My bad. J'étais sans doute en train de ruminer mon énervement quotidien au boulot. J'ai effectivement dit déclaration à la place d'instanciation. Merci de l'avoir noté, ça fait tâche (sans doute la fixette que je fais sur cette erreur que je vois bien trop souvent).

Sinon si, j'ai vérifié, c'est bien un algo en O(n * log n) que j'ai proposé.

Je suis en train de l'implémenter pour le tester mais à priori ça a l'air d'être bon. Il faut trier les intervalles par le minimum, puis par le maximum et faire des soustractions en fonction des positions de la liste (d'ailleurs c'est amusant que dans le problème on est appelé le chiffre que l'on cherche le niveau maximum). Grosso modo, j'ai deux parcours en O(n) et argmax que je calcule en O(n * log n). En fait c'est fondé sur la position dans les listes pour savoir qui est inclus dans quoi. Sur un processus à 1 GHz, normalement avec cette complexité et malgré les 3 étapes tu dois être en dessous de 500 ms.
17/06/2015, 12h08
Tr0n33

Tout est fondé sur la position.

Tableau des manteaux avec ton exemple :
Intervalle cree : [1,3]
Intervalle cree : [2,5]
Intervalle cree : [5,8]
Intervalle cree : [3,6]
Intervalle cree : [2,5]
Intervalle cree : [3,8]
Intervalle cree : [3,6]
Intervalle cree : [3,8]

Trié par min (max decroissant en cas d'égalité)
[1,3] [2,5] [2,5] [3,8] [3,8] [3,6] [3,6] [5,8]
Trié par max (min croissant en cas d'égalité
[1,3] [2,5] [2,5] [3,6] [3,6] [5,8] [3,8] [3,8]

Tu vois alors rapidement qu'est ce qui est inclu dans quoi en fonction : de la position intiale, et de la position dans les deux tableaux de min.
Par exemple tu vois que l'intervalle [5,8] est en position 3 dans le tableau de départ, qu'il est en position 8 dans le tableau des min et en position 6 dans le tableau des max. Il est donc inclu... Dans 2 intervalles, qui sont... [3,8] et [3,8]. Même exemple pour [3,6] qui est en position 6 et 7 dans le tableau des min et en position 4 et 5 dans le tableau des max. Il est donc inclu dans... 3 éléments : lui même (puisqu'il apparait 2 fois) et [3,8] deux fois

On a ainsi non pas les éléments qui sont inclus dans quoi, mais uniquement leur nombre. Il faut bien penser à sauvegarder les positions dans les étapes de tri. L'astuce me semble donc être fondé sur une double comparaison d'un tableau de tri des températures par leur minimum d'un côté et par leur maximum de l'autre, avec une comparaison des positions dans ces tableaux. Ca devrait t'aider pour ton probleme, j'espère.

Ca permet normalement de faire ton calcul du niveau max non ?

Moi, j'aurais bien tenté d'utiliser un arbre pour résoudre ce probleme grace à la propriété de transitivité évidente du probleme. Avec ca, on pourrait insérer directement chaque éléments au bon endroit.

Ca donnerait un truc du genre:

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
class Manteau
{
  // Si on range directement les Elements dans cette liste triés selon min puis max croissants, ca permet de ne pas avoir à la parcourir.
  List<Manteau> fils = new ArrayList<Manteau>();
 
  int min;
  int max;
  Manteau(int min, int max)
  {
    this.min = min;
    this.max = max;
  }
 
   void addManteau(Manteau manteau)
   {
      int i = 0;
      while(i < fils.size() && manteau.min >= fils.get(i).min)
      {
         if(manteau.max <= fils.get(i).max)
         {
            fils.get(i).addManteau(manteau);
            return;
         }
         ++i;
      }
 
      // i pointe sur le premier manteau dont le min est plus grand ou bien sur fils.size()
      // Maintenant, on regarde si un ou plusieurs manteaux peuvent etre inclus dans le nouveau manteau
      while(i < fils.size() && manteau.max >= fils.get(i).max)
      {
         // Tous les manteaux ici devront etre supprimes de l'element pere (this) et inseres dans le nouvel element
         // Note qu'ici, on peut inserer directement la liste sans avoir a faire les verifications de addManteau (puisqu'elles ont deja ete faites)
         manteau.addManteau(fils.get(i));
         fils.remove(i);
      }
      fils.add(i, manteau);
   }
 
   int compteFils()
   {
      int ret = fils.size();
      for(Manteau manteau : fils)
      {
         ret += manteau.compteFils();
      }
      return ret;
   }
   @Override
   public String toString()
   {
      return "[" + min + "," + max + "]";
   }
}
 
Manteau base = new Manteau(0, 0);
Manteau el;
ArrayList<Manteau> listManteaux = new ArrayList<Manteau>();
el = new Manteau(1, 3);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(2, 5);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(5, 8);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 6);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(2, 5);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 8);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 6);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 8);
base.addManteau(el);
listManteaux.add(el);
 
for(Manteau manteau : listManteaux)
{
   System.out.println("Manteau " + manteau.toString() + " fils=" + manteau.compteFils());
}

Note que ce code ne gere pas les doublons donc il faut adapter. Mais je ne vois pas trop comment faire plus efficace...

17/06/2015, 14h10
Tr0n33

Citation:

Envoyé par hwoarang

Moi, j'aurais bien tenté d'utiliser un arbre pour résoudre ce probleme grace à la propriété de transitivité évidente du probleme. Avec ca, on pourrait insérer directement chaque éléments au bon endroit.

Ca doit pouvoir se faire. J'aime bien aussi cette idée :)
17/06/2015, 14h17
hwoarang

A la reflexion, il manque aussi une condition d'arret dans mon algo lors du premier parcours des manteaux (en fonction de max). Mais bon, c'est juste pour l'exemple. J'etais parti sur du pseudocode mais je trouve ca moins lisible ^^
17/06/2015, 19h07
Metogon

Merci pour vos réponses.

J'étudie ça dès que j'ai plus de temps.

Citation:

Envoyé par hwoarang

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
class Manteau
{
  // Si on range directement les Elements dans cette liste triés selon min puis max croissants, ca permet de ne pas avoir à la parcourir.
  List<Manteau> fils = new ArrayList<Manteau>();
 
  int min;
  int max;
  Manteau(int min, int max)
  {
    this.min = min;
    this.max = max;
  }
 
   void addManteau(Manteau manteau)
   {
      int i = 0;
      while(i < fils.size() && manteau.min >= fils.get(i).min)
      {
         if(manteau.max <= fils.get(i).max)
         {
            fils.get(i).addManteau(manteau);
            return;
         }
         ++i;
      }
 
      // i pointe sur le premier manteau dont le min est plus grand ou bien sur fils.size()
      // Maintenant, on regarde si un ou plusieurs manteaux peuvent etre inclus dans le nouveau manteau
      while(i < fils.size() && manteau.max >= fils.get(i).max)
      {
         // Tous les manteaux ici devront etre supprimes de l'element pere (this) et inseres dans le nouvel element
         // Note qu'ici, on peut inserer directement la liste sans avoir a faire les verifications de addManteau (puisqu'elles ont deja ete faites)
         manteau.addManteau(fils.get(i));
         fils.remove(i);
      }
      fils.add(i, manteau);
   }
 
   int compteFils()
   {
      int ret = fils.size();
      for(Manteau manteau : fils)
      {
         ret += manteau.compteFils();
      }
      return ret;
   }
   @Override
   public String toString()
   {
      return "[" + min + "," + max + "]";
   }
}
 
Manteau base = new Manteau(0, 0);
Manteau el;
ArrayList<Manteau> listManteaux = new ArrayList<Manteau>();
el = new Manteau(1, 3);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(2, 5);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(5, 8);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 6);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(2, 5);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 8);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 6);
base.addManteau(el);
listManteaux.add(el);
el = new Manteau(3, 8);
base.addManteau(el);
listManteaux.add(el);
 
for(Manteau manteau : listManteaux)
{
   System.out.println("Manteau " + manteau.toString() + " fils=" + manteau.compteFils());
}

Note que ce code ne gere pas les doublons donc il faut adapter. Mais je ne vois pas trop comment faire plus efficace...

Il y a un pb avec cet algo. Mais je suis sur que c'est la bonne base. Je verrais demain, où si vous avez des idées, merci :)

Ma sortie:

Code:

1
2
3
4
5
6
7
8
Manteau [1,3]{  }0
Manteau [2,5]{ [2,5]{  } }1
Manteau [5,8]{  }0
Manteau [3,6]{ [3,6]{  } }1
Manteau [2,5]{  }0
Manteau [3,8]{ [3,8]{ [5,8]{  } } }2
Manteau [3,6]{  }0
Manteau [3,8]{ [5,8]{  } }1

perso je ferais un algo qui droppe les manteaux au fur et à mesure comme ceci:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 faire une liste de manteaux (ou tableau) faire une liste de manteaux potentiel identique pour chaque manteau potentiel M1: taille à 0 faire une liste de travail pour chaque autre manteau M2 dans la liste de travail: si M2 rentre dans M1: retirer M2 des potentiels (un plus grand que lui existe il ne pourra jamais être un bon candidat) taille +1 sinon si M1 rentre dans M2: le nouveau candidat est M2 retirer M1 des potentiels taille + 1 reprendre au début de la liste de travail sinon passer au suivant de la liste de travail fin pour si taille > meilleur candidat meilleur candidat = celui qu'on a testé stocker la meilleur taille passer au potentiel suivant.
L'avantage c'est que 2 conditions sur 3 expurgent définitivement des candidats dans ta liste de potentiel, donc même si c'est du O(n²), le worst case (tout le monde comparé à tout le monde) se produira quand aucun chevauchement n'existe et le o() moyen sera probablement bien plus acceptable.

Au delà pour augmenter les perfs, faudra recourir à des algos de partitionnement d'espace mais c'est un travail assez long dev avec un prétraitement. On s'approche plus du Travail de fin d'étude que d'un examen :)

18/06/2015, 08h55
hwoarang

Citation:

Envoyé par Metogon

Il y a un pb avec cet algo. Mais je suis sur que c'est la bonne base. Je verrais demain, où si vous avez des idées

Il y a au moins 2 problemes dont j'ai deja parlé:
- Il n'y a pas de gestion des doublons. Si 2 manteaux identiques sont insérés, le 2e prendra la place du premier. Son compte de niveau sera bon mais pas celui du manteau remplacé.
- La condition d'arret de la premiere boucle n'est pas suffisante. Comme on suppose la liste de fils classée, il faut ajouter une condition sur le max pour sortir si on trouve une borne min égale et une borne max superieure.

Il n'y a rien de bien sorcier pour corriger ces problemes. Il faut juste choisir ce que tu veux faire pour la gestion des doublons (suppression du manteau doublon au profit d'un compteur / utilisation d'une sur-classe de stockage / bidouillerie dans la classe / ...)
21/06/2015, 18h57
Metogon

J'ai un peu cherché ce WE et je me dis qu'il est peut-être possible de résoudre le problème avec un arbre ? Ou bien un arbre de Fenwick?