LogoFrance-IOI
France-IOI » Courses and tasks » Efficacité temporelle » Premier absent
fedi37
See my public page
My profile
Authentication
Log out
Language: English
Sitemap
Improving
Presentation
Courses and tasks
Frequent questions
Help forum
Teaching
Presentation
Groups and classes
Competing
Presentation
Ranking
Contest tasks
Results
Olympiads
Presentation
Selection
Results
Other Olympiads
The association
Presentation
History
Training camps
Contact us
Report a bug
225 users online
Demands for help
today
domino
Distributeur automatique
today
calusrel
Maison de l'espion
today
mamous 2021
Tours de Hanoï
yest.
marie974 2017
La bataille
d.
kamikadze 2020
Nombre d'amour
Successful submissions
16:08
haonam 2015
Tri des données
16:08
thefrenchmonster
Encore des punitions
16:08
nathan-rorby 2017
Villes et villages
16:07
mestre-maiwenn 2020
Transport d'eau
16:07
melyna 2020
Course avec les enfants
16:07
benjaminolivier 2020
Course avec les enfants
16:07
vtcba
Mathématiques de base
16:07
skrempp 1997
Résumés de livres
16:07
sarkozy 2020
Graduation de thermomètres
16:07
miroineau 2020
Visite de la mine
16:06
calusrel
Amitié entre gardes
16:06
bast29 2020
Mont Kailash

C++
Validé !Premier absent
Print
TaskSolveHelpActivitySolution
Jacques-Henri Jourdan

Solution naïve
On peut stocker dans une liste l'ensemble des élèves déjà arrivés. Pour implémenter cette liste, on peut par exemple utiliser un tableau, qui contient, dans les premières cases, les élèves déjà arrivés. À chaque fois qu'un nouvel élève arrive, on peut recalculer le premier élève absent : il va donc faloir tester, pour chaque élève inscrit, s'il est présent.

Il y a nbPrésents arrivées de nouveaux élèves, et à chaque fois, a priori, il faut vérifier nbInscrits élèves inscrits. De plus, la vérification de la présence d'un élève se fait en nbPrésents étapes. Au total, la compexité est de O(nbInscrits*nbPrésents^2).

   présents = liste vide
   Pour chaque présent de 0 à nbPresents-1
      Lire identifiant
      présents.ajouter(identifiant-1)
      Pour chaque inscrit de 0 à nbInscrits-1
         inscritEstAbsent = Faux
         Pour chaque élève dans présents
            Si élève == inscrit
               inscritEstAbsent = Vrai
               Sortir de la boucle
         Si inscritEstAbsent
           Afficher inscrit
           Sortir de la boucle
      Si aucun absent n'a été trouvé
        tous les élèves sont présents
On peut faire une meilleure analyse de la complexité : en effet, l'identifiant du premier élève absent sera toujours plus petit ou égal au nombre d'élèves présents. Ainsi, la boucle qui teste tous les élèves inscrits et qui vérifie s'il est présent n'effectue en fait dans le pire cas que O(nbPrésents) itérations. La complexité devient alors O(nbPrésents^3), ce qui est trop lent.

Meilleure structure de données
Dans la solution précédente, une opération qui prend du temps est de tester si un élève donné est présent. Il existe plusieurs structures de données qui permettent de répondre à ce type de question efficacement. Ici, on peut par exemple utiliser un tableau à accès direct : dans chaque case du tableau, on met Vrai si l'élève est déjà arrivé, Faux sinon.

  élèvesArrivés = tableau à nbInscrit cases, remplies à Faux
  Pour chaque présent de 0 à nbPresents-1
     Lire identifiant
     élèvesArrivés[identitifant-1] = Vrai
     Pour chaque inscrit de 0 à nbInscrits-1
        Si non élèvesArrivés[inscrit]
           Afficher inscrit
           Sortir de la boucle
     Si aucun absent n'a été trouvé
        tous les élèves sont présents
L'accès à la table se fait en O(1), et l'algorithme a donc une complexité de O(nbPrésents^2). Par contre, la complexité en mémoire est moins bonne : elle est en O(nbInscrits). Le sujet du problème indique que seuls 5000 Ko sont disponibles pour résoudre ce prolème. En supposant que l'on stocke un booléen sur un octet, nbInscrits ne pourra jamais dépasser 5 000 000.

Pour éviter le problème de mémoire, on peut utiliser une deuxième fois le fait que l'identifiant du premier élève absent est plus petit ou égal au nombre d'élèves présents. On voit donc qu'il suffit de prendre un tableau de taille nbPrésents+1.

  élèvesArrivés = tableau à nbPrésents+1 cases, remplies à Faux
  Pour chaque présent de 0 à nbPresents-1
     Lire identifiant
     Si identifiant < nbPrésents
        élèvesArrivés[identitifant] = Vrai
     Pour chaque inscrit de 0 à nbInscrits-1
        Si non élèvesArrivés[inscrit]
           Afficher inscrit
           Sortir de la boucle
     Si aucun absent n'a été trouvé
        tous les élèves sont présents
La complexité en mémoire devient O(nbPrésents). Cependant, la complexité en temps reste O(nbPrésents^2), ce qui est trop lent vu les contraintes du sujet.
Solution finale
On remarque que l'identifiant du premier élève absent ne fait qu'augmenter. Aussi, il n'est pas nécessaire de tester la présence d'élèves qui ont déjà été testés comme présent à une itération précédente.

  élèvesArrivés = tableau à nbPrésents+1 cases, remplies à Faux
  premierAbsent = 0
  Pour chaque présent de 0 à nbPresents-1
     Lire identifiant
     Si identifiant < nbPrésents
        élèvesArrivés[identitifant] = Vrai
     Tant que premierAbsent < nbInscrits et élèvesArrivés[premierAbsent]
        premierAbsent++
     Si premierAbsent < nbInscrits
        Afficher premierAbsent
     Sinon
        tous les élèves sont présents
La variable premierAbsent ne peut être incrémentée que O(nbPrésents) fois. Le nombre d'itérations total effectué par le corps de la boucle Tant que est donc O(nbPrésents). La complexité de l'algorithme est donc O(nbPrésents) en temps et en mémoire.

Code C++
#include<cstdio>

bool presents[250 * 1000 + 1];

int main(){
  int nb_presents, nb_eleves;
  scanf("%d%d", &nb_eleves, &nb_presents);
  int premier_absent = 0;
  for(int present = 0; present < nb_presents; present++)
  {
    int id;
    scanf("%d", &id);
    id--;
    if(id < nb_presents)
      presents[id] = true;

    while(premier_absent < nb_eleves && presents[premier_absent])
      premier_absent++;

    if(premier_absent == nb_eleves)
      printf("-1\n");
    else
      printf("%d\n", premier_absent + 1);
  }

  return 0;
}
Code Caml
let scan_int () = Scanf.scanf " %d" (fun x -> x)
let show_int n = Printf.printf "%d\n" n
let nb_eleves = scan_int()
let nb_presents = scan_int()

let presents = Array.make (nb_presents+1) false
let premier_absent = ref 1

let _ =
   for present = 1 to nb_presents do
      let id_eleve = scan_int() in

      if id_eleve < nb_presents
         then presents.(id_eleve) <- true;

      while !premier_absent < nb_eleves && presents.(!premier_absent) do
         incr premier_absent
      done;

      if !premier_absent = nb_eleves
         then show_int (-1)
         else show_int (!premier_absent)
  done
Validé !Premier absent
Print