Tè con gli amici

Aiuto
1

Salve a tutti, dal momento che ho visto che 9 di voi hanno già risolto questo problema, ho pensato di chiedere una mano perchè non riesco ad ottenere oltre 25/100 in questo problema. La mia prima soluzione eseguiva semplicemente i cambiamenti di posto di tutti i partecipanti e poi trovava il primo degli amici… (25/100) la mia seconda soluzione spostava solo gli amici (nel tentativo di risparmiare tempo ma il risultato è stato sempre 25/100… E’ logico pensare che eseguire tutti i “salti” non sia la soluzione ottimale (dato che le assunzioni ammettono input abbastanza grandi) perciò mi era venuto in mente che probabilmente la soluzione ottimale sarebbe quella di tentare di diminuire il più possibile il numero di T (numero di squilli) in maniera tale che abbia la stessa soluzione finale (dopo T squilli) eseguendo però soltanto X scambi con X<T. Sono sulla buona strada? come dovrei trovare X? 

2
probabilmente la soluzione ottimale sarebbe quella di tentare di diminuire il più possibile il numero di T (numero di squilli) in maniera tale che abbia la stessa soluzione finale (dopo T squilli) eseguendo però soltanto X scambi con X<T. Sono sulla buona strada?

gianpiero96

Sì, la prima osservazione da fare è che non è possibile una situazione di questo tipo:

l'ospite k si trova nel posto i ---> viene catapultato in un posto j
[succedono eventi...]
l'ospite k si trova di nuovo nel posto i ---> viene catapultato in un posto diverso da j
3

la mia soluzione consiste nel trovare dopo quanti salti ogni amico k torna al posto di partenza, e fra i numeri trovati fare in MCM= X successivamente sarebbe necessario eseguire T%X salti per raggiungere la disposizione finale, il problema è che anche questa soluzione sembra non rientrare nei limiti di tempo…  

4
la mia soluzione consiste nel trovare dopo quanti salti ogni amico k torna al posto di partenza

gianpiero96

Quello lo sai con una sola operazione, basta seguire ciò che ha detto Wil93 :)
5

prendo ogni amico Ki singolarmente  e lo sposto fino a quando non torna al posto di partenza giusto? o c’è qualcosa di più rapido che mi sfugge? 

6

Non sono sicuro di capire la necessità di fare il MCM… non va bene eseguire T%X salti usando un X diverso per ogni amico?

7

effettivamente non ci avevo badato… il MCM non serve come suggeriva Wil93… ora con la nuova soluzione sono arrivato a 45/100 sembro sforare il limite di tempo di circa 1 secondo… devo trovare qualche cosa da velocizzare… 

8

Attento che l’esecuzione di solito viene bloccata automaticamente circa un secondo dopo il tempo limite… quindi non è detto che il tuo programma sfora solo di un secondo

9

si esatto si blocca dopo 3 secondi (il limite è 2) però per molti dei casi test che non supero, la mia soluzione viene data a circa 2,90. Comunque in ogni caso la soluzione non è di certo ottimale, considerando le altre date…  

10

Prova a farti un disegno della tabella degli spostamenti, dovresti notare qualcosa!

11

Qualcosa tipo che dopo 6 squilli (nel caso di esempio) tutti tornano al posto di partenza? 

12

Non ti fissare sul “tornare al posto di partenza” guardando la totalità della tabella di spostamenti (perché, appunto, ti costringerebbe a fare il m.c.m.).

13

Si questo mi era chiaro, infatti nella mia ultima soluzione non c’è M.C.M. Ognuno dei Ki amici viene considerato singolarmente e procedo in questo modo:

1) vedo quanti X squilli sono necessari affinché Ki torni al posto di partenza
2) sposto Ki come se sentisse soltanto T%X squilli, e sono sicuro che Ki si trova nella posizione finale (quella che avrebbe se avesse seguito T squilli).

probabilmente il mio limite sta nella parte di codice del punto 1, poichè con K molto grande la ricerca di tutte le X sfora i limiti di tempo.   
14

Suppongo che tu ti metta a cercare X(i) per K(i) con un ciclo, per questo esci dai limiti.
Ripeto: disegnati la tabella di spostamenti e guardala sotto un’altra prospettiva.

Hint: grafo (o meglio, insieme di grafi).
Da lì dovresti trovare X(i) in O(1).
15

Caspita che sbadato… non avevo considerato proprio la possibilità di trattarlo come un insieme di grafi… Grazie! provo a scrivere un nuovo codice… 

16

Mi ricordo che tempo fa avevo scritto una soluzione (che non ho più) che procedeva in modo completamente diverso.

Si basava sulla costruzione di nuove tabelle di mobilità, le quali equivalgono a 2,4,8, 2^i squilli di tromba (mentre la tabella originale corrisponde a 1 solo squillo)

17

http://pastebin.com/71kBUxrn
con questo codice ottengo 20/100 come potrei migliorarlo?

18
http://pastebin.com/71kBUxrn
con questo codice ottengo 20/100 come potrei migliorarlo?

riccardomereu5

Da quello che ho capito lanci una DFS da ogni amico per contare quanto è lungo il suo ciclo (D) e poi trovi la sua posizione in O(T%D), sbaglio?
Se è così, una volta che sai D puoi trovarti la posizione dopo T squilli in O(1) se ti salvi un altro paio di cose!

In ogni caso se già hai l'idea di salvarti quanto è lungo il ciclo di ogni amico allora se sulla buona strada!
19

Se è così, una volta che sai D puoi trovarti la posizione dopo T squilli in O(1) se ti salvi un altro paio di cose!

VashTheStampede

Ad esempio? (se puoi non darmi la risposta, ma un indizio che mi porti sulla giusta strada)
20

Ad esempio se sai la lunghezza D di un ciclo, ti interesserebbe sapere pure quali nodi appartengono a quel ciclo.
Draw it! =P