Salut à tous
Je suis en train de m'entrainer en C sur le site France-IOI pour ceux qui connaissent. Je suis arrivé au chapitre efficacité temporelle et je bloque sévère sur un exercice. Le problème doit venir des limitations présentes dans l'énoncé

voilà, à partir de là j'ai élaboré un code, qui passe 18 tests sur les 20 requis pour valider l'exercice.

voici mon code :

Si jamais des gens voient comment améliorer ça niveau mémoire, ou changer complètement l'algo je serai vraiment reconnaissant

Merci d'avance pour vos réponses

tu alloues trop avec calloc

Re je me suis permis de faire le test de mon côté.

effectivement c'est bien un problème vis à vis de la mémoire allouée, même si c'est pas la fonction calloc() en elle-même qui retourne l'erreur. C'est l'exo et donc leur machine virtuelle qui te contraint en taille mémoire en fait.

Ton programme est censé fonctionné pour N jusqu'à 1Mds, P jusqu'à 250k, et t'as une mémoire allouable max de 16M

Du coup faut que tu repenses ton algo sans faire une allocation en O(N) mais plutôt en O(P). Pour info sur cet exo N = 1Mds

Bonsoir, un petit conseil quand tu demandes de l'aide en programmation : mieux vaut fournir au sein de ton post un code formatté plutôt que sous forme de screenshot, ça permet de tester de son côté bien plus facilement et c'est bien plus encourageant par rapport à du code volumineux.

Sur JVC tu peux insérer un programme entre les balises <code></code> en cliquant sur l'icône en forme de chevrons sur la barre supérieure de la zone de texte, comme ci-dessous :

printf("Code mis en forme.\n"); 

Le 07 février 2024 à 16:41:54 :
tu alloues trop avec calloc

merci

Le 07 février 2024 à 19:16:41 :
Re je me suis permis de faire le test de mon côté.

effectivement c'est bien un problème vis à vis de la mémoire allouée, même si c'est pas la fonction calloc() en elle-même qui retourne l'erreur. C'est l'exo et donc leur machine virtuelle qui te contraint en taille mémoire en fait.

Ton programme est censé fonctionné pour N jusqu'à 1Mds, P jusqu'à 250k, et t'as une mémoire allouable max de 16M

Du coup faut que tu repenses ton algo sans faire une allocation en O(N) mais plutôt en O(P). Pour info sur cet exo N = 1Mds

okay je vais essayer de remanier l'algo alors !

Le 07 février 2024 à 21:14:29 :
Y a plus l'aide intégré dans france-ioi ? je me rappelle quand je l'utilisais on pouvait poser une question et un tuteur répondait

je crois que c'est très peu actif à ce niveau

Le 07 février 2024 à 19:23:46 :
Bonsoir, un petit conseil quand tu demandes de l'aide en programmation : mieux vaut fournir au sein de ton post un code formatté plutôt que sous forme de screenshot, ça permet de tester de son côté bien plus facilement et c'est bien plus encourageant par rapport à du code volumineux.

Sur JVC tu peux insérer un programme entre les balises <code></code> en cliquant sur l'icône en forme de chevrons sur la barre supérieure de la zone de texte, comme ci-dessous :

printf("Code mis en forme.\n"); 

je ne savais pas ! merci du conseil

Donc je reposte mon code au bon format

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main() {
      
    int nbEleves, nbPresents, eleve;

    scanf("%d %d", &nbEleves, &nbPresents);

    //tableau de booléens pour suivre les élèves présents
    bool *presence = (bool *)calloc(nbEleves+1, sizeof(bool));

    // Initialiser le premier élève manquant à 1
    int premierManquant = 1;

    for (int i = 0; i < nbPresents; i++) {
        scanf("%d", &eleve);

        // Mettre à jour la présence de l'élève dans le tableau
        if (eleve >= 1 && eleve <= nbEleves) {
            presence[eleve - 1] = true;

            // Si l'élève présent = le premier élève manquant, mettre à jour le premier élève manquant
            if (eleve == premierManquant) {
                while (premierManquant <= nbEleves && presence[premierManquant - 1]) {
                    premierManquant++;
                }
            }
        }

        if (premierManquant > nbEleves)
            printf("-1\n");
        else
            printf("%d\n", premierManquant);
    }

    free(presence);
    return 0;
}

le problème semble venir de l'algo utilisé (effectivement, un tableau a potentiellement 1Millard de cases ça fait beaucoup )
Si certains ont des idées c'est avec plaisir

