# Himalaya ... una vetta difficile da raggiungere

**URL:** <https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704>\
**Category:** Aiuto\
**Created:** [5 Settembre 2021, 8:28am UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704 "2021-09-05T08:28:43Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![micsal](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/e274bd/32.png) [@micsal](https://forum.olinfo.it/u/micsal)\
**Post date:** [5 Settembre 2021, 8:28am UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704/1 "2021-09-05T08:28:43Z")

</div>

Buon giorno, sono bloccato al **subtask 4** della traccia **Himalaya** , subtask del quale riesco a risolvere solamente il test **case 14** e **19** , tutti gli altri vanno in _ **Execution timed out** _,  
qualcuno si ritrova un test case dal **15** al **18** o dal **20** al **23**?

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [6 Settembre 2021, 5:56pm UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704/2 "2021-09-06T17:56:22Z")

</div>

Ho quei file ma sono molto grossi come te li invio?  
comunque per i time out suggerirei di partire dal fondo.

---

<div class="post-metadata">

**Author:** ![micsal](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/e274bd/32.png) [@micsal](https://forum.olinfo.it/u/micsal)\
**Post date:** [7 Settembre 2021, 5:25am UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704/4 "2021-09-07T05:25:40Z")

</div>

Purtroppo parto **già dal fondo** ma non riesco ad **ottimizzare** la ricerca. Tranne in **alcuni casi particolari** nei quali il bob **non parte** o il **valore d’arresto è uguale al precedente,** in tutti gli altri casi vado a rieseguire i calcoli fino a un valore di **energia negativo** o la **fine delle vette** , pensandoci bene, non penso il problema sia dovuto alla mancata considerazione di alcuni casi particolari ma semplicemente il **numero di passaggi troppo elevato** , proverò a ragionarci su grazie ugualmente.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [7 Settembre 2021, 8:00am UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704/5 "2021-09-07T08:00:31Z")

</div>

L’ho risolto qualche tempo fa però qualche idea potrebbe essere:

1. trascurare la Massa, moltiplicare per 20 le altezze e lavorare direttamente col quadrato della velocità

2. tenere una lista delle sole altezze che interessano per capire dove si arriva a partire da una cima:  
con i dati del secondo esempio 3 2 1 5 3 3 8 2 1 e partendo dal fondo la lista contiene:  
1 poi solo il 2 poi solo l’8 poi 3,8 poi 3,8 poi 5,8 poi 1,5,8 poi 2,5,8  
Ovviamente devi anche memorizzare le posizioni di quei valori.  
Nota che la lista è sempre ordinata …

---

<div class="post-metadata">

**Author:** ![micsal](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/e274bd/32.png) [@micsal](https://forum.olinfo.it/u/micsal)\
**Post date:** [7 Settembre 2021, 2:53pm UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704/6 "2021-09-07T14:53:37Z")

</div>

Ok, grazie Vittorio, il primo punto era facile per il secondo mi sto organizzando, grazie per le dritte

---

<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:** [9 Settembre 2021, 12:36pm UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704/7 "2021-09-09T12:36:27Z")

</div>

Propongo una soluzione alternativa, anche se leggermente più lenta.

Anche io per comodità parto moltiplicando l’altezza delle varie vette per 10M, in questo modo passare dalla vetta H\_i alla vetta H\_{i+1} incrementa la velocità attuale di H\_{i+1} - H\_i ,mentre la velocità iniziale rimane sempre uguale a \frac{1}{2}MV^2.

Calcoliamo ora p\_i come la quantità di velocità che accumulerei partendo dalla vetta 0 ed arrivando alla vetta i: p\_0 = 0, p\_i = p\_{i - 1} + H\_{i - 1} - H\_i \forall \le i \le N - 1.  
Per trovare, per ogni vetta, a quale delle vette successive ci fermeremo effettuiamo il seguente ragionamento: sappiamo che partendo dalla vetta H\_i ci fermeremo quando la velocità sarà diminuita di V che equivale a dire che ci fermeremo alla prima vetta H\_j con j \> i tale per cui p\_j - p\_i \< -V, sottraendo p\_i da entrambi i lati otteniamo p\_j \le -V + p\_i.  
Quindi per ogni vetta i dobbiamo trovare min j | j \> i, p\_j \le -V+p\_i (in caso tale j non esistesse significa che partendo dalla vetta i è possibile visitare tutte le vette successive) è possibile effettuare tale operazione con complessità temporale logaritmica rispetto al numero di vette utilizzando un segment tree, ottenendo una complessità finale pari a O(NlogN).  
In caso non foste in grado di capire come implementare un segment tree in grado di eseguire tale operazione (consiglio di provare a pensarci in quanto non è complicato) oppure per maggiori dettagli consultare la seguente [voce](https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-8), in particolare la query chiamata: **Searching for the first element greater than a given amount**

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [9 Settembre 2021, 4:21pm UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704/8 "2021-09-09T16:21:33Z")

</div>

Guardando meglio il vecchio codice ho moltiplicato le altezze per 20 ed ho corretto il punto 1

---

<div class="post-metadata">

**Author:** ![micsal](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/e274bd/32.png) [@micsal](https://forum.olinfo.it/u/micsal)\
**Post date:** [9 Settembre 2021, 6:19pm UTC](https://forum.olinfo.it/t/himalaya-una-vetta-difficile-da-raggiungere/6704/9 "2021-09-09T18:19:21Z")

</div>

Si, non ti preoccupare, avevo capito che avevi omesso una moltiplicazione scontata e quindi in realtà occorreva moltiplicare per 20, grazie al tuo consiglio, ieri sono stato in grado di ultimare l’esercitazione ✌ 👍grazie anche a @frakkiobello per le dritte sui segment tree
