Comment réviser pour la demi finale ?

Bonjour tout le monde !

Je m'apelle Lostindark (enfin, pas vraiment vous vous en doutez mais j'aime qu'on m'apelle comme ça !), et c'est la première année ou je participe au Prologin.
J'ai été sélectionné à mon grand étonnement pour les demis finales, et du coup, j'aimerais bien avoir quelques conseils des anciens et des plus fort pour réviser pour cette epreuve. Evidemment, j'ai prévu de faire des exercices d'entrainement sur Prologin (et peut-être sur françe ioi ?), mais je n'ai pas beaucoup de temps donc je n'en ferais que quelques-un.
Du coup voilà, est-ce que vous auriez des méthodes de révision, exercices particuliers (ceux que vous trouvez le plus instructif ici par exemple), algorithmes a connaitre etc ... A me conseiller ?

Je ne pense pas avoir le niveau pour arriver en finale, mais j'aimerais bien réussir à y aller quand même, quitte a finir dernier car je doit-être un des pires stratèges de l'histoire de l'humanité (c'est pas faute d'avoir lu l'art de la guerre ...) et donc pour faire une IA c'est peut pratique.

Sur ce, domo arigato pour vos conseils ! :)

Bonjour, Lostindark ! Mon pseudonyme est généralement Frigory, mais j'apprécie d'être désigné par mon prénom.

>> je doit-être un des pires stratèges de l'histoire de l'humanité

On est nombreux à ne rendre aucune IA, ou une IA très simpliste.
Je pense quand même que je vais essayer d'être plus productif cette année.

>> J'ai été sélectionné à mon grand étonnement pour les demis finales

Ce n'est pas très difficile, tu l'auras sans doute remarqué !

>> est-ce que vous auriez des méthodes de révision, exercices particuliers

L'important est surtout connaître les structures de données élémentaires : pile, file, liste, matrice, arbre binaire, arbre quelconque. Et avoir un minimum de connaissances mathématiques et algorithmiques, avec par exemple la récursivité, les algorithmes dynamiques, les graphes, la trigonométrie, les vecteurs…
Il faudrait au moins que tu nous indiques quel niveau tu as réellement pour que l'on puisse te donner plus d'indications. France-IOI enseigne plus ou moins toutes ces notions, mais je doute que tu puisses tout maîtriser d'ici la demi-finale. Sache toutefois que l'accès en finale est relativement facile.

>> j'apprécie d'être désigné par mon prénom.
D'accord, alors bonjour Sylvain !

>> On est nombreux à ne rendre aucune IA
Bon, alors ça me laisse une chance ! Cool ! \^\^

>> ou une IA très simpliste.
J'étais à la limite de l'euphémisme quand je disais dans les pires stratèges, du coup je pense que celles là me vaincront x)
(Ps : je ne suis pas pessimiste, mais plutôt dans l'optique connaît tes limites, et apprend de toutes tes défaites a advance war et autres jeux de stratégies que t'es pas vraiment fait pour ça ... \^\^')

>> Ce n'est pas très difficile, tu l'auras sans doute remarqué !
Oui, ce fut en effet assez simple x)

Pour mon niveau, en maths c'est terminale, et en algo, je connais dans ce que tu as cité, pile, file, liste, matrice (merci a la spé maths), récursivité et graphe (mais je n'en m'en suis pas ou peu servi, par exemple je connais Dikstra mais je ne l'ai jamais implémenté quoi, et des algos récursifs j'y pense de temps en temps mais c'est peu fréquent, je ne me suis pas assez familiarisé avec eux pour que ça soit instinctif ...)

>> l'accès en finale est relativement facile.
Ah bon ? Relatif dans quelles proportions ? :o
Je m'attendais a du challenge, et à passer les épreuves avec difficultés ... On verra bien \^\^

Bon, merci de ta réponse ! Je vais essayer de me renseigner sur les arbres, et approfondir un peu ma connaissances des autres domaines. J'espère qu'avec la connaissance de mon niveau tu aura d'autre conseils !

Merci d'avance ! :)

