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
¶ 04/04/2025 AM
¶ Lezione ed esercitazione: stringhe e hashing (Valerio Stancanelli)
Le stelle
indicano il livello di difficoltà dei problemi.
- Concetti base stringhe (alfabeto, suffisso, prefisso, ecc.)
- Problema del matching
- Z-array e algoritmo Z
- Algoritmo di hashing di Rabin-Karp
- Hashing per multiset (Zobrist Hash)
Materiale:
Problemi:
- cses_1753 - String Matching
- cses_1732 - Finding Borders
- cses_1733 - Finding Periods
- abc367_f - Rearrange Query
- cses_2420 - Palindrome Queries
- cses_2105 - Distinct Substrings
- cses_2106 - Repeating Substring
Problemi avanzati (circa in ordine di difficoltà):
- 1984D - "a" String Problem
- 1827C - Palindrome Partition
- 105535G - Gorgeous Summation
- 906E - Reverses
¶ 04/04/2025 PM
¶ Gara 1 (14:30-19:30)
¶ 05/04/2025 AM
¶ Lezione: Hopcroft–Karp & Treap (Romeo Rizzi, Fabrizio Brioni)
- Algoritmo specializzato per matching bipartito non pesato: Hopcroft-Karp
- Teorema di Hall
- Teorema di Konig: equivalenza tra max matching e minimum vertex cover nel caso bipartito
- Treap (classici e impliciti) - CEOI 2022/5 - Abracadabra
Materiale:
Problemi:
¶ 05/04/2025 PM
¶ Editorial gara 1 + Esercitazione (Fabrizio Brioni, Cheng Zhong, Linus Lüchinger)
Problemi: