Con questo post volevo inaugurare una serie di nuovi esercizi per la piattaforma di allenamento training.olinfo.it!
Il nome della rubrica è Think about it[TAI], i problemi proposti saranno realizzati da me e @zJack1342 , e saranno pubblicati (circa ) ogni 2 settimane.
Si tratta principalmente di esercizi ritenuti interessanti che avranno una difficoltà variabile, e che copriranno i principali campi della programmazione competitiva come strutture dati e programmazione dinamica.
Al termine delle due settimane sarà pubblicato un post con un piccolo editorial riguardante quel problema. Saremo ben felici di discutere e condividere le soluzioni con tutti voi!
Il primo esercizio della rubrica è Pila Di monete. Buon divertimento
Con l’arrivo del nuovo esercizio mle apro le discussioni relative a questo esercizio.
Provo a dare un’idea del metodo risolutivo di questo esercizio. Come è facile notare si tratta di game theory e la programmazione dinamica è essenziale per risolverle il problema. Definendo dp(i) come lo score massimo che si può ottenere con le ultime i monete si nota facilmente come, per calcolare dp(i) tornano comodi dp(i-1), dp(i-2), .., dp(i-k). Infatti con i monete rimaste dp(i-1), dp(i-2), .., dp(i-k) rappresentano gli score che il mio avversario può effettuare dopo la mossa corrente. L’obiettivo è quindi prendere x monete in modo che l’avversario ottenga meno punti possibili sapendo che il mio score con i monete rimaste è uguale alla somma delle prime i monete meno lo score avversario, quindi dp(i)=sum[i]-min(dp[i-1]..dp[i-K]).
In base all’algoritmo e alla struttura dati utilizzati si ottengono complessità computazionali differenti, la soluzione richiesta ha complessità O(N) , al momento evito di dare specifiche tecniche sull’algoritmo richiesto in quanto considero più utile l’idea proposta precedentemente, ma ovviamente siamo aperti a discussioni di ogni genere.
E’ un problema molto divertente quindi penso valga la pena riportarlo in vita dopo tanto tempo
Sono riuscito a fare il secondo subtask con una soluzione in O(n*k) e il terzo subtask in O(n log n) grazie all’uso di una priority queue
Pero’ non riesco a capire quale struttura si possa usare per fare delle minimum queries in O(1*)
Ho ipotizzato l’uso di una deque, ma non riesco ad essere certo che dal fondo o dalla cima riesco a raggiungere il minimo elemento con una complessita’ accettabile
Una volta aggiunto un elemento in coda, ci saranno casi in cui lo inserirai una seconda?
Una volta aggiunto un elemento in coda, ed è ottimo rispetto ad alcuni elementi già presenti, gli elementi non ottimi rispetto a quello inserito, sono utili?
L’elemento globalmente ottimo in coda, ha una “scadenza”? Sarebbe comodo poterlo rimuovere.
) ogni 2 settimane.