Think About It: Nuova Rubrica

Salve a tutti!

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 :slight_smile: ) 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 :blush:

9 Mi Piace

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.

3 Mi Piace