Il contenuto è lo stesso di OII 2025: Selezioni Territoriali | Wiki delle Olimpiadi di Informatica.
In questo post si trova una breve spiegazione dei problemi della fase territoriale di ieri, 16 aprile 2025. Riporto le soluzioni con una possibile implementazione. Non mi addentro nei singoli subtask (com’è consigliato in gara). È un buon esercizio dimostrare la correttezza delle soluzioni proposte.
Problemi
Spegnitutto
Dei quattro, questo era il problema più facile. L’osservazione chiave, intuitiva ma non scontata, è che non è mai conveniente cambiare lo stato di una lampadina già spenta. Quindi possiamo considerare i processi di spegnimento delle componenti connesse di lampadine (cioè i gruppi grandi il più possibile di lampadine accese adiacenti) separatamente. Data una fila di K lampadine accese, queste si spengono in \lceil \frac{K}{2} \rceil mosse e, poiché ogni mossa spegne al più due lampadine, non è possibile fare meglio di così.
Domanda: supponiamo ora che ogni interruttore cambi lo stato di tre lampadine. L’osservazione non vale più (perché?). Come si può aggiustare la soluzione? Ve ne vengono in mente altre?
Abbassatutto
Il numero totale di punti da togliere è sempre lo stesso (cioè la somma dei P_i). Finché non abbiamo finito, almeno un giocatore ha punteggio positivo, quindi è sempre possibile togliere punti al primo in classifica. Se C_1 è piccolo e C_i è grande per i \neq 1, quindi, è conveniente togliere tutti i punti al primo. Generalizzando questa strategia si può mostrare che il costo minimo è \sum_{i = 1}^{N}P_i \cdot \min\{C_1, \dots, C_i\}.
(Abbozzo di) dimostrazione di correttezza.
Sia K_1, \dots, K_N il numero di volte che togliamo un punto ai giocatori in posizione 1, \dots, N. Il costo in questo caso è \sum_{i=1}^{N} K_iC_i. Una configurazione di mosse è valida se e solo se vale la condizione: (\star) \ \forall i = 1, \dots, N \ K_i + \dots + K_N \le P_i + \dots + P_N. (Perché? Posso supporre di fare le mosse in ordine decrescente di indice?)Data una sequenza di K_i valida, se per due indici i < j si diminuisce K_j per aumentare K_i della stessa quantità, allora (\star) rimane valida. In altre parole, è sempre possibile spostare verso il basso il peso della sequenza dei K_i. Allora, dati K_i validi, questi si possono spostare opportunamente verso il basso per ottenere costo \sum_{i = 1}^{N} K_i \cdot \min\{C_1, \dots, C_i\}.
K_i = P_i è una sequenza valida, quindi il costo ottimale sopra si può ottenere. Grazie a (\star) si mostra che non è possibile fare meglio di così.
Investitutto
Tengo per ogni i = 0, \dots, N - 1 un valore booleano P_i \in \{0, 1\} che indica se è possibile ottenere il titolo i. La risposta sarà il massimo V_i + G_i \cdot (N - i) al variare degli i con P_i = 1, cioè il massimo valore di un titolo che possiamo ottenere. Come calcolo i P_i? In ordine: P_0 = 1, per i > 0 si ha P_i = 1 \iff \exists j < i tale che V_j + G_j \cdot (i - j) \ge V_i, cioè se posso ottenere un titolo precedente che al giorno i vale almeno tanto quanto V_i. La complessità di questo approccio è \mathcal{O}(N^2).
Questa implementazione è lasciata al lettore.
L’esercizio si poteva risolvere anche in \mathcal{O}(N \log N) (vedi qui). L’idea è considerare ogni titolo come una retta passante per il punto (i, V_i) con coefficiente angolare G_i. La struttura dati nell’implementazione che allego qui è specializzata per operazioni del tipo (a) aggiungi una retta a un insieme inizialmente vuoto e (b) dimmi il valore minimo di una retta a un certa cordinata x.
Espanditutto
Quanti giorni al più ha un pixel bruciato? Tanti quanti la distanza da un pixel non bruciato. L’idea è rosicchiare il più possibile il bordo di ogni componente connessa. I pixel rimanenti sono necessariamente bruciati al giorno 0. Il massimo numero di giorni che ha la componente connessa è il massimo numero di giorni che hanno i pixel originari, cioè il numero di strati rosicchiati. Poiché i pixel bruciati spontaneamente sono bruciati tutti lo stesso giorno e ogni componente connessa contiene almeno un pixel di quelli bruciati spontaneamente, la risposta è il minimo massimo numero di giorni di una componente connessa.
L’implementazione è una BFS multisorgente a partire dai pixel sul bordo delle componenti connesse.
Trucchi implementativi come i vettori dx, dy per iterare sui vicini e la funzione inside(x, y) che verifica se un punto appartiene alla griglia rendono più breve il codice e i bug meno probabili. Si noti che non è necessario trovare esplicitamente le componenti connesse.