Merci d'avance

je pense avoir trouvé une piste, une fois que les élèves sont présent, ils sont mis à True : ceci étant figé, je peux supprimer le début du tableau car nous n'avons plus besoin de la chaine de ceux présents

En effet, allouer un tableau de potentiellement 1 000 000 000 de cases c'est trop lourd en terme de mémoire.

L'idée de l'exo c'est de réfléchir à une structure de donnée qui te permettrait de réduire la consommation en mémoire.

Par exemple au lieu d'avoir un tableau de N cases qui stock un boolean, tu pourrais aussi avoir un tableau de P cases dont les valeurs sont les IDs des élèves qui sont arrivés. Lidée serait d'ajouter dans ce tableau l'ID de l'élève qui arrive, à chaque tour de boucle.

Bon là je parle de tableau mais en terme de complexité algorithmique ça serait pas le mieux, donc la structure idéale serait probablement un Set mais j'imagine que t'as pas le droit d'utiliser des libs externes ? Recoder un Set en C ça peut être un peu complexe.

En python ça donnerait un truc du genre:

nb_students = 5  # N
arriving_students = 4  # P
arrivals = [1, 2, 3, 0]

arrived = set()
first_absent = 0
for arrival in arrivals:
    arrived.add(arrival)
    while first_absent in arrived:
        first_absent += 1
    if first_absent >= nb_students:
        print(-1)
    else:
        print(first_absent)

Il y a un petit glitch sur le site qui fait que je peux valider un exercice peu importe le langage
J'ai essayé en python :
nb_students, arriving_students = map(int, input().split()) arrivals = [int(input()) for _ in range(arriving_students)] arrived = set() first_absent = 1 for arrival in arrivals: arrived.add(arrival) while first_absent in arrived: first_absent += 1 if first_absent >= nb_students: print(-1) else: print(first_absent)

Plus de problème de mémoire mais de performance cette fois

Oui j'ai essayé de le faire en C avec une liste chainée (je me suis bien pris la tête ) mais cette-fois ci c'est le temps qui fait défaut...

Ils veulent qu'on implémente un algo d'insertion en O(n*log(n)) ou quoi ?

Bon sinon faut voir si en python y a pas déjà une fonction qui fait le tri en O(n*log(n)), mais en C un peu la flemme là

Le 08 février 2024 à 13:43:15 TopicNorman7 a écrit :
Il y a un petit glitch sur le site qui fait que je peux valider un exercice peu importe le langage
J'ai essayé en python :
nb_students, arriving_students = map(int, input().split()) arrivals = [int(input()) for _ in range(arriving_students)] arrived = set() first_absent = 1 for arrival in arrivals: arrived.add(arrival) while first_absent in arrived: first_absent += 1 if first_absent >= nb_students: print(-1) else: print(first_absent)

Plus de problème de mémoire mais de performance cette fois

bah oui c'est du python, c'est moins performant que du C

Le 08 février 2024 à 15:48:38 :
Oui j'ai essayé de le faire en C avec une liste chainée (je me suis bien pris la tête ) mais cette-fois ci c'est le temps qui fait défaut...

Ils veulent qu'on implémente un algo d'insertion en O(n*log(n)) ou quoi ?

Bon sinon faut voir si en python y a pas déjà une fonction qui fait le tri en O(n*log(n)), mais en C un peu la flemme là

oui vraiment c'est terrible

Au lieu d'utiliser un set, une autre technique ça peut être un tableau trié dans l'ordre croissant des IDs des élèves arrivés, dans lequel on ferait un binary search.

Mais du coup l'insertion et l'accès serait en O(log n) au lieu de O(1) avec le set

#include<bits/stdc++.h>
#define M 250000
using namespace std;
int main ()
{
  set<int>list;
  int P,N,id,min=1;
  scanf("%d %d",&N,&P);
  for (int i = 1 ; i <= P ;i++)
  {
   scanf ("%d",&id);
   list.insert(id);
   if (i == N) printf("-1\n");
   else
   {
     if (min==id)
      for(set<int>::iterator it1 = list.begin() ; it1!=list.end();it1++)
        {
        if (min!=*it1)
          break;
        list.erase(min);
        min++;
        }
     printf("%d\n",min);
   }
  }
  return 0;
}

Voilà au final ce qui m’a carry
Sujet résolu

Le 07 février 2024 à 15:05:14 TopicNorman7 a écrit :
Salut à tous
Je suis en train de m'entrainer en C

ok bravo pour la solution en C++ utilisant la STL