Paris-Saclay & Sorbonne Université

Les universités Paris-Saclay et Sorbonne Université s’entraînent pour SWERC 2020.

Sinon pour tout le monde voici quatre problèmes sur lesquels vous pourriez réfléchir :

À la prochaine séance on va

Parler de vos solutions du google doc,
Parler des 4 problème ci-dessus
Former des équipes pour SWERC, écrire un livret de code.
Voir comment lire l’entrée standard et écrire vers la sortie standard en C++ et Python.
Voir comment chercher en temps O(|x|+|y|) si une chaîne x est une sous-chaîne de y par Knuth Morris Pratt.

… encore un chose que je voulais vous dire. Essayez de lire du code des autres, vous gagnerez du temps à l’implémentation.

En C++ Google Drive\SWERC entrainement 2020-2021\Livres\hitchhikersGuide.pdf est très bien. Regardez l’élégance du code pour subsetsum.
Dans Google Drive\SWERC entrainement 2020-2021\Livres\fuch.pdf admirez la simplicité du code pour le couplage à cardinalité maximum dans un graphe biparti.
Pour Python, pourquoi ne pas lire notre bibliothèque tryalgo. Je crois que ne peux plus vous recommander notre livre, je trouve qu’il contient trop de coquilles. Mi-décembre la traduction en anglais va sortir, et elle bien améliorée. L’explication qu’on y donne de Knuth-Morris-Pratt est très soignée, mais vous l’allez l’avoir en live lors de la prochaine séance.

Lundi 7 décembre 2020, 18h

Une liste d’algorithmes traités dans notre livre. Mais bon, il n’existe pas une liste définitive d’algorithmes cruciaux pour la compétition.