TD

Table of Contents

1 TD01

Ce TD est surtout une introduction. Nous allons voir les entrées sorties en C++ et comment utiliser map et vector. Inscrivez vous sur la liste puis les problèmes à faire sont:

  • 10055: Très facile
  • 11559: Facile
  • 272: Lecture d'entrée
  • 10420: Utilisation de map
  • 12205: SWERC2009 I (Bonus)
  • 12269: SWERC2010 A (Bonus)
  • 12394: SWERC2011 H (Bonus)
  • 12550: SWERC2012 G (Bonus) (Remarque: l'entrée n'est pas terrible j'ai ajouté des choses à ce propos)

2 TD02

Au programme de ce TD, génération exhaustive, backtracking, glouton et pour quand même avoir un algo malin pendant le TD, une application maligne de la recherche binaire. Les problèmes sont les suivants:

Quelques conseils: Les bonus ne sont triés ni par difficulté ni par type de problèmes. Je vous conseille de réfléchir avant de coder, pas seulement à l'algorithme (parfois une programmation dynamique compliquée n'est en fait qu'un glouton direct) mais aussi à l'organisation de votre programme (parfois un glouton compliqué n'est en fait qu'une boucle sur un tableau d'entier). Vérifiez également que la complexité de votre algorithme sera suffisamment rapide sur les pires entrées (combien d'opérations peut faire votre ordinateur en 1 sec ?). Globalement mieux vaut bien réfléchir avant, écrire du pseudo code pour avoir un programme clair et concis (pour info et sans l'avoir fait exprès, mes programmes non bonus font tous 42 lignes \o/) que coder rapidement et débugger longtemps.

3 TD03

Pendant ce TD, encore du backtracking et un peu de programmation dynamique. Les problèmes sont les suivants:

  • 11085: Backtraking
  • 357: Programmation dynamique (pièces)
  • 10616: Programmation dynamique (sac à dos)
  • 12393: SWERC2011 G (Bonus)
  • 12547: SWERC2012 D (Bonus)

4 TD04

Encore de la programmation dynamique avec deux types de problèmes, le sous rectangle de somme maximale et la plus longue sous suite croissante. Voici les problèmes:

Edit: Le problème 481 est en fait pour la prochaine scéance où nous verrons comment garder la séquence. À la place il y à calculer la taille de la LIS. Je vais sans doute bientôt ajouter un validateur sur ce site en attendant un jeu d'entrées sorties est sur la page testcases. Voci la description du problème:

Une entrée consiste en un entier N suivi de N entiers (a_1,…a_N) (tout tient dans des int). Vous devez renvoyer /Case i: / où i est le numéro du testcase en commencant à 1 suivi par la longueur de la LIS (longuest increasing subsequence (subsequence dans le sens, 1 3 est subsequence de 1 2 3) ). Regarder les IO pour en savoir plus sur le format attendu.

La complexité attendue est en O(Nlg(N)). Pour vous donner une idée, en compilant avec -O2 et en utilisant ios::sync_with_stdio(false); votre code doit mettre moins de 2 secondes. Vous pouvez utiliser time ./a.out < LIS.in pour mesurer le temps. Si quelqu'un le code en O(n^2) je veux bien savoir le temps que ça met. Edit: Plus de 200 sec, l'ordre de grandeur de difference est de 1000 à vous de le coder en nlg(n).

5 TD05

Des algorithmes de string ! La suite de la LIS avec la reconstruction de solution en O(nlg(n)) et une nouvelle structure de donnée les suffix array avec une construction "simple" en O(nlg^2(n)) permetant de résoudre le longest commun prefixe (LCP) of two given suffix en O(lg(n)). (Note on peut facilement adapter pour avoir du O(nlg(n))) et avec un range minimum query (voir futur TD) faire le LCP en O(1) avec un prétraitement en O(nln(n)).

Voici les problèmes:

  • 481: LIS
  • 760: SA, LCP (Bonus fortement recommandé)
  • 11107: SA (Bonus)
  • 12206: SWERC2009 J (Bonus)

J'ai fait des testcases pour le problème suivant: lisant une chaine de charactères, retourner ses suffixes triés (le faire en O(nlg^2(n))).

Et pour le problème: lisant n le nombre de chaines, puis n chaines. Pour chaque chaine retourner l'indice de la permutation donnant la plus petite chaines (cf problème 719 mais ses testcases ont changés ce que le rend compliqué avec des SA).

6 TD06

Suite à un problème de salle, peu de problèmes cette semaine mais plusieurs choses théoriques. Nous allons finir le problème des LIS et des SA et nous allons voir une structure de donnée permettant le calcul d'une somme sur un intervalle et la modification de valeurs en temps O(ln(n)).

Voici le problème:

Et n'oubliez pas il y a des testcases pour la LIS et le SA, pour le moment il n'y a pas de validateur automatique mais il faut résoudre ces problèmes.

Vous pouvez lire l'article original de Peter Fenwick ici. La feuille de TD est disponible ici.

7 TD07

Toujours des problèmes de salles. Nous allons parler Range Minimum Queries (RMQ) et de Lowest Common Ancestor (LCA). Le but est de savoir coder rapidement des choses efficaces pour ces problèmes (et la version dynamique) mais nous verrons aussi comment avec un prétraitement de O(n) répondre en O(1) aux requêtes.

Voici les problèmes:

  • 11235: Application assez directe
  • 11297: QuadTree (Bonus)
  • 11402: Très dynamique (Bonus)
  • 12389: SWERC2011 B (Bonus)

La feuille de TD est disponible ici. Un bon article sur les problèmes de cette semaine ici.

8 TD08

Dernier jour de problème de salle (normalement). Nous avons fait des problèmes du SWERC2012 et SWERC2011 au tableau. Il faut faire le problème I du SWERC2011. Notez que des éléments de correction sont disponible ici et .

Le problèmes est le suivant:

9 TD10

Ce week-end les qualifications pour le Google Code Jam commencent. Au programme des problèmes des années précédentes. À faire au choix 4 parmi:

10 TD11

Aujourd'hui nous allons un peu parler des concours off-line et de comment utiliser gmp et openmp, puis nous attaquons des problèmes de graphes (Kruskal, BFS, Floyd Warshall et Dijkstra). Voici les problèmes (c'est peut-être long on continuera sans doute la semaine prochaine):

11 TD12

Des flots, et en bonus divers problèmes de graphes. A priori il ne nous reste plus qu'à parler de géométrie, donc certains problèmes bonus de cette semaine seront surement à faire la semaine prochaine.

Voici les problèmes:

  • 820: Word Final 2000 (comme quoi le niveau ne baisse pas toujours), Flots
  • 11506: Min cut
  • 12176: SWERC2008 A (Bonus)
  • 12182: SWERC2008 G (Bonus)
  • 12544: SWERC2012 A (Bonus)
  • 12549: SWERC2012 F (Bonus)

12 TD13

Un dernier problème de graphe et un peu (vraiment peu en fait) de géométrie.

  • 558: Bellman Ford
  • 378: Intersection de lignes
  • 634: Intérieur d'un polygone
  • 10566: Computational geometry

13 TD14

Le dernier TD ! Au programme, finir les TD précédents, deux exo qui étaient à l'exam de l'an dernier. Et implémenter l'algorithme de KMP vu en cours d'algo 2.

Regardez le problème à propos de KMP, le format sera sensiblement le même pour l'exam. L'archive contient le fichier a remplir pour résoudre le problème (le but est uniquement d'avoir un nom canonique) un fichier small.in qui contient de petites entrées, un fichier small.res qui est le résultat attendu pour cette entrée. N'hésiter pas a utiliser diff pour compararer votre sortie avec celle attendue. (En pratique j'utilise diff -wq). Un fichier big.in qui est le fichier d'entrée utilisée. Lors du partiel vous pourrez soumettre en ligne le shasum de votre fichier pour vérifier que vous avez le bon résultat. Aujourd'hui il y a un fichier .shasum qui contient le shasum. Vous programmes devront compiler sans erreur avec g++ -O2, et s'exécuter en moins de 10 sec. Vous pouvez utiliser time pour mesurer le temps, en pratique j'utilise ulimit -t 10 pour tuer tout programme demandant plus de 10 sec de cpu.

Voici les problèmes:

Et l'énnoncé de KMP. On définit le F(n) le nième mot de Fibonnaci comme:

  • F(0)=0
  • F(1)=1
  • F(n)=F(n-1)F(n-2)

Chaque testcase contient une ligne indiquant un entier 1<n<31 suivi d'une ligne contenant un mot (de taille < 1000000). Si ce mot apparait dans F(n) vous devez répondre Yes! sinon No! sur une ligne.