Prologin 2016

Salut à tous,

La qualification du concours Prologin touche à sa fin (le 3 janvier) et la prochaine étape se déroulera en février 2016 dans les grandes villes de France.

Participez-vous à ce concours ? Venant de Lyon, j'aimerais savoir si il y a des Agrumes parmi nous qui aient demandé l'ISEG de Lyon pour passer la demi-finale.

Je vous écoute !

J'ai essayé d'y participer, mais mes connaissances de 3^ème en maths ne m'ont pas permis de réussir tous les problèmes (j'ai réussi 3 problèmes sur 5).

Par expérience, c'est suffisant pour être sélectionné.

ThuleMalta : accroche toi, c'est une superbe expérience, et les premières phases de sélection sont très souples !

Je participe aussi, en ocaml ! C'est ma dernière année en tant que participant donc il faut au moins que j'aille jusqu'au bout une fois. Par contre je serais certainement plus du côté de Paris.

Tu as déjà été en finale ?

Malheureusement non, j'ai même pas fait de demie-finale, j'étais assigné à des centres beaucoup trop loin de chez moi en terminale, et j'ai pas eu le courage de le faire en classe préparatoire.

Bonne idée que d'encourager les gens a venir ! ThuleMalta, je ne pense pas que les connaissances en math soient vraiment importantes. Je me suis qualifié en 4em et 3em pour la finale, c'est donc que ça doit suffire ce niveau ! Prologin c'est moins des math que de l'algorithmie, ce qui peut s'apprendre totalement indépendamment de l’école (via wikipedia pour les algos, des tutoriels, et la quantité impressionnante d'exos sur le site france-ioi) Et 3 sur 5 c'est pas mal. En fait le deux autres nécessitent d'avoir déjà abordé ce type de problèmes…

Arf ! Me dis pas ça, j'ai pas encore commencé ! x(

Prologin est vraiment une super expérience. Je n'en garde que de bons souvenirs

Pour avoir été en finales, c'est vraiment une expérience que je n'oublierais pas ! Pour dire, ce que j'y ai appris me sert actuellement dans mon parcourt universitaire (Bac+3) !

Cependant, le concours à tout de même un certain niveau.

Salut,

Je l'ai commencé à le faire mais je me suis arrêté au niveau trois donc je ne serais pas en demi-final.

Je re-tenterais l'année prochaine

Pourquoi t’arrête au niveau 3 ? Où bloques-tu ? Essaye encore, fais des recherches au pire. Bref, aide toi et le ciel t'aidera, dit-on …

Déjà, certaines années, 3 exercices, ça suffi à allez en demi-finale.

L'algorithmie, selon moi, c'est résoudre des problèmes mathématiques grâce à l'informatique. Quand je dis que je n'ai pas le niveau pour les exercices 4 et 5, c'est que je ne sais même pas par ou commencer.
@ache Faire des recherches sur Internet ça n'a pas grand intérêt à mon avis, le but c'est de trouver par soi-même. Être sélectionné en cherchant sur Internet pour ensuite ne savoir rien faire une fois arrivée la demi-finale, c'est pire que de ne réussir qu'une partie des exercices soi-même et n'être pas sélectionné (selon moi).

Après, si 3 exercices suffisent à aller en demi-finale, je croise les doigts.

Pourtant, c'est dans la recherche que tu trouveras le plus de ressources aptes à pouvoir t'aider à préparer les demi-finales … Curieux non ?

Il faut être capable de se dire que l'on ne réinventera pas tous. Que des gens plus intelligents (ou pas d'ailleurs, ça n'a pas d'importance) que nous on déjà bien étudier certains problèmes et qu'ainsi comprendre leurs démarches nous apporte beaucoup.

Pour dire, le dernier exercice de qualification de l'édition 2012, relaxation En fait, pour bien comprendre le problème, il faut allez très loin.

Certains l'on fait avec de la programmation dynamique. À cette époque, je ne connaissais pas la programmation dynamique. J'étais incapable de la même en œuvre. C'est à Prologin justement que j'ai appris. Mais pour m'y qualifié, j'ai utilisé un algo peu connu. Imagine l'effort que ça a été pour étudier ce problème dans les détailles afin de coder l'algo issue de cet article.

