I problemi assegnati in questa gara sono:
In seguito si trova una breve spiegazione delle soluzioni ai problemi proposti. Riportiamo le idee chiave con una possibile implementazione. Non ci addentriamo nei singoli subtask (com'è consigliato in gara). È un buon esercizio dimostrare la correttezza delle soluzioni proposte.
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 lampadine accese, queste si spengono in 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?
Il numero totale di punti da togliere è sempre lo stesso (cioè la somma dei . Finché non abbiamo finito, almeno un giocatore ha punteggio positivo, quindi è sempre possibile togliere punti al primo in classifica. Se è piccolo e è grande per , quindi, è conveniente togliere tutti i punti al primo. Generalizzando questa strategia si può mostrare che il costo minimo è .
(Abbozzo di) dimostrazione di correttezza.
Sia il numero di volte che togliamo un punto ai giocatori in posizione . Il costo in questo caso è . Una configurazione di mosse è valida se e solo se vale la condizione: . (Perché? Posso supporre di fare le mosse in ordine decrescente di indice?)Data una sequenza di valida, se per due indici si diminuisce per aumentare della stessa quantità, allora rimane valida. In altre parole, è sempre possibile spostare verso il basso il peso della sequenza dei . Allora, dati validi, questi si possono spostare opportunamente verso il basso per ottenere costo .
è una sequenza valida, quindi il costo ottimale sopra si può ottenere. Grazie a si mostra che non è possibile fare meglio di così.
Tengo per ogni un valore booleano che indica se è possibile ottenere il titolo . La risposta sarà il massimo al variare degli con , cioè il massimo valore di un titolo che possiamo ottenere. Come calcolo i ? In ordine: , per si ha tale che , cioè se posso ottenere un titolo precedente che al giorno vale almeno tanto quanto . La complessità di questo approccio è : sufficiente per eseguire la soluzione in al più qualche secondo.
Questa implementazione è lasciata al lettore.
L'esercizio si poteva risolvere anche in con tecniche più avanzate. L'idea è considerare ogni titolo come una retta passante per il punto con coefficiente angolare . 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 . Possiamo ridurre il problema ad al più di queste operazioni. Questo approccio non necessario per i limiti del problema.
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 . 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.