longest increasing sequence : buggué en mode strict 3 4 7 4 5 6 1 2 3 4 5 6 7 8 9 10
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
z-function
Hopcroft Karp


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

    Fusion de listes triées
    Fenêtre avec k éléments distincts
    Somme d'un intervalle
    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

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

Graphes

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

Cycles

    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)
    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
    Mariage stable (Gale-Shapley)
OK  Flot maximal (Ford-Fulkerson, Edmonds-Karp)
OK  Coupe minimale
    Coupe minimale pour graphe planaire
    Largeur d'un ordre partiel

Arbres

    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
    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
    Bézout
    Coefficients binomiaux
    Exponentiation rapide
    Nombres premiers
    Évaluation d'une expression arithmétique
    Systèmes d'équations linéaires

Exploration exhaustive

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