# Consigli e aiuto per sommelier

**URL:** <https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955>\
**Category:** Aiuto\
**Created:** [9 Dicembre 2019, 4:59pm UTC](https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955 "2019-12-09T16:59:00Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![jeppo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/4491bb/32.png) [@jeppo](https://forum.olinfo.it/u/jeppo)\
**Post date:** [9 Dicembre 2019, 4:59pm UTC](https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955/1 "2019-12-09T16:59:00Z")

</div>

Ciao, sto cercando di risolvere sommelier ma non riesco a scendere sotto una complessità quadratica tuttavia sono convinto che si possa fare con una complessità lineare o n(log n) tramite programmazione dinamica ma non saprei come fare, qualcuno mi aiuterebbe senza darmi la soluzione ma solamente con qualche consiglio a me utile?  
Grazie in anticipo.

Questo è il problema [sommelier](https://training.olinfo.it/#/task/sommelier/statement)

---

<div class="post-metadata">

**Author:** ![jeppo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/4491bb/32.png) [@jeppo](https://forum.olinfo.it/u/jeppo)\
**Post date:** [9 Dicembre 2019, 5:38pm UTC](https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955/2 "2019-12-09T17:38:58Z")

</div>

Ho sbagliato la complessità del mio codice è esponenziale con base 2 in teoria 2^n

---

<div class="post-metadata">

**Author:** ![lorenzocazzador](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lorenzocazzador/32/548_2.png) [@lorenzocazzador](https://forum.olinfo.it/u/lorenzocazzador)\
**Post date:** [9 Dicembre 2019, 9:16pm UTC](https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955/3 "2019-12-09T21:16:20Z")

</div>

Vedo che lo hai risolto, quindi in un modo o nell’altro ci sarai arrivato 😅  
Se servono altri chiarimenti chiedi pure 🙃

---

<div class="post-metadata">

**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:** [10 Dicembre 2019, 8:01am UTC](https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955/4 "2019-12-10T08:01:08Z")

</div>

Nonostante le assunzioni per questo esercizio sono molto basse sulla piattaforma quindi non è necessario ottimizzare, la soluzione più semplice ha complessità O(N^2), ma si può risolvere anche in O(NlogN).

---

<div class="post-metadata">

**Author:** ![jeppo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/4491bb/32.png) [@jeppo](https://forum.olinfo.it/u/jeppo)\
**Post date:** [11 Dicembre 2019, 6:21pm UTC](https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955/5 "2019-12-11T18:21:19Z")

</div>

La mia domanda era se qualcuno mi aiuterebbe dandomi qualche consiglio per riuscire a scrivere la soluzione ottimale quella n log n

---

<div class="post-metadata">

**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:** [11 Dicembre 2019, 7:15pm UTC](https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955/6 "2019-12-11T19:15:39Z")

</div>

È una variazione del problema: longest increasing subsequence.

---

<div class="post-metadata">

**Author:** ![jeppo](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/4491bb/32.png) [@jeppo](https://forum.olinfo.it/u/jeppo)\
**Post date:** [11 Dicembre 2019, 7:46pm UTC](https://forum.olinfo.it/t/consigli-e-aiuto-per-sommelier/5955/7 "2019-12-11T19:46:11Z")

</div>

grazie ho provato a cercare e ho visto un po’ di cose che mi hanno aiutato a capire circa come fare, comunque è interessante come questo tipo di problema si leghi ad altri problemi di craattere algoritmico.  
grazie mille 😀