# Fette di Strudel strategia **URL:** \ **Category:** Aiuto\ **Created:** [14 Ottobre 2017, 4:51pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820 "2017-10-14T16:51:59Z")\ **Posts on this page:** 19\ **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:** [14 Ottobre 2017, 4:51pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/1 "2017-10-14T16:51:59Z")
Ho provato a risolvere [fette di strudel](https://cms.di.unipi.it/#/task/strudel/statement) partendo dall’algoritmo più semplice (sapendo che sarebbe andato in time-out) con complessità O(n^2) usando [questo](https://pastebin.com/4jkLgvtq) 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. 😉 ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [14 Ottobre 2017, 6:22pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/2 "2017-10-14T18:22:38Z")
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. ---
**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:** [14 Ottobre 2017, 7:03pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/3 "2017-10-14T19:03:13Z")
Ho le idee piu confuse di prima hahaha > [@bortoz](#): > > 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. 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? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [14 Ottobre 2017, 7:08pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/4 "2017-10-14T19:08:40Z")
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? ---
**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:** [14 Ottobre 2017, 7:39pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/5 "2017-10-14T19:39:56Z")
A rigor di logica scelgo il -6 ed il -2 perché sono i più lontani tra loro in cui il primo è minore del secondo. ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [14 Ottobre 2017, 8:21pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/6 "2017-10-14T20:21:28Z")
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. ---
**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:** [14 Ottobre 2017, 8:29pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/7 "2017-10-14T20:29:08Z")
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? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [14 Ottobre 2017, 8:39pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/8 "2017-10-14T20:39:56Z")
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. ---
**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:** [14 Ottobre 2017, 8:59pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/9 "2017-10-14T20:59:03Z")
SI ma non capisco perchè mi serve trovare il primo elemento minore o uguale anche se questo si si potrebbe fare tramite una ricerca dicotomica. ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [14 Ottobre 2017, 9:06pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/10 "2017-10-14T21:06:25Z")
Quando trovi il suo indice fai la differenza con quello su cui lavori, ripeti per tutti gli elementi tenendoti il massimo, il tutto in O(NlogN). ---
**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:** [14 Ottobre 2017, 9:11pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/11 "2017-10-14T21:11:44Z")
Si ma perché mi serve l’indice del più piccolo tra i più grandi? Non dovrei trovare il più lontano tra i più grandi? ---
**Author:** ![rossimelthomas](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/r/d26b3c/32.png) [@rossimelthomas](https://forum.olinfo.it/u/rossimelthomas)\ **Post date:** [15 Ottobre 2017, 7:23am UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/12 "2017-10-15T07:23:15Z")
Dato un numero X in quale complessità riesci a trovare tutte le sequenze di fette di strudel lunghe X? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [15 Ottobre 2017, 7:59am UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/13 "2017-10-15T07:59:41Z")
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. ---
**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:** [15 Ottobre 2017, 10:05am UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/14 "2017-10-15T10:05:24Z")
> [@rossimelthomas](#): > > Dato un numero X in quale complessità riesci a trovare tutte le sequenze di fette di strudel lunghe X? 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. > [@bortoz](#): > > uoi provare che sotto opportune condizioni il più lontano è anche il primo numero minore o uguale? 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? 😄 ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [15 Ottobre 2017, 10:15am UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/15 "2017-10-15T10:15:06Z")
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. ---
**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:** [15 Ottobre 2017, 10:39am UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/16 "2017-10-15T10:39:42Z")
Ok credo di aver capito questo passaggio: 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? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [15 Ottobre 2017, 10:45am UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/17 "2017-10-15T10:45:14Z")
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 ---
**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:** [15 Ottobre 2017, 11:07am UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/18 "2017-10-15T11:07:25Z")
Ultima cosa, a cosa serve la ricerca dicotomica? Poi mi guardo la map perché l’ho usata poco. ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [15 Ottobre 2017, 12:15pm UTC](https://forum.olinfo.it/t/fette-di-strudel-strategia/4820/19 "2017-10-15T12:15:48Z")
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