Tout savoir sur le concours ACM-ICPC (sur Wikipédia), qui depuis 2018 n’est plus soutenu par l’ACM.
Calendrier 2015
- 10/09 Recherche de motifs
- 17/09 Programmation dynamique
- 23/09 Structures de données
- 02/10 Plus courts chemins
- 08/10 Couplages et flots
- 15/10 Exploration exhaustive
- 22/10 Géométrie
- 05/11 4 problèmes à résoudre
- 12/11 Liste des problèmes
2015
- 20/11 Let’s go to Porto!
SWERC 2014
- Exploration exhaustive (2)
- Plus courts chemins (2)
- Programmation dynamique (1)
- Recherche de motifs (1)
- Couplages et flots (1)
- Géométrie (2)
- Fast Fourier Transform WTF (1)
SWERC 2013
- Structures de données (tas, tables de hachage) (2)
- Plus courts chemins (1)
- Exploration exhaustive (1)
- Mathématiques (1)
- Recherche de motifs + mathématiques (1)
- Programmation dynamique (dont réécriture WTF) (2)
- Couplages et flots (1)
- Géométrie (1)
Liste des problèmes
Chaînes de caractères
- 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
- 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
- Requêtes de minimum sur un intervalle
- Requêtes de somme sur un intervalle
Intervalles
- Arbre d’intervalles
- Union d’intervalles
- Couverture d’intervalles
Graphes
- DFS : Parcours en profondeur
- BFS : Parcours en largeur
- 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
- Graphes avec poids positifs ou nuls (Dijkstra)
- Graphes avec poids arbitraires (Bellman-Ford)
- Toutes paires source-destination
- Grille
Couplages et flots
- Couplage maximum biparti
- Couplage parfait de poids maximal (hongrois, Kuhn-Munkres)
- Couplage planaire sans croisement
- Mariage stable (Gale-Shapley)
- Flot maximal (Ford-Fulkerson, Edmonds-Karp)
- 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
- Plus long chemin dans un arbre
Ensembles
- Sac à dos
- Rendu de monnaie
- SUBSET-SUM
- k-somme
Points et polygones
- Enveloppe convexe
- Paire de points les plus proches
- Polygone rectilinéaire simple
Rectangles
- Plus grand carré dans une grille
- Plus grand rectangle dans un histogramme
- Plus grand rectangle dans une grille
- Union de rectangles
- Union de rectangles disjoints
Calculs
- 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
- Le compte est bon