regarder le fichier de christoph fuch_bien.pdf (RMQ, bigint, ... plein de choses à prendre !)
https://sites.google.com/site/indy256/algo/fenwick_tree
Big integer
Faire des algos de flots et de matching plus courts


Liste des problèmes
===================

Chaînes de caractères
OK  Recherche de motifs (Knuth-Morris-Pratt, Rabin-Karp)
    Arbre lexicographique
    Plus grande période
    Plus long palindrome (Manacher)
    Facteur commun maximal

Programmation dynamique

    Plus court chemin dans un DAG
    Plus longue sous-séquence commune
    Distance d'édition de Levenshtein
    Plus longue sous-séquence commune
OK  Plus longue sous-séquence croissante
    Stratégie gagnante dans un jeu à deux joueurs
    Multiplication d'une séquence de matrices

Tableaux

OK  Fusion de listes triées
    Fenêtre avec k éléments distincts
OK  Somme d'un intervalle (différence de sommes prefixes)
    Doublon d'un intervalle
    Plus grande somme d'un intervalle
OK  Requêtes de minimum sur un intervalle (treap, segment tree)
OK  Requêtes de somme sur un intervalle (treap, segment tree)

Intervalles

OK  Arbre d'intervalles
    Union d'intervalles
    Couverture d'intervalles

Graphes

OK  DFS : Parcours en profondeur
OK  BFS : Parcours en largeur
OK  Composantes connexes
OK  Composantes biconnexes
OK  Tri topologique
OK  2-SAT
OK  Composantes fortement connexes

Cycles

OK  Chemin eulérien
    Problème du postier chinois (Google Hash Code 2014)
    Cycles de ratio poids sur longueur minimal (Karp)
    Cycles de ratio coût sur temps minimal

Plus courts chemins

    Graphes avec poids 0 ou 1
OK  Graphes avec poids positifs ou nuls (Dijkstra)
OK  Graphes avec poids arbitraires (Bellman-Ford)
OK  Toutes paires source-destination
    Grille (dynamique ?)

Couplages et flots

OK  Couplage maximum biparti
OK  Couplage parfait de poids maximal (hongrois, Kuhn-Munkres)
    Couplage planaire sans croisement
OK  Mariage stable (Gale-Shapley)
OK  Flot maximal (Ford-Fulkerson, Edmonds-Karp)
OK  Coupe minimale
    Coupe minimale pour graphe planaire (plus court chemin dans le graphe dual)
    Largeur d'un ordre partiel (nombre d'el - couplage max ?)

Arbres

OK  Arbre couvrant de poids minimal
    Requêtes d'ancêtre commun le plus proche (variante treap : on peut utiliser RMQ)
OK  Plus long chemin dans un arbre (dynamique)

Ensembles

    Sac à dos
    Rendu de monnaie
    SUBSET-SUM
    k-somme

Points et polygones

OK  Enveloppe convexe
OK  Paire de points les plus proches
    Polygone rectilinéaire simple

Rectangles

OK  Plus grand carré dans une grille (dynamique)
OK  Plus grand rectangle dans un histogramme
OK  Plus grand rectangle dans une grille
    Union de rectangles
    Union de rectangles disjoints

Calculs

OK  PGCD
OK  Bézout
OK  Coefficients binomiaux
OK  Exponentiation rapide
OK  Nombres premiers
    Évaluation d'une expression arithmétique
    Systèmes d'équations linéaires

Exploration exhaustive

    Sudoku
OK  Énumération de permutations (next_permutation)
    Le compte est bon