Se non diversamente specificato, gli orari sono 09:00 - 13:00 e 15:00 - 19:00 nei giorni di lezione, mentre 08:30 - 12:30 e 14:30 - 19:30 nei giorni di gara.
- Introduzione. Programmazione dinamica come implementazione efficiente di una ricorrenza.
- Esempio del calcolo del binomiale. Approccio top-down vs. bottom-up;
- Più lunga sottosequenza comune (LCS);
- Più lunga sottosequenza crescente (LIS);
- Equivalenza tra LCS e LIS;
- Corollario: LCS tra due array, almeno uno dei queli è una permutazione, si fa in O(NlogN).
...il resto si impara mettendoci le mani!
Problemi a cui pensare:
- Dati tre mazzi di carte A=[a1,…,an], B=[b1,…,bm] e C=[c1,…,cn+m], determinare se C può essere ottenuto da un singolo shuffle (miscuglio all'americana) di A e B.
Problemi da scrivere:
- Atcoder DP Contest: problemi in ordine crescente di difficoltà, da molto facili a molto difficili. (Inizia dai primi che non risolvi istantaneamente.)
- soluzioni dei problemi A,B,...,O: qui
Per problemi extra, potete fare riferimento alla prima lezione del primo stage dello scorso anno.
Problemi:
- DFS-tree
- trovare cicli e ordinamento topologico
- dp su DAG (e quindi su alberi)
- ponti e punti di articolazione (in grafi non diretti)
- algoritmi per i cammini minimi: Floyd-Warshall e Dijkstra
- (siete invitati a leggervi come funziona Bellman-Ford)
Problemi classici:
Problemi meno classici:
Implementazioni:
- Isomorfismo tra alberi
- Intuizione per il minimo albero ricoprente (MST):
- grafi planari e dualità
- caratteristica di Eulero di un albero, i.e. M=N−1
- lemma del ciclo e lemma del taglio
- Algoritmi per l'MST
- Kruskal in O(MlogM);
- Prim in O(N2) e O(MlogM);
- Borůvka in O(MlogN)
- Diametro di un albero
- Calcolare per ogni nodo, la somma delle distanze da tutti gli altri nodi: "rerooting"
Buon test per i concetti base di teoria dei grafi:
Problema carino "domanda per la lode" a cui pensare:
- Un grafo si dice 3-colorabile se è possibile assegnare a ogni suo vertice uno tra tre colori in modo tale che ogni arco connetta vertici di colori distinti. Ti è dato un grafo planare 3-colorabile e vuoi trovarne una 3-colorazione. In generale questo problema è NP-completo (i.e. molto difficile), per tua fortuna hai a tua disposizione un oracolo a cui puoi fare quante domande vuoi. Dato un qualunque grafo, l'oracolo ti dice se questo è o meno 3-colorabile. Riesci a trovare una 3-colorazione del grafo originale in tempo polinomiale?
- se sì, hai appena dimostrato che trovare una 3-colorazione è polinomialmente equivalente a decidere se ne esiste una;
- l'ipotesi di planarità non è necessaria, ma aiuta a visualizzare la soluzione e non si perde niente ad assumerla.
Problemi classici:
Problemi meno classici:
Codice:
Commento: Kruskal e Prim di solito si preferiscono a Borůvka, che ha un'implementazione un po' meno intuitiva. A lezione ho detto che la complessità di Borůvka non cambia se si implementa la DSU naive. Tuttavia, provando a implementare la DSU naive, posso garantirvi che è un'esperienza strettamente peggiore di implementare la vera DSU, che quindi è da preferire in ogni caso.
Quando risolvete i problemi non dimenticate che esistono Prim in O(N2) e Borůvka: possono tornare utili.
Problemi:
Problemi per la teoria:
Problemi per l'esercitazione:
- in sospeso dalla lezione precedente: isomorfismo tra alberi nel caso non radicato
- utilizzo furbo della Standard Library
- somme su un range: Segment Tree (e generalizzazione)
- range-query/range-update: lazy propagation
- array *tanto* grandi:
- compressione degli indici
- segment sparsi
Materiale:
Problemi:
- Range query meno classiche:
Implementazioni viste a lezione:
Problemi:
Materiale:
Problemi:
- Grafi moltiplicati
- Strutture dati su alberi
- Grafi funzionali
- Sparse table
Problemi:
Problemi:
Nota: ultimi tre stanno pure su training.
Soluzioni di index:
Non sono scritte benissimo, ma ci sono le idee. Particolarmente consigliata la soluzione con ricerca binaria parallela.
Il peso ai fini della graduatoria finale delle gare internazionali sarà di 0.5 (pari a quello della gara nazionale). I partecipanti online possono accedere al secondo stage totalizzando un punteggio minimo di 100 punti su 400.
Skill issue
Avete abbondanti problemi dalle scorse lezioni: questo è un buon momento per implementarli. Se ne volete altri non esitate a chiederne.
Altrimenti:
Avete abbondanti problemi dalle scorse lezioni: questo è un buon momento per implementarli.