Ciao a tutti,
sto pensando a come risolvere Talmart (solo che la mia voglia di programmare è pari a 0 e quindi mi limito a questo 
)
Si può risolvere con una dp e poi migliorarlo per entrare nei limiti di tempo o è meglio se cambio strategia?
L’approccio è greedy.
Pensa a qual è il caso più conveniente dove invertire il senso dell’ascensore.
Ma l’ascensore si inverte sempre
Si ma scegli tu quando far uscire un cliente e si conseguenza scegli tu quando farlo invertire.
Innanzitutto l’esercizio è risolvibile in O(n).
Supponiamo di avere n clienti, la risposta s a questo problema sarà un valore tra 1<=s<=n dove il risultato 1 ed n si può ottenere solo in casi particolari:
-
s=1, mi sembra abbastanza scontato che questo output sarà ottenibile solamente quando tutti i valori saranno crescenti, e quindi in qualsiasi punto venga effettuata l’inversione nessun’altro cliente potrà più uscire
-
s=n, si ottiene quando i valori all’interno dell array saranno “alternati” , quindi A_1>A_0 A_2<A_1 e così via
A[10]={5,2,10,4,100,20,22,21,30,26};
A questo punto , avendo capito che devi cercare di invertire più volte possibili per avvicinarti a s=n ,devi capire cosa fare nel caso in cui trovi 2 o più valori consecutivi crescenti/decrescenti e in quale di essi devi fermarti, anche se la soluzione è molto semplice.
Capito, grazie mille, più facile del previsto effettivamente 
1 Mi Piace
Bonus: supponiamo che possano esserci una o più persone che vogliono scendere allo stesso piano. Vale ancora una strategia greedy?
5 Mi Piace
No ma si trasforma in dp.
Potrebbe capitare che durante la salita mi convenga fermare l’ascensore ad un piano, anche se potrei salire ancora, basta pensare al caso in cui allo stesso piano scendano molte persone, al successivo solo una e il primo piano che incontro nella discesa è minore di entrambi:
Al piano 27 scendono 100 persone
Al piano 28 una
Al piano 20 una
Questo caso è abbastanza scontato ma credo che basti per affermare che non sia greedy
1 Mi Piace
Esattamente, ora come lo risolveresti rispettando il tempo limite di 1 secondo lasciando le stesse identiche assunzioni?
4 Mi Piace
Perdonatemi se sbaglio ma si potrebbe migliorare la complessità ad una dp con un albero oppure dividere in due soluzioni (in modo ricorsivo) il problema ogni volta che incontro più numeri doppi Si può anche qui migliorare la complessità con memorizzazione (dovrebbe stare nei tempi)
Chiedo venia per le mie carenze di implementazione di dp, nelle ois li svolgeva un mio compagno e per le individuali non ho potuto partecipare alla territoriale dopo aver passato la scolastica e quindi non l ho mai fatta bene la dp
Io ho scritto una soluzione DP in O(N^2) e penso che ci sarebbe da rimuovere il ciclo interno della funzione ricorsiva.
Magari con una ricerca binaria o qualche struttura dati in modo da abbassare a O(NlogN)?
2 Mi Piace
Posso vedere la soluzione? 
https://pastebin.com/yiwZkgdn
Non l’ho provata per i valori uguali, però teoricamente dovrebbe funzionare.
1 Mi Piace
Prova questo input
5 30
20 20 20 27 21
L’ho fatto mentalmente e ritorna 4 piuttosto che 5, però penso che basterebbe fare in modo che quando il valore è uguale il secondo parametro goup non venga invertito (adesso non posso provarlo)
1 Mi Piace
Comunque la risposta giusta dovrebbe essere 3.
Non riceve una mancia per ogni cliente che scende?
Scenderebbero i primi tre al ventesimo piano e poi gli altri (con risultato cinque).
1 Mi Piace
Si ma dopo è costretto a scendere e non ci sono piani sotto il 20.
Mi hai messo in difficoltà, spero di poterti rispondere domani 
1 Mi Piace
Il 30 che vedi non è il primo piano ma i piani totali, la risposta dovrebbe essere 3