# Think About It: Nuova Rubrica **URL:** \ **Category:** Algoritmi\ **Created:** [7 Ottobre 2019, 7:22pm UTC](https://forum.olinfo.it/t/think-about-it-nuova-rubrica/5850 "2019-10-07T19:22:49Z")\ **Posts on this page:** 4\ **Page:** 1
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [7 Ottobre 2019, 7:22pm UTC](https://forum.olinfo.it/t/think-about-it-nuova-rubrica/5850/1 "2019-10-07T19:22:49Z")
Salve a tutti! Con questo post volevo inaugurare una serie di nuovi esercizi per la piattaforma di allenamento [training.olinfo.it](http://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](https://training.olinfo.it/#/task/tai_monete/statement). Buon divertimento 😊 ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [23 Ottobre 2019, 8:50pm UTC](https://forum.olinfo.it/t/think-about-it-nuova-rubrica/5850/2 "2019-10-23T20:50:46Z")
Con l’arrivo del nuovo esercizio [mle](https://forum.olinfo.it/t/think-about-it-mle/5853) 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. ---
**Author:** ![iRom](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/i/9fc29f/32.png) [@iRom](https://forum.olinfo.it/u/iRom)\ **Post date:** [17 Giugno 2022, 9:54pm UTC](https://forum.olinfo.it/t/think-about-it-nuova-rubrica/5850/3 "2022-06-17T21:54:12Z")
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 ---
**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\ **Post date:** [18 Giugno 2022, 9:53am UTC](https://forum.olinfo.it/t/think-about-it-nuova-rubrica/5850/4 "2022-06-18T09:53:11Z")
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. [Minq](https://cp-algorithms.com/data_structures/stack_queue_modification.html#queue-modification-method-3)