Himalaya ... una vetta difficile da raggiungere

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?

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

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.

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 …

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

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, in particolare la query chiamata: Searching for the first element greater than a given amount

1 Mi Piace

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

1 Mi Piace

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 :v: :+1:grazie anche a @frakkiobello per le dritte sui segment tree