Ciao a tutti,
Si potrebbe avere qualche testcase per il problema pozzo?
Grazie mille 
1 Mi Piace
Io più che ai testcase sarei interessato ad una dritta… è da Maggio che lo provo °L°
Nessuno risponde? :0
Vediamo se vi è d’aiuto:
Consideriamo un gallo x, e dividiamo i rimanenti in: galli con braccia più corte e galli con braccia più lunghe del gallo x.
I galli dalle braccia lunghe formano una torre, in cima alla quale sale il gallo x. Supponiamo che, in questo modo, egli non sia in grado di uscire. Cosa si può concludere?
1 Mi Piace
Vediamo se vi è d'aiuto:Innanzitutto grazie per aver risposto! :PConsideriamo un gallo x, e dividiamo i rimanenti in: galli con braccia più corte e galli con braccia più lunghe del gallo x.I galli dalle braccia lunghe formano una torre, in cima alla quale sale il gallo x. Supponiamo che, in questo modo, egli non sia in grado di uscire. Cosa si può concludere?fram
Ci ho pensato tutta ieri sera ma l'unica conclusione è: se X non può uscire allora nessuno prima di X potrà mai uscire.
Il problema è quindi scegliere opportunamente X, ma qui non arrivo a nulla..
Nel senso che ho sempre in testa il fatto di scegliere il più basso tra quelli che possono uscire così da rendere "meno influente" la sua uscita sulla torre generale (non so se mi spiego).
Ma basta poco per smentire questo metodo :\
se X non può uscire allora nessuno prima di X potrà mai uscire.Cosa intendi con "prima di X"? I galli con le braccia corte?VashTheStampede
In tal caso non è vero che nessuno di loro potrà mai uscire dal pozzo, perché se per esempio tutti i galli formassero una torre, magari anche un gallo dalle braccia cortissime potrebbe farcela.
Invece la torre che dicevo io è composta solo dai galli con braccia più lunghe di quelle di X.
L'unica cosa che mi viene in mente è che se X non riesce ad uscire, allora gli conviene lasciare il suo posto a qualcun altro della pila, che avrà delle braccia più lunghe che gli permetteranno di uscire.se X non può uscire allora nessuno prima di X potrà mai uscire.Cosa intendi con "prima di X"? I galli con le braccia corte?VashTheStampede
In tal caso non è vero che nessuno di loro potrà mai uscire dal pozzo, perché se per esempio tutti i galli formassero una torre, magari anche un gallo dalle braccia cortissime potrebbe farcela.Invece la torre che dicevo io è composta solo dai galli con braccia più lunghe di quelle di X.fram
L'unica cosa che mi viene in mente è che se X non riesce ad uscire, allora gli conviene lasciare il suo posto a qualcun altro della pila, che avrà delle braccia più lunghe che gli permetteranno di uscire.E se ha braccia più lunghe ma è più basso? Io stavo pensando che forse quell'ordinamento va fatto in base alla lunghezza totale data dalla somma dell'altezza con la lunghezza delle braccia. Così se X non riesce ad uscire arrampicandosi sui più lunghi vuol dire che almeno uno tra quelli meno lunghi di X non riesce ad uscire in senso assoluto. Quindi forse posso iterare da quello più lungo a quello più corto, in modo che: se X non riesce ad uscire, prendo il più alto tra quelli non più lunghi di X e decido che non uscirà mai. Sottraggo la sua altezza alla profondità del pozzo. Se X non riesce ancora ad uscire ripeto quello che ho fatto prima. Se ora X riesce ad uscire passo al secondo più lungo dopo X che non ho già scartato e ripeto. Quando arrivo all'ultimo la situazione sarà che quelli rimasti saranno in grado di uscire arrampicandosi ognuno sulle spalle dei più lunghi, dal più corto al più lungo, fino all'ultimo che esce da solo.mark03
Può funzionare? Non la so implementare.
Così se X non riesce ad uscire arrampicandosi sui più lunghi vuol dire che almeno uno tra quelli meno lunghi di X non riesce ad uscire in senso assoluto.Su questa parte non sono convinto, può essere che tutti quelli più corti di X riescano ad uscire.
Per il resto ammetto che mi convince e non poco!
L'unico appunto che vorrei fare è che non è detto che far uscire il primo che ci riesce sia vantaggioso.. magari è più vantaggioso sfruttare la sua altezza e farne uscire altri due (o più) e quindi migliorare la soluzione.
L'unico appunto che vorrei fare è che non è detto che far uscire il primo che ci riesce sia vantaggioso.. magari è più vantaggioso sfruttare la sua altezza e farne uscire altri due (o più) e quindi migliorare la soluzione.
Per l'implementazione non mi sembra complicato =0
@fram si hai ragione sono un'idiota mi sono perso in una banalità hahaha
Hai ragione, tra quelli meno lunghi di X va incluso anche X. Quindi se X non riesce ad uscire arrampicandosi sui più lunghi, allora tra quelli non più lunghi di X c’è uno che sicuramente non riesce ad uscire in senso assoluto. Tanto vale scartare quello più alto, che per lo meno abbasserà la profondità del pozzo.
Per il resto: non volevo fare uscire il primo che ci riesce.
Quindi se X non riesce ad uscire arrampicandosi sui più lunghi, allora tra quelli non più lunghi di X c'è uno che sicuramente non riesce ad uscire in senso assoluto.Come fai a dire che sicuramente uno non potrà uscire tra i più bassi di X? Metti caso che tutti i più bassi di X abbiano le braccia lunghissime e riescano ad uscire... (poi non capisco cosa vuol dire che tra i meno lunghi di X debba essere anche incluso X)Luke
Infatti la lunghezza l’ho definita come somma tra braccia e altezza. E facciamo pure che X va incluso tra i meno lunghi di X.
Lui dice che l’insieme C dei galli più corti di X è l’insieme di tutti i galli per cui H(i)+L(i) <= H(X)+L(X) quindi anche X fa parte dei suoi “sottoposti” (da quello che ho capito).
Comunque mi sono perso qualcosa: la tua idea non è quella di prendere il più lungo (H+L) e cercare di farlo uscire ad ogni costo “obbligando” alcuni tra i galli più corti (H+L) a rimanere nel pozzo (e li prendi dal più alto in poi)?
EDIT: preceduto! 
L’idea di considerare somma H+L è vincente!
Quello che dicevo io sulla lunghezza delle sole braccia in realtà non portava a niente
1 Mi Piace
Era leggermente diversa. (Mi riferisco a Vash)
1) Se X non riesce ad uscire allora prendo il più alto (non il più lungo!) tra quelli non più lunghi di X, e lo scarto a priori (decido che non uscirà mai).
2a) Ora se il più alto tra i non più lunghi di X era proprio X, allora scarto X e passo al gallo successivo ad X in ordine di lunghezza (quindi quello subito meno lungo).
2b) Se invece quello più alto non era X, allora se X ora riesce ad uscire, passo comunque al successivo (per lunghezza). Se invece X non riesce ancora ad uscire mi trovo nella stessa situazione di partenza e riprocedo con 1). Questo non vuol dire che voglio fare uscire X a tutti i costi. Infatti se X viene ad essere il più alto lo scarto comunque.
Sisisi intendevo il caso in cui X non sia il più alto tra quelli da sacrificare!
Ora bisognerebbe vedere se questo approccio porta sempre alla soluzione ottima °L°
Odio i problemi Greedy, quasi mai ci capisco qualcosa <_<
Prova, io non sono capace nemmeno ad ordinare un array in modo da avere gli indici anzichè le lunghezze.
Però ripercorrendola dall’inizio mi sembra sensata. Se il più lungo non riesce ad uscire conviene per certo scartare quello più alto. Come potresti far di meglio? Hai la certezza che uno non potrà mai uscire comunque, e hai pure la certezza che quello più alto è quello che può aiutare meglio gli altri ad uscire. Quindi facendo uscire quello più alto non hai nulla da perdere.
Ora se la stessa situazione si verifica per un X qualsiasi, cioè che X non riesce ad uscire, vuol dire che almeno uno tra i rimasti non può uscire. Non ha senso scartare quelli più lunghi di X, visto che verranno usati in ogni caso per arrampicarsi, quindi ha senso scartare solo quelli non più lunghi di X. E quindi di nuovo: quello più alto.
In tutto questo non ne sono affatto convinto, ma se qualcuno che la sa implementare la prova possiamo vedere se è vero!
In tutto questo non ne sono affatto convinto, ma se qualcuno che la sa implementare la prova possiamo vedere se è vero!
Io la penso come te ma di dimostrarlo formalmente non ne sono in grado…
Per implementarlaaaa… boh!
Per ogni gallo dobbiamo vedere tutti quelli più corti (compreso lui) e cercare il più alto (e questo procedimento viene ripetuto tante volte finché X esce oppure viene scelto come gallo da non far uscire) e mi sembra quadratica…
Con un RangeTree però si può scendere a NlogN
Mi sono accorto che non funziona, va sistemata.
Era leggermente diversa. (Mi riferisco a Vash)E se il gallo X riesce a uscire, lo includo nella soluzione ottima?
1) Se X non riesce ad uscire allora prendo il più alto (non il più lungo!) tra quelli non più lunghi di X, e lo scarto a priori (decido che non uscirà mai).
2a) Ora se il più alto tra i non più lunghi di X era proprio X, allora scarto X e passo al gallo successivo ad X in ordine di lunghezza (quindi quello subito meno lungo).
2b) Se invece quello più alto non era X, allora se X ora riesce ad uscire, passo comunque al successivo (per lunghezza). Se invece X non riesce ancora ad uscire mi trovo nella stessa situazione di partenza e riprocedo con 1). Questo non vuol dire che voglio fare uscire X a tutti i costi. Infatti se X viene ad essere il più alto lo scarto comunque.Luke
Cioè, vediamo se ho capito:
- Itero sui galli in ordine decrescente di lunghezza totale (H + L). Alla i-esima iterazione considero il gallo ai:
- Se la lunghezza di ai sommata alla somma delle lunghezze di tutti i galli più lunghi è maggiore o uguale della profondità del pozzo, aumento la soluzione di 1 (cioè includo quel gallo nella soluzione ottima).
- Altrimenti, se non riesce a uscire, considero il gallo bi di altezza massima tra quelli con lunghezza minore o uguale di ai. Rimuovo bi dall'array e decremento la profondità del pozzo della sua altezza.
- Se bi coincide con ai, passo al gallo successivo (in ordine di lunghezza).
- Altrimenti, vedo se ai è ora in grado di uscire: se è così, lo inserisco nella soluzione ottima e passo al gallo successivo; in caso contrario procedo come prima, finché non riesce a uscire o esaurisco i galli.
- Alla fine, i galli che riescono a uscire saranno tutti quelli che non sono stati scartati.
Così pare funzionare, per la dimostrazione:
- Tutti i galli non scartati riescono sicuramente a uscire, in ordine contrario a come sono stati considerati.
- Il numero di galli scartati è anche il minimo: infatti, ogni volta che il gallo ai non riesce a uscire (localmente), sicuramente un gallo di lunghezza minore non riuscirà a uscire globalmente. Il gallo ottimo da scartare (cioè quello che minimizza gli scarti successivi) è sicuramente quello di altezza massima, visto che una scelta differente non farebbe che peggiorare le cose.