Ho provato a risolvere il problema pizzeria in dp con memoizzazione, ma l’ultimo subtask va sempre fuori tempo.
Ho scritto diverse soluzioni, questa mi sembra la più decente:
La funzione da implementare è “contentezza”. La funzione “mangia” restituisce il valore massimo tra quelli ottenibili mangiando la prima o l’ultima fetta.
Domanda bonus: nei problemi con grader mi conviene “globalizzare” una variabile data nella funzione da implementare come ho fatto in questo caso? (Ho notato che i tempi sono ancora più lunghi se passo l’intero vettore nella funzione “mangia”).
Prova con una strategia differente, pensala così:
Hai N=4 e 8 13 2 4 come valori;
Se la sequenza fosse composta solo dal valore i=0,1,2,3 quindi: o 8 o 13 o 2 o 4 è facile intuire quale sia la somma massima , passa invece al caso in cui la sequenza sia composta da 2 valori, anche qui è facile sapere quanto è il massimo che posso ottenere e quanto otterrà l’avversario, per esempio in 8 13 il primo giocatore totalizza 13 e il secondo 8 mentre con 13 2 il primo totalizza 13 ed il secondo 2.
Ora per sapere facilmente quanto è il massimo ottenibile con la sequenza 8 13 2 non è difficile , si può utilizzare lo stesso ragionamento per tutta le sequenza.
Anche io ci sto ragionando su questo problema e avevo pensato a una top down in cui gestivo la tabella usando gli indici i pezzi di pizza che posso scegliere.
Usare una memo di vettori non è esagerato?
è la prima volta che provo a risolvere i problemi di game theory, quindi non saprei.
Comunque avevo usato una matrice perché la mia idea era memorizzare (o forse si dice memoizzare) il numero massimo di contentezza raggiungibile considerando V dalla posizione “a” fino a “b”
Sì, praticamente sì, in questo modo valuti la strategia migliore per entrambi i giocatori, ovviamente calcolati sia quanto può ottenere al massimo il G1 in un determinato momento ma anche il G2, visto che la mossa successiva i valori si invertiranno.
Ho ripensato al tuo algoritmo e notando che hai usato il push_back mi è venuto in mente che quella funzione impiega complessita lineare a seconda della size del vector (almeno secondo c++ reference).
Cosi ho modificato l algoritmo utilizzando direttamente matrici e vettore dichiarati in globale.
Per evitare di scrivere 2 for per inizializzare la memo esiste la funzione memset con cui puoi impostare il valore.
Anche la funzione massimo si può evitare di scrivere utilizzando direttamente max.
Nella funzione mangia potresti anche evitare l if ( a > b ) return 0 visto che nel if precedente controlli se sono uguali, i due indici assumeranno sempre lo stesso valore.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 5000
int pizza[MAXN];
int memo[MAXN][MAXN];
int mangia(int a, int b, int somma) {
if (a==b) return pizza[a];
if (memo[a][b]==-1) memo[a][b]=max(somma-mangia(a+1, b, somma-pizza[a]), somma-mangia(a, b-1, somma-pizza[b]));
return memo[a][b];
}
int contentezza (int N, int V[]) {
int sum=0;
for (int i=0; i<N; i++) {
pizza[i] = V[i];
sum+=V[i];
}
memset(memo,-1,sizeof(memo));
return mangia(0, N-1, sum);
}
@madeve Mi puoi spiegare perché come valore fai restiture la somma massima meno quel pezzo di pizza ? Io avevo fatto un algoritmo molto simile ma restituendo solo quel pezzo di pizza (ed infatti non funzionava xd ) .
In sostanza, se prendi un pezzo di pizza sai che l’altro giocatore farà la mossa ottimale sulla parte restante del vettore, quindi tu riuscirai a mangiare soltanto quello che resta (cioè le somma di tutti i pezzi - quelli presi dalla mossa ottimale dell’avversario)
Comunque grazie mille, non pensavo che push_back impiegasse così tanto tempo
Allora, non è vero che push_back ha complessità lineare, la vera complessità è ammortizzato costante (come appunto è scritto sul tuo link). Il motivo di tale complessità è dato dal fatto che un std::vector alloca più spazio di quanto effettivamente ne usa. Se durante la riallocazione, alloco il doppio dello spazio attualmente utilizzato, il numero di riallocazioni sarà \log_2 n e il numero di elementi spostati sarà al più 2n. Se vuoi approfondire puoi guardare qua.
Comunque se si vuole evitare la riallocazione si possono usare le funzioni resize e reserve che allocano lo spazio in una sola volta con la differenza che la prima funzione modifica la dimensione del std::vector mentre la seconda si limita ad allocare la memoria senza modificare la dimensione.
Utilizzando queste due funzioni puoi notare che usare o non usare push_back non modifica sensibilmente i tempi di esecuzione. Il motivo principale per cui il tuo programma dà TLE è il fatto che usi una matrice dinamica che, a differenza di quelle statiche, non alloca gli elementi in modo contiguo e quindi necessità di n distinte allocazioni. Normalmente questa differenza di prestazioni non dovrebbe influire sul punteggio, tuttavia in questo task abbiamo dimensioni piuttosto grandi, ovvero 5000\times 5000=2.5\cdot 10^7, che richiedono un pizzico di ottimizzazioni.
Grazie della correzione, avevo dato una rapida occhiata alla guida e avevo capito cosi.
Non sono molto ferrato con i calcoli di tempi ecc…
Non mi è mai capitato di dover usare resize o reserve xD
Grazie del chiarimento, la prossima volta starò più attento prima di usare le matrici dinamiche
P.S. a proposito, in generale se ho un grafo in un problema con grader devo trasformare l’elenco di archi in una lista di adiacenza? Perché mi sembra uno spreco di memoria/tempo(?) e non capisco se c’è un altro modo.
