Quali strutture di dati e algoritmi di base si dovrebbero imparare prima di iniziare la programmazione competitiva?

Sei fortunato. Ci sono un sacco di risorse.

Suggerisco di iniziare con l'USACO Training Gateway (pagina su Delos). È una raccolta di centinaia di problemi e tutorial che hanno lo scopo di aiutare le persone ad allenarsi per la USACO. Ma si potrebbe usare per allenarsi essenzialmente per qualsiasi competizione di programmazione. Potrebbe iniziare come piuttosto basilare per voi, ma non appena entrerete nell'ultima parte del capitolo 1 e nel capitolo 2, coprirete alcuni concetti di teoria dei grafici così come la programmazione dinamica. E' probabilmente una delle migliori risorse là fuori per iniziare ad allenarsi per le competizioni.

Un'altra serie di tutorial che suggerisco è quella di TopCoder (Algorithm Tutorials). Trovo che questi tutorial siano migliori di quelli forniti da USACO. Tuttavia, i problemi che i tutorial TopCoder forniscono non sono buoni come i problemi USACO.

Ho approfondito qui: Come può un principiante imparare a programmare? La prima risposta è la mia.

Per quanto riguarda algoritmi e tecniche specifiche, sarebbe difficile fornire una lista completa di tutto. Uno dei primi tutorial nel Gateway USACO fornisce una breve lista di tipi di problemi che è probabile vedere in una competizione di programmazione, ma non dà veramente una lista di algoritmi.

Alcuni algoritmi/tecniche di base che ogni programmatore competitivo di successo ha nel suo arsenale sono:

1. Depth-First Search (Graph Search)
2. Breadth-First Search (Graph Search) (incluso Flood-Fill)
3. Dijkstra's Algoritmo (Shortest Path)
4. Floyd-Warshall's Algoritmo (Shortest Path)
5. Algoritmo di Bellman-Ford (percorso più breve)
6. Algoritmi Greedy
7. Programmazione dinamica (inclusi i problemi Knapsack)
8. Ricorsione
9. Alberi a scansione minima
10. Ricerca binaria e lineare
11. Un po' di combinatoria di base e teoria dei numeri.

Ti serviranno anche alcune strutture dati:

1. Pila
2. Queue
3. Hash Table
4. Heap
5. Bag (forse. Bag (forse. Non l'ho visto usare spesso nelle competizioni di programmazione)

Inoltre, queste sono le basi. Se volete conoscere concetti più avanzati, sentitevi liberi di leggere cose online o libri. Suggerisco Introduzione agli algoritmi di Cormen e Algoritmi di Sedgewick. Introduction to Algorithms copre molto, ma è molto più orientato alla matematica. Algoritmi di Sedgewick è più pratico perché fornisce codice Java mentre Introduzione agli algoritmi fornisce pseudocodice.