Problème Algorithmique ioi france

**TRx56** · 25/06/2024, 12h17

Bonjour;

Je suis actuellement bloqué sur un exercice de chez ioi France, mon code passe 18 tests sur 21. Les derniers tests échouent pour dépassement de la limite du temps.

Voici l'ennocée:
Un festival de musique met chaque jour un groupe en scène, un groupe pouvant jouer plusieurs jours différents. En tout, nbGroupes groupes vont jouer pour ce festival et ce dernier durera nbJours jours.

Vous connaissez l'ordre dans lequel les différents groupes vont se succéder au cours du festival à raison d'un par jour, et vous désirez assister au concert de chacun de ces groupes au moins une fois. Vous écrivez donc un programme capable de determiner la longueur de la plus petite séquence contiguë de jours permettant de voir au moins une fois chaque groupe.
Limites de temps et de mémoire (C)

Temps : 1 s sur une machine à 1 GHz.
Mémoire : 32 000 ko.

Contraintes

1 <= nbJours <= 100 000, où nbJours est le nombre de jours du festival.
1 <= nGroupes <= nbJours, le nombre de groupes jouant pour le festival.

Entrée

La première ligne de l'entrée contient deux entiers : nbJours et nbGroupes.

La ligne suivante contient nbJours entiers, le ie entier correspondant à l'identifiant 1 <= groupei <= nbGroupes du groupe jouant le ie jour.
Sortie

Votre programme doit afficher un unique entier : le plus petit nombre de jours consécutifs nécessaires pour voir au moins une fois chaque groupe jouer.
Exemple

entrée :

12 5
1 3 2 2 5 4 3 2 5 5 1 4

sortie :

6

Voici mon code:

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
#include <stdio.h>
#include <stdlib.h>
int nbJours, nbGroupes;
int *planning = NULL, *dejaVu = NULL;
int minDays(int minimum);
int main()
{
   int i;
   scanf("%d%d", &nbJours, &nbGroupes);
 
   planning = malloc(sizeof(int) * nbJours);
   dejaVu = malloc(sizeof(int) * nbJours);
   for(i = 0; i < nbJours; i++)
   {
      scanf("%d", &planning[i]);
      dejaVu[i] = 0;
   }
 
   printf("%d", minDays(nbJours));
 
   free(dejaVu);
   free(planning);
}
int minDays(int minimum)
{
   int debut = 0, iFin = 0, compteur = 0;
   int iGroup = 0;
   while(iFin < nbJours)
   {
      if(dejaVu[planning[iFin]] == iGroup)
      {
         dejaVu[planning[iFin]] = iGroup+1;
         compteur++;
      }
 
      while(compteur == nbGroupes)
      {
         if((iFin+1 - debut) < minimum)
            minimum = (iFin+1 - debut);
         iGroup++;
         debut++;
         compteur = 0;
         iFin = debut-1;
      }
      iFin++;
   }
   return minimum;
}

J'utilise un tableau dejaVu pour valider un groupe complet de jours. Je parcours le tableau planning plusieurs fois. Je pense que c'est cela qui plombe la vitesse.
Merci d'avance pour l'aide apportée !

**boboss123** · 25/06/2024, 13h56

Bonjour,

Tu ne testes pas les éléments d'entrée, je te conseille donc de le faire, c'est une bonne pratique à adopter.
De plus, tu utilises des variables globales, ce qui est déconseillé.