Relativement facile, quand on est de France-IOI.
Plusieurs personnes sélectionnées aux IOI n'ont notamment pas réussi à passer la demi-finale lors de leur première participation à Prologin, comme quoi sans entraînement...
Par ailleurs, j'avais calculé il y a un ou deux ans que seuls 30 % des demi-finalistes n'ayant jamais participé à la finale étaient finalement retenus. Si en plus on se mettait à compter les nouveaux France-IOIciens sérieux (donc quasi sûrs d'être sélectionnés)... Bref, Sylvain ne se rend pas compte de la difficulté pour un "non-initié".
À part ça, pas besoin de maîtriser les arbres binaires pour Prologin (voire même de connaître), il suffit de voir les annales : il y a déjà bien à faire avant. Regarde-les donc, vois où tu bloques, comprends la solution, maîtrise sa généralisation et enfin recommence.

>> Relativement facile, quand on est de France-IOI.

Aie ... Je suis sur leur site mais j'ai pas un bon niveau du tout comparé a certains ... \^\^'

>> Plusieurs personnes sélectionnées aux IOI n'ont notamment pas réussi à passer la demi-finale lors de leur première participation à Prologin, comme quoi sans entraînement...
Par ailleurs, j'avais calculé il y a un ou deux ans que seuls 30 % des demi-finalistes n'ayant jamais participé à la finale étaient finalement retenus. Si en plus on se mettait à compter les nouveaux France-IOIciens sérieux (donc quasi sûrs d'être sélectionnés)...

Ça c'est très décourageant x)

>> Bref, Sylvain ne se rend pas compte de la difficulté pour un "non-initié".

Comment on devient initié ? Y a un rituel ? :D

>> Regarde-les donc, vois où tu bloques, comprends la solution, maîtrise sa généralisation et enfin recommence.

Donc la méthode traditionnelle ? Même pour réviser "à fond" ?
Ok, j'essayerais ! :)
Mais par contre, comment je peut comprendre la solution si je bloque ? Y a des corrections ? Ou ça ? :o

Merci pour ton aide ! ;)

>> Relativement facile, quand on est de France-IOI.

Obligatoire, quand on est de France-IOI (j'espère que je ne me ferai pas jeter pour ça).
J'ai accédé à la demi-finale de Prologin en troisième, alors que je programmais depuis à peine deux ans et quelques en C et C++, qui m'ont été enseignés par l'association Jeunes-Science Bordeaux qui m'a fait connaître Prologin.
En seconde, je codais toujours comme un porc (je n'ai cessé de le faire réellement que trois ans plus tard, c'est-à-dire l'an dernier), et j'avais des connaissances mathématiques et algorithmiques extrêmement limitées (ça m'étonnerait que je susse ce qu'était une file ou même une pile à l'époque). J'ai quand même été sélectionné pour la finale.
Je considère ainsi que l'accès à la finale est relativement facile, même si le niveau a augmenté depuis quatre ans (du fait de la hausse de la limite d'âge et une plus grande influence de l'informatique auprès des jeunes recrues).
Toutefois, mon jeune âge avait sans doute joué, et en parallèle je maîtrisais un petit peu les fonctions récursives, ainsi que d'autres techniques algorithmiques élémentaires. Ça se résumait surtout à énormément de pratique pour très peu de théorie (en gros, je codais tout seul dans ma chambre).
Je n'ai découvert France-IOI que l'année suivante, en première.

>> matrice (merci a la spé maths)

En fait, j'entends surtout algorithmes sur des tableaux à deux dimensions, pas ce qu'on voit en spécialité mathématiques. Le genre d'algorithmiques quadratiques bateau que l'on trouve au niveau 2 sur France-IOI et que j'adorais faire quand j'étais gamin.

>> pas besoin de maîtriser les arbres binaires pour Prologin

En effet, j'exagère, les arbres généralistes sont bien plus importants. Mais à ma demi-finale en 2010, l'épreuve écrite était à peu près infaisable si on n'utilisait pas un arbre binaire comme structure de données. M'enfin c'était une exception ; tout le monde en a souffert.

>> Donc la méthode traditionnelle ? Même pour réviser "à fond" ?

En effet, c'est probablement stratégique de voir sur quels types de problèmes tu bloques, plutôt que de tout faire. Déjà, l'idée est de maîtriser un minimum la méthode France-IOI : reformulation du problème, dessins pour modéliser la situation, pseudo-code courts pour structurer l'algorithme. Personnellement, je la maîtrise très mal parce que j'ai toujours la flemme de prendre un papier et un stylo,mais ça te permettra de visualiser sur quel type de problème tu bloques et de t'exercer sur les problèmes qu'il faut.

>> je ne suis pas pessimiste, mais plutôt dans l'optique connaît tes limites, et apprend de toutes tes défaites a advance war et autres jeux de stratégies que t'es pas vraiment fait pour ça

Je suis également exécrable en jeux de stratégie, et pourtant le principe m'a toujours amusé, de voir l'économie dans un jeu vidéo plutôt que la réalité.
Il faut une idée… Même parmi les dix premiers, certains disent : « Franchement, si j'ai pu arriver là, c'est que ce n'était pas si compliqué ! » Le classement à la finale est assez aléatoire ; cela dit j'ai à chaque fois été dans les 50.

>> J'ai accédé à la demi-finale de Prologin en troisième, alors que je programmais depuis à peine deux ans et quelques en C et C++

Ça ne veut pas dire grand chose, certains font plus que d'autres en deux ans : http://codeforces.com/profile/scott_wu.

>> En seconde, je codais toujours comme un porc

Là aussi on s'en fiche, ce n'est qu'au plus un critère de départage. Tant que ton code compile et résout les exercices à l'épreuve machine...

>> je maîtrisais un petit peu

Ça y est, tu te remets à écrire n'importe quoi.

En fait, avec les deux premières expressions que tu as citées, je cherchais à montrer que je n'avais vraiment aucune connaissance théorique… Mais je suppose que tu t'en doutes.

>> Ça y est, tu te remets à écrire n'importe quoi.

Oui, ça ressemble à un oxymore, j'avais la flemme de formuler mieux que ça.

Rebonjour ! Merci pour vos conseils, j'ai lu quelques sujets des années précédentes et j'ai essayé de les faire, et je suis confronté à un "léger" problème. Une question récurrente est celle du choix de la structure de donnée. De manière intuitive j'arrive presque toujours a me débrouiller pour en trouver une qui m'aille, mais le truc, c'est que c'est intuitif, donc pas forcément bon ... Est-ce que vous auriez des conseils pour bien choisir ses structures de données ?

Merci beaucoup ! :)

Ce que je fait, c'est de me demander : de quelles opérations j'ai besoin ? Quelle compléxité est-ce que je vise pour cette opération ?

Avec ça, tu vas relativement facilement trouver ce que t'as besoin :-)

Wow, ça s'appelle du déterrage là… Mais j'approuve.