Ho provato a risolvere fette di strudel partendo dall’algoritmo più semplice (sapendo che sarebbe andato in time-out) con complessità O(n^2) usando questo codice.
Sostanzialmente dopo aver inserito nell’array diff[] la differenza tra cannella e mandorle, successivamente provo a partire da ogni sezione vedo quante posso mangiarne partendo da quella.
Dopo questo algoritmo ho pensato che avrei potuto usare un array di somme prefisse e cercare tramite la ricerca dicotomica il valore massimo con il quale la differenza tra due indici risulti positiva(quindi la determinata sezione di array i,j dove la somma dei valori compresi tra diff[i] e diff[j] risulta positiva), accorgendomi che però non è detto che se non posso mangiare k sezione contigue dello strudel io non ne possa mangiare un numero maggiore di k
Quindi stavo pensando quale algoritmo utilizzare e in che modo posso sfruttare le somme prefisse.
Ciao,
questo problema si può fare facilmente in O(NlogN).
Supponiamo di lavorare con l’elemento V[i], dobbiamo trovare l’elemento V[j] tale che V[j] <= V[i] con j più piccolo possibile.
Utilizzando la ricerca binaria si può farlo in O(logN), tuttavia bisogna capire come trovare l’elemento con indice più piccolo possibile. Il problema diventa più semplice se non considero tutti gli elementi precedenti a V[i] ma solo alcuni, resta da capire quali.
Per l’implementazione io ho usato tranquillamente una map con chiave la somma e valore il suo indice.
con V intendi l’array dove ho le differenza presumo, ma non dovrei tenere conto anche di V[i+1]V[i+2]V[j-2]V[j-1] cioè i valori interni? o ti stai gia referendo alle somme prefisse?
Mi riferisco alle somme prefisse, nel secondo caso di esempio abbiamo una cosa di questo tipo: 0, -6, -5, -7, -4, -2, -7
Come ti comporti in questo caso?
Esattamente, adesso supponiamo di lavorare sul -2, se prendiamo l’intervallo precedente e lo ordiniamo otteniamo: -7,-6,-5,-4,0
Puoi notare che la ricerca binaria è totalmente inutile, però se troviamo un criterio con cui eliminare alcuni di questi elementi, la ricerca binaria darà un risultato corretto.
Non capisco quale valore dovrei trovare con la ricerca binaria.
Perchè se non conosco la posizione di quegli elementi ordinati non me ne faccio molto, nel senso una volta ordinate le somme prefisse a me non interessano che la differenza tra i valori sia maggiore ma che la differenza tra gli indici sia maggiore no?
Il problema è trovare l’elemento minore o uguale con l’indice più piccolo possibile, adesso questo problema non è risolvibile con una ricerca binaria. Se però riusciamo a trasformare il problema nel trovare il primo elemento minore o uguale all’elemento preso in considerazione, allora questo problema è risolvibile con una ricerca binaria. Ovviamente la ricerca non deve restituire il valore ma bensì l’indice del valore ma a questo ci pensiamo dopo.
Puoi provare che sotto opportune condizioni il più lontano è anche il primo numero minore o uguale?
In particolare considero gli elementi su cui devo effettuare la ricerca binaria, se devo aggiungere un numero j ma ho già aggiunto un numero i minore, non ha senso aggiungere anche j poiché i ha indice minore. Quindi bisogna crearsi un insieme di elementi tale che la ricerca binaria del numero minore o uguale dia come risultato il numero più lontano.
Tramite le somme prefisse lo posso fare in complessità lineare, basta che provo a fare la differenza tra ogni valori V[i]-V[i-x] fino ad N.
0, -6, -5, -7, -4, -2, -7
Riferendomi al -6 il -5 è il più piccolo tra i più grandi ma non è il più lontano quindi credo che mi stia sfuggendo qualcosa?
Probabilmente ho fatto confusione con maggiore e minore, comunque per ottenere una somma devi fare V[i]-V[j] quindi V[j] deve essere minore o uguale a V[i] per ottenere una somma non negativa. Quindi sempre nel secondo esempio, una volta che ho scelto il -6, è inutile scegliere il -5 poiché qualsiasi somma che risulti non negativa con il -5, lo sarà anche con il -6 e dato che quest’ultimo ha indice minore dovrò scegliere quello. Quindi una volta che hai capito quali scegliere e quali ignorare puoi utilizzare la ricerca binaria per ricavare il suo indice.
Scorrendo l’array è inutile collocare tra le possibili sezioni di partenza dei valori la cui somma prefissa è maggiore di un numero a lui precedente giusto?
Esattamente, adesso l’implementazione più semplice fa uso di una std::map, con chiave la somma e valore il suo indice, per tenere i possibili punti di partenza
Quello che dobbiamo fare è trovare il primo elemento minore o uguale all’elemento su cui lavoriamo che sotto queste condizioni sarà anche l’elemento con indice minore.
Prendiamo ancora il secondo caso d’esempio: 0, -6, -5, -7, -4, -2, -7
Partiamo con l’inserire (0,0); poi inseriamo (-6,1) poiché -6 < 0; -5 > -6 quindi lo saltiamo, inseriamo (-7,3) e proseguiamo fino alla fine.
Quando passiamo sul -2 dobbiamo fare la ricerca binaria sui valori (supponiamo in ordine decrescente): 0, -6, -7
Il primo valore minore o uguale a -2 è -6 e il suo indice è 1 quindi la lunghezza dello strudel sarà 5 - 1 = 4