Du coup, ben le problème du rendu de monnaie, je le connais bien maintenant ^^"

Je m’arrête avec un dernier exemple.

Cette année j'ai à coder un algorithme en 2 phases de Kociemba … Le gars qui a prouvé que le nombre de dieu du rubik's cube était 20. Son algorithme, impossible pour moi de le coder. Mais par-contre, la méthode, je l'ai bien comprise. Et si jamais un jour je repère un modèle identique dans un problème que je veux résoudre, je pourrais appliqué Kociemba à ce problème.

Idem pour l'algorithme de recherche KMP, l'algorithme de Borůvka, …

D'autant plus que pour les algorithmes 4 et 5, ce sont des algorithmes qu'on rencontre dans beaucoup de problèmes courants.

Certains font prologin avec le bagage d'une classe préparatoire, et 5 ans passés à chercher de plus que toi. Pourquoi n'aurais-tu pas le droit de chercher toi aussi ? C'est l'un des meilleurs entrainements pour progresser efficacement.

Bonsoir !

C'est ma première participation (je suis en 1eS), et comme @ThuleMalta j'avoue que je bloque vraiment sur l'exercice n°4 tout particulièrement. Est-ce que l'un d'entre vous à une piste pour nous mettre sur la voie (il ne s'agit pas de donner la réponse bien sûr je trouve ça totalement inutile :p) ? J'ai déjà pensé à des algorithme comme Kruskal, la théorie des Graphes, mais j'ai lu qu'il fallait ici utiliser la programmation dynamique, que je n'ai jamais pratiquée …

Merci par avance pour vos réponses

A toi de chercher, de voir… Essaye de bien identifier le problème, c'est un problème classique. Ça semble effectivement ressembler a un graphe. Par contre, si tu as vu quelque part que c'était de la programmation dynamique… Que ça ne te bloque par pour autant ! Ne change pas de voie de recherche simplement en ayant vu ça. La programmation dynamique consiste, de base, simplement a retenir des calculs pour éviter de les refaire ensuite, et calculer des résultat en fonction des autres. Ce principe peut très bien être appliqué avec des algos de graphe ! (en fait c'est même très lié)

Souvent, Wikipédia est une très bonne source d'information.

Et souvent … Wikipédia en anglais en est encore une meilleure !

Si tu veux t’entraîner à la programmation dynamique, essaye des exercices comme ceux là : https://prologin.org/train/2014/semifinal/deadline Ou sur France-IOI

Salut,

Vous me trouverez à Lille en DF.

Arf, t'es loin :/

J'espère sur Nantes pour moi.

Je bloque au troisième problème "La Prophétie". Si quelqu'un peut me donner un coup de main…

Voilà mon 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

using namespace std;

int main()
{
    int volTempete, nbMontagnes;
    cin >> volTempete >> nbMontagnes;

    int altMontagnes[nbMontagnes];
    int altMinMontagne = 100000, altMaxMontagne = -100000;
    for(int iMont(0); iMont < nbMontagnes; iMont++)
    {
        cin >> altMontagnes[iMont];

        if(altMontagnes[iMont] < altMinMontagne)
            altMinMontagne = altMontagnes[iMont];

        if(altMontagnes[iMont] > altMaxMontagne)
            altMaxMontagne = altMontagnes[iMont];
    }

    int volTemporaire = -1;
    int altMer = altMinMontagne;
    int altTempete = altMaxMontagne + 1;

    while(volTemporaire != volTempete)
    {
        altTempete--;
        volTemporaire = 0;

        if(altTempete == altMer)
            break;

        for(int iMont(0); iMont < nbMontagnes; iMont++)
        {
            if(altTempete - altMontagnes[iMont] >= 0)
                volTemporaire += altTempete - altMontagnes[iMont];
        }
        //cout << "Vol : " << volTemporaire << endl;
    }

    cout << altTempete;
}

1

    while(volTemporaire != volTempete)

Euh, tu voudrais pas plutôt faire :

1

    while(volTemporaire > volTempete)

On a fait différemment. J'ai commencé par trié les montagnes …

Personnellement, j'ai fait un algo qui augmente une variable niveau de la mer de 1 et qui compte le nombre de montagnes submergées à chaque itération.