Donc voici déjà un correctif (je n'ai pas modifié ton algorithme, il y a donc toujours le problème):

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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
typedef struct {
  uint32_t nbJours;
  uint32_t *planning;
 
  uint32_t nbGroupes;
  uint8_t *dejaVu;
} inputStruct;
 
uint32_t minDays(inputStruct *input);
 
int main(){
  uint32_t i;
  uint32_t result;
 
  inputStruct input;
 
  printf("Entrer nbJours et nbGroupes: ");
  scanf("%u%u", &input.nbJours, &input.nbGroupes);
  printf("\nnbJours %u, nbGroupes %u\n", input.nbJours, input.nbGroupes);
  if((input.nbJours < 1) || (input.nbJours > 100)){
    printf("[ERR] 1 <= nbJours(%u) <= 100\n", input.nbJours);
    return -1;
  }
  if((input.nbGroupes < 1) || (input.nbGroupes > input.nbJours)){
    printf("[ERR] 1 <= nbGroupes(%u) <= nbJours(%u)\n", input.nbGroupes, input.nbJours);
    return -1;
  }
 
  input.planning = malloc(sizeof(uint32_t) * input.nbJours);
  input.dejaVu = malloc(sizeof(uint8_t) * input.nbGroupes);
  if((input.planning == NULL) || (input.dejaVu == NULL)){
    printf("[ERR] memory allocation failed\n");
    return -1;
  }
  printf("Init...\n");
  for(i = 0; i < input.nbJours; i++){
    printf("Entrer Groupe pour jour %u: ", i+1);
    int groupe;
    scanf("%u", &groupe);
    if((groupe < 1) || (groupe > input.nbGroupes)){
      printf("[ERR] Le Groupe n'est pas compris entre 1 et %u\n", input.nbGroupes);
      i--;
    } else {
      input.planning[i] = groupe;
    }
  }
  for(i = 0; i < input.nbGroupes; i++){
    input.dejaVu[i] = 0;
  }
 
  printf("Process...\n"); 
  result = minDays(&input);
  if(result >= input.nbGroupes){
    printf("Result: %u\n", result);
  } else {
    printf("[ERR] Result: les groupes n'ont pas tous été plannifiés\n");
  }
 
  free(input.dejaVu);
  free(input.planning);
  printf("End\n");
 
  return 0;
}
 
uint32_t minDays(inputStruct *input){
  uint32_t debut = 0, iFin = 0, compteur = 0;
  uint32_t iGroup = 0;
  uint32_t minimum = input->nbJours;
  while(iFin < input->nbJours){
    if(input->dejaVu[input->planning[iFin]] == iGroup){
      input->dejaVu[input->planning[iFin]] = iGroup+1;
      compteur++;
    } 
    while(compteur == input->nbGroupes){
      if((iFin+1 - debut) < input->nbJours){
        minimum = (iFin+1 - debut);
      }
      iGroup++;
      debut++;
      compteur = 0;
      iFin = debut-1;
    }
    iFin++;
  }
  return minimum;
}

Ton programme ne fonctionne pas :

Code :

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

1
2
10 5
1 1 2 2 3 4 5 5 1 2

=> retourne 6. Donc je te laisse trouver la solution pour modifier minDays afin que ça fonctionne.

La première piste que je peux te donner : pourquoi ton tableau dejaVu fait la même taille que planning ?
=> le tableau dejaVu devrait indiquer si le groupe a déjà été vu. De plus, tu devrais avoir un compteur qui t'indique le nombre de groupe déja vu : dès que le compteur atteint la valeur du nombre de groupe, c'est que tous les groupes sont passés et si à la fin de l’exécution de la fonction minDays le compteur est inférieur au nombre de groupes, c'est qu'un ou plusieurs groupe n'ont pas été planifiés.

**Guesset** · 25/06/2024, 19h51

Bonjour,

Le principe d'utiliser pour les groupes vus un tableau d'entier me chagrinait un peu (des booléens suffisent). D'où le remplacement par un entier de 64 bits dont chaque bit à 0 signale que le groupe correspondant a déjà été vu. Quand l'entier vaut 0 c'est bon. Et on tient un prétendant au meilleur score mais la sortie se fait aussi avec la limite de durée. Dans ce cas si l'entier ne vaut pas 0 c'est fini on retourne directement le résultat trouvé (durée + 1 si aucune solution).
On peut dépasser les 64 bits donc 64 groupes en utilisant plusieurs mots mais c'est un peu plus laborieux, genre vus[j >> 6] &= ~(1 << (plan[j] & 63)); etc. En résumé j'ai eu la flemme

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
#include <stdio.h>
#include <stdlib.h>
 
int duree;                                       // durée du festival
int *plan;                                       // Groupe de chaque jour
unsigned long long visibles;                     // Ensemble des groupes visibles au festival
 
int minDays() {
   int minimum = duree + 1;
   int i, j;
   for(i = 0; i <= duree; i++) {
      unsigned long long vus = visibles;
      for(j = i; (j < duree) && (vus); j++) vus &= ~(1 << plan[j]);
      if(vus) return minimum;                    // Pas la peine d'insister
      int d = j - i + 1;
      if(d < minimum) minimum = d;
   }
   return minimum;
}
 
int main() {
   int i, result,nbGroupes, nbGrpMax;
   do {
      printf("Entrer duree (1..100) et nb groupes (1..min(64,duree)) : ");
      scanf ("%d%d", &duree, &nbGroupes);
      printf("\n%d jours, %d groupes\n", duree, nbGroupes);
      nbGrpMax = duree > 64 ? 64: duree;
   } while((duree < 1) || (duree > 100) || (nbGroupes < 1) || (nbGroupes > nbGrpMax));
   plan     = malloc(sizeof(int) * duree);
   visibles = (1 << nbGroupes) - 1;              // 5 groupes => b100000 - 1 = b11111
   printf("\nInitialisation\n------------------\n");
   for(i = 0; i < duree; i++) {
      int groupe;
      printf("Groupe du jour %2d ? ", i+1);
      scanf("%d", &groupe);
      if((groupe > 0) && (groupe <= nbGroupes))
         plan[i] = groupe - 1;                   // -1 ramène de 0 à nbGroupes-1
      else {
         printf("Erreur : groupe non entre 1 et %d\n", nbGrpMax);
         i--;
      }
   }
   result = minDays();
   if(result <= duree) printf("------------------\nResultat : %d\n", result);
   else printf("[ERR] Certains groupes non plannifies\n");
   free(plan);
   return 0;
}

Salutations

**boboss123** · 26/06/2024, 09h28

Envoyé par Guesset

Bonjour,
On peut dépasser les 64 bits donc 64 groupes en utilisant plusieurs mots mais c'est un peu plus laborieux, genre vus[j >> 6] &= ~(1 << (plan[j] & 63)); etc. En résumé j'ai eu la flemme

Vu qu'il peut potentiellement y avoir 100 000 groupes, je ne suis pas certains que ça soit la meilleur solution que d'utiliser cette méthode.

Remarque : en langage C le type int n'a pas de taille imposée, ça peut être un nombre de 16bits, ce qui est insuffisant pour enregistrer la valeur 100000. il serait mieux d'utiliser le type uint32_t (4 octets) à la place, ce qui amène une consommation de 4 x 100000 = 400 ko pour la tableau planning et 1 x 100000 = 100 ko pour le tableau dejaVu (il faut ajouter quelques octets pour le stockage des variables tampon pendant les calculs) : on est donc dans les clous, pas besoin d'utiliser cette méthode pour réduire la consommation mémoire.

**Guesset** · 26/06/2024, 10h39

Bonjour Boboss,

Envoyé par boboss123

Vu qu'il peut potentiellement y avoir 100 000 groupes, je ne suis pas certains que ça soit la meilleur solution que d'utiliser cette méthode.
Remarque : en langage C le type int n'a pas de taille imposée, ça peut être un nombre de 16bits, ce qui est insuffisant pour enregistrer la valeur 100000. il serait mieux d'utiliser le type uint32_t (4 octets) à la place, ce qui amène une consommation de 4 x 100000 = 400 ko pour la tableau planning et 1 x 100000 = 100 ko pour le tableau dejaVu (il faut ajouter quelques octets pour le stockage des variables tampon pendant les calculs) : on est donc dans les clous, pas besoin d'utiliser cette méthode pour réduire la consommation mémoire.

Un entier int est aujourd'hui au moins du 32 bits sur les ordinateurs (ce qui exclut, mais de moins en moins, les MPU). Mais c'est vrai que je préfère les types explicites.
La forme initiale de gestion des groupes utilise 100 000 int soit 400 000 octets contre 12 500 octets soit 1563 uint64_t pour le mode set.
Mais le gain principal ne réside pas là. Le travail avec un ensemble permet de détecter beaucoup plus rapidement que tous les groupes ont étés vus. Environ 64 fois plus vite et la vérification à 0 n'a statistiquement que la moitié des 1563 uint64_t à parcourir.

Il me semblait que le temps était un critère non satisfait d'où ce type de proposition (en fait je crois que j'utiliserais les instruction AVX512 pour x par 8 encore les performances mais cela nécessite de l'assembleur inline).
Une question : je me demande comment sont vérifiés les temps dans un programme qui fait de la saisie manuelle et n'intègre pas de mesure de temps intrinsèque sur la partie critique ? Automate de saisie ?

Ceci étant, un festival de 100 000 jours durerait à peu près de 273 ans 9 mois 12 jours. Je ne suis pas sûr que ce soit réaliste

. De même que la distribution des groupes, imagine un groupe qui passe le premier et dernier jour du festival de 100 000 jours

.

Salut

**boboss123** · 26/06/2024, 12h08

Envoyé par Guesset

Une question : je me demande comment sont vérifiés les temps dans un programme qui fait de la saisie manuelle et n'intègre pas de mesure de temps intrinsèque sur la partie critique ? Automate de saisie ?

C'est la question que je me posais aussi : surtout qu'il y a des scanf.

Je serais parti sur cette solution :

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
 
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
typedef struct {
  uint32_t nbJours;
  uint32_t *planning;
 
  uint32_t nbGroupes;
  uint8_t *dejaVu;
} inputStruct;
 
uint32_t minDays(inputStruct *input);
 
int main(){
  uint32_t i;
  uint32_t result;
 
  inputStruct input;
 
  printf("Entrer nbJours et nbGroupes: ");
  scanf("%u%u", &input.nbJours, &input.nbGroupes);
  printf("\nnbJours %u, nbGroupes %u\n", input.nbJours, input.nbGroupes);
  if((input.nbJours < 1) || (input.nbJours > 100)){
    printf("[ERR] 1 <= nbJours(%u) <= 100\n", input.nbJours);
    return -1;
  }
  if((input.nbGroupes < 1) || (input.nbGroupes > input.nbJours)){
    printf("[ERR] 1 <= nbGroupes(%u) <= nbJours(%u)\n", input.nbGroupes, input.nbJours);
    return -1;
  }
 
  input.planning = malloc(sizeof(uint32_t) * input.nbJours);
  input.dejaVu = malloc(sizeof(uint8_t) * input.nbGroupes);
  if((input.planning == NULL) || (input.dejaVu == NULL)){
    printf("[ERR] memory allocation failed\n");
    return -1;
  }
  printf("Init...\n");
  for(i = 0; i < input.nbJours; i++){
    printf("Entrer Groupe pour jour %u: ", i+1);
    int groupe;
    scanf("%u", &groupe);
    if((groupe < 1) || (groupe > input.nbGroupes)){
      printf("[ERR] Le Groupe n'est pas compris entre 1 et %u\n", input.nbGroupes);
      i--;
    } else {
      input.planning[i] = groupe;
    }
  }
  for(i = 0; i < input.nbGroupes; i++){
    input.dejaVu[i] = 0;
  }
 
  printf("Process...\n"); 
  result = minDays(&input);
  if(result >= input.nbGroupes){
    printf("Result: %u\n", result);
  } else {
    printf("[ERR] Result: les groupes n'ont pas tous été plannifiés\n");
  }
 
  free(input.dejaVu);
  free(input.planning);
  printf("End\n");
 
  return 0;
}
 
uint32_t minDays(inputStruct *input){
  uint32_t counter = 0;
  uint32_t indexNbJours = 0;
  uint32_t indexDejaVu;
  uint8_t *ptrDejaVu;
 
  uint32_t *planning = input->planning;
  uint8_t *dejaVu = input->dejaVu;
 
  uint32_t nbJours = input->nbJours;
  uint32_t nbGroupes = input->nbGroupes;
 
  while(indexNbJours < nbJours){
    //printf("indexNbJours: %u\n", indexNbJours);
    indexDejaVu = planning[indexNbJours]-1;
    //printf("indexDejaVu: %u\n", indexDejaVu);
    ptrDejaVu = &dejaVu[indexDejaVu];
    if(*ptrDejaVu == 0){
      *ptrDejaVu = 1;
      counter++;
      if(counter == nbGroupes){
        indexNbJours++;
        //printf("Result: %u [OK]\n", indexNbJours);
        return indexNbJours;
      }
    }
    indexNbJours++;
  }
 
  //printf("[ERR] Result: %u\n", counter);
  return counter; // erreur : retourne le nombre de groupes planfiés
}

=> je me demande quelle est la différence de temps d’exécution avec ta solution

**kaitlyn** · 27/06/2024, 12h32

Salut,

Envoyé par Guesset

Une question : je me demande comment sont vérifiés les temps dans un programme qui fait de la saisie manuelle et n'intègre pas de mesure de temps intrinsèque sur la partie critique ? Automate de saisie ?

Tu fais tes mesures dans une application parent. Concrètement, elle lance le programme à évaluer comme processus enfant, en mode pausé, active le chrono, débloque le processus, Après avoir redirigé les entrée et sortie standards, elle transmet les données par tube (pipe). Dès réception du résultat (toujours par pipe), elle stoppe le chrono. Pour les autres infos, c'est l'OS qui les donne, notamment avec l'identifiant du processus. Voilà pour les grandes lignes, plus augmenter la priorité du processus aussi.

Problème Algorithmique ioi france

C

Vue hybride

Discussions similaires

Partager

Partager