¶ Link
- Stanza unica: https://meet.google.com/toz-rdfu-mhy
Se non diversamente specificato, le mattine (AM) sono in orario 09:00 - 13:00 e i pomeriggi (PM) sono in orario 15:00 - 19:00.
¶ Programma e materiale
¶ 08/02/2025 AM
¶ Square root tricks (Valerio Stancanelli, Francesco Vercellesi)
Se vedi questo argomento per la prima volta, puoi leggere le slide e risolvere il primo blocco di problemi (spiegheremo le soluzioni).
Altrimenti, puoi provare i problemi bonus e imparare l'algoritmo di Mo online.
Se ti senti davvero forte, risolvi il "problema cucinato".
Le stelleindicano il livello di difficoltà dei problemi.
Materiale:
- Slide dell'anno scorso
- Algoritmo di Mo online
- Registrazione della lezione
Problemi:
- 1485C - Floor and Mod
- abc242_g - Range Pairing Query
- abc359_g - Sum of Tree Distance
- 1520F2 - Guess the K-th Zero (Hard Version)
- Soluzioni
Problemi bonus:
- 1967B2 - Reverse Card (Hard Version)
- abc219_g - Propagation
- abc350_g - Mediator
- 1845E - Boxes and Balls
Problema cucinato:
¶ 08/02/2025 PM
¶ Matematica (Lorenzo Ferrari, James Bamber)
- somma di serie aritmetiche e geometriche
- maggiorazioni classiche
- numero di fattori primi
- numero di divisori
- valori distinti di
- le somme parziali della serie armonica vanno come
- crivello di Eratostene in (qui lineare)
- stars and bars
- numeri di Catalan
- principio di inclusione-esclusione
- esponenziazione di matrici
Questa lezione fornisce strumenti utili ma sicuramente noti a qualcuno di voi. Chi sa già ~tutto può divertirsi con una o più tra inversione di Möbius, Lemma di Burnside e FFT.
Problemi:
L'intera sezione "Mathematics" di cses. In particolare:
- Distributing Apples
- Divisors Analysis
- Prime Multiples
- Christmas Party
- Bracket Sequences II
- Graph Paths I
- Graph Paths II
Bonus:
Codice:
¶ 09/02/2025 AM (08:30 - 13:30)
¶ Gara 1
Assistenza: Filippo Casarin, Lorenzo Ferrari.
¶ 09/02/2025 PM
¶ Editorial gara 1 ed esercitazione (James Bamber, Valerio Stancanelli)
Problemi:
- 712C - Memory and De-Evolution
- 862D - Mahmoud and Ehab and the binary string
- 780E - Underground Lab
- 1100D - Dasha and Chess
¶ 22/02/2025 AM
¶ Small to large e decomposizioni di alberi (Francesco Vercellesi, Filippo Casarin)
Consiglio a chi ha già familiarità con l'argomento di concentrarsi da subito sui problemi tratti da gare, che verrano spiegati a fine lezione.
Consiglio ai più coraggiosi di passare la mattinata a risolvere il "problema inaspettato".
Materiale:
Approfondimenti:
Problemi standard:
- CSES - Distinct Colors
- CSES - Path Queries 2
- CSES - Fixed-Length Paths 1
- CSES - Fixed-Length Paths 2
Problemi da gare (circa in ordine di difficoltà):
Problema inaspettato:
¶ 22/02/2025 PM
¶ Geometria computazionale (Francesco Vercellesi)
Consiglio a chi ha già familiarità con l'argomento di concentrarsi da subito sui problemi tratti da gare, che verrano spiegati a fine lezione.
Materiale:
Problemi standard per prendere la mano:
- La sezione di geometria su CSES, tranne Minimum Euclidean Distance.
Problemi tratti da gare (in nessun particolare ordine):
- 105112I - Isolated Island
- ABC 356G - Freestyle
- 104064F - Flatland Olympics
- APIO18 - Circle selection
¶ 23/02/2025 AM (8:30 - 13:30)
¶ Gara 2
Assistenza: Elia Soldati, Davide Bartoli
¶ 23/02/2025 PM
¶ Editorial gara 2 e connettività dinamica (Davide Bartoli, Alessandro Bortolin)
Materiale:
Problemi:
- Dynamic Connectivity CSES o Codeforces
- 500F - New Year Shopping
- Dynamic Connectivity Contest
¶ 08/03/2025 AM
¶ Flusso massimo e varianti (Fabrizio Brioni, Lorenzo Ferrari)
- problema di flusso massimo
- algoritmo di Ford-Fulkerson e Edmonds-Karp
- problema di minimo taglio, dualità e max flow min cut theorem
- max flow min cost
- max matching su grafo bipartito
- modellare problemi come flusso
Materiale:
- Edmonds-Karp (cp-algorithms)
- Maximum flow (wikipedia)
- Simulating Cost Flow
Problemi classici:
- in generale gli ultimi problemi di della sezione "Graph Algorithms" di cses
- Minimum Cost Maximum Flow
Problemi:
) ¶ 08/03/2025 PM
¶ DP Optimization (Fabrizio Brioni, Valerio Stancanelli)
- Knuth Optimization: rimuove un fattore quando lo "split" ottimale è monotono
- Square Tree DP: sembra ma in realtà è
- SOS DP: in realtà è una prefix sum -dimensionale
- Aliens' Trick: trasforma un constraint che richiede un fattore in una binary search
- Serve la convessità / concavità. Come dimostrarla?
Materiale:
- Registrazione della lezione
- Knuth Optimization
- Square Tree DP (paragrafo 7)
- SOS DP
- convolution (non l'abbiamo spiegata, ma è utile)
- Aliens' Trick
Problemi:
Problemi bonus:
¶ 09/03/2025 AM (8:30 - 13:30)
¶ Gara 3
Assistenza: Giorgio Audrito, Elia Soldati
¶ 09/03/2025 PM
¶ Editorial gara 3 ed esercitazione (James Bamber, ...)
Problemi: