L’ approccio da usare è la programmazione dinamica.
Prova a spiegare l’ idea che hai in mente e quello che fa il codice.
Leggendolo non si capisce che fa
Mi consiglieresti di utilizzare la top down o la bottom up?
In pratica cerco di utilizzare la bottom up, almeno credo .
Le variabili u e v rappresentano la posizione nel vettore “match” della prima e dell’ultima partita partita svolta nello stesso giorno.
Ogni volta che in un giorno ci sono più di una partita la funzione “max_win” verrà chiamata.
All’interno della funzione la prima cosa che faccio è ordinare la parte del vettore “match” corrispondente alle partite del giorno in questione basandosi sulla fine di ogni match(in ordine crescente).
Successivamente creo una matrice di match[v].E+1 righe, cioè in questo modo ci saranno 0,1,2… m[v].E righe(m[v].E sarebbe la partita con l’orario di fine più grande) in modo tale da poter andare a risolvere i casi in ogni limite di tempo.Mentre l’ascissa è compost dal numero di partite+1(così per ogni riga della tabella il primo valore sarà 0).
Per ogni cella della nostra tabella andrò a vedere se “giocare o non giocare la partita in questione”, nel caso in cui io decida di giocarla devo tener conto di due cose:
(match[u+k].E<=i) = cioè se il match in questione finisce prima del limite di tempo i.
(M+m[match[u+k].S][k-1]>=match[u+k].B) se il badget è sufficiente per giocare la partita.
Se entrambe le condizioni sono vere faccio una somma tra il guadagno di questa partita e il guadagno che potrei ottenere dall’inizio della giornata fino all’inizio della partita a cui facciamo riferimento, la somma fatta la confronto con il valore della cella alla mia sinistra(che corrisponde al caso in cui decido di non giocare la partita) e prendo il valore più grande.
Se le condizioni risultano false copio il valore della cella precedente m[i][k]=m[i][k-1].
E così “dovrei” ottenere il risultato migliore della giornata che poi, sommato con i risultati delle altre giornate e con il budget iniziale, mi dovrebbe dare il risultato finale.
Mi scuso ma purtroppo non sono molto bravo a spiegare…
Considerando il caso peggiore in cui ci sono 100 000 parite in un giorno e crei una matrice 100 000 x 1 000 hai bisogno di 100 000 000 interi che trasfromati in megabyte sono circa 400.
Quindi anche se il tuo ragionamento è giusto non prenderebbe mai il 100/100 per i limiti di memoria.
Hai bisogno di rivedere la strategia risolutiva, ordinare e dividere la dp su più giorni è già un buon inizio.
Inizia col non complicarti la vita leggendo gli input cosi, puoi salvare benissimo i valori in un vettore e quando il giorno non coincide con il precedente fai partire la dp.
Ordinando per fine (come hai fatto) ti permette di creare l’ ordine con cui potresti giocare le varie partite, quindi considerando una partita in posizione i essa può essere giocata se il budget di inizio giorno te lo permette oppure esitono delle partite j con j < i precedenti da cui potresti ricavarti la somma da poter usare nella i-esima partita.
Il budget per il giorno successivo è dato dal massimo che puoi ricavare per ogni partita e il budget iniziale di giornata.
Prova a scrivere una soluzione O(N^2) dove per ogni posizione i provi a combinarla con le precedenti.
Se tutto va bene dovresti riuscire a ottenre 85/100.
Immagino che a questo punto hai intuito che struttura usare per conservare i risultati per ogni partita.
Per il 100 su 100 ci sono due ottimizzazioni che si potrebbero fare ma l’ importante ora è arrivare ad avere output corretti.
Molte grazie per il suggerimento, ero fermo da un pezzetto a 85/100 ma utilizzando le tue considerazioni sono arrivato in fondo. Tutto considerato era imparentato con la “Dieta di Poldo”.
Non ho molta esperienza con questi conti ma direi O(nlogn).
Per memorizzare il massimo che posso fare per ogni torneo e recuperare il massimo guadagno utilizzabile che precede il torneo i uso un segment tree.
Inoltre Il vettore dei tornei di una giornata viene ordinato prima della scansione.
n è il numero di tornei di una giornata.
Il tutto ripetuto per tutte le giornate.
In realtà si può migliorare.
La complessità minima è data dall’ordinamento del quale non si può fare a meno, ma se invece di ordinare tutto il vettore iniziale lo si divide in giorni si possono fare N/giorni ordinamenti e la complessità è inferiore rispetto ad un unico ordinamento.
Successivamente si può notare come ordinando i tornei in base alla loro fine possiamo fare in modo di calcolare il miglior budget per ogni singolo attimo solamente una volta.
Senza ricorrere a segment o fenwick che aggiungono un fattore logaritmico.
Pensala così, ogni torneo, stando a ciò che fai tu, aggiorna un suffisso dei possibili momenti, quindi , per esempio l’ultima cella del vettore viene aggiornata N volte, anche se ciò potrebbe essere fatto un’unica volta.
Non mi pare che il mio algoritmo funzioni così, come dicevo lavora stile “La dieta di Poldo” e non è ricorsivo.
Nell’ambito dei tornei di una giornata (ordinati crescenti per orario di fine torneo):
vado dal primo fino all’ultimo
ad ogni torneo mi guardo indietro per capire se posso farlo e se si quanto al massimo mi trovo in saccoccia dopo aver vinto quel torneo, facendo attenzione a quei tornei che terminano tutti allo stesso istante e memorizzando il totale delle vincite fin li +la posta di partenza.
Il valore memorizzato ad un certo istante viene elaborato tante volte per quanti sono i tornei che terminano in quell’istante e così anche per il valore superiore dell’ultima cella.
Ad intuito penso che usi il segment tree per controllare quale sia il maggior numero di soldi con il quale puoi iniziare ogni torneo.
Se è come penso:
Se usi un fenwick dovrebbe essere leggermente più veloce.
In questo modo per ogni torneo controlli quanto è il massimo prima del suo inizio avendo poi una complessità log(1000). Modificando leggermente l’algoritmo puoi conoscere quel valore in O(1), ma ovviamente devi cambiare l’aggiornamento che non sarà più O(1) ma O(1000) per ogni giornata:
Quindi per ogni singolo giorno, dove hai K tornei, invece di di avere O(Klog(1000) +K) puoi avere O(2K).
Si l’algoritmo lavora così.
Il suggerimento N1 mi è chiaro e ci posso provare quasi subito
Sul secondo devo meditare, tra l’altro con il calcolo della complessità ho problemi.
Un’ultima cosa:
Un update del valore del segment tree relativamente alla fine di quel torneo.
Supponendo che:
il torneo i termini al momento y
che potendolo fare mi trovi in tasca z
che questo z sia maggiore w cioè di quanto mi farebbe incassare un altro torneo già analizzato e che terminava sempre all’istante y (sempre che ce ne sia uno prima)
allora vado a mettere z nel segment tree in posizione y.
Scusa ripensandoci non vedo cosa mettere dentro Fenwick a meno di ripensare il tutto.
