Sto provando a risolvere https://cms.di.unipi.it/#/task/abc_studioamico/statement ma non capisco come velocizzare l’algoritmo, io sono partito da un codice molto base quasi scontato : https://pastebin.com/DXg5K36s anche se ero gia sicuro non funzionasse, in quanto la complessita risulta NLogN*2+NLogN che come worstcase quindi N=10000000 dovrebbe fare: 10000000*26*2+10000000 che va fuori tempo e anche di un po .
Piu che altro non capisco se il mio errore è di ragionamento o non uso una struttura abbastanza efficiente(ho provato anche con le upper_bound() del multiset ma il risultato peggiora), solo che non capisco come posso velocizzare il ragionamento, io li devo controllare tutti a prescindere o mi perdo qualcosa?
L’idea di base è giusta, devi solo trovare un modo più efficiente di ordinare gli array, sapendo che i valori possibili sono in un range molto ristretto. Invece di ordinare l’array, conta il numero di elementi per ogni valore e ricostruisci l’array in O(N). Se non la conosci già, questa è una Counting sort, e ti permette di portare la complessità finale a O(3 * N) = O(N).
[spoiler]Mah, sai, le ho inventate quasi tutte io, non a caso mi chiamo Dario Dijkstra Kosaraju Kruskal Tarjan Turing.
… ci sei cascato?
[/spoiler]
Scherzi a parte, molte di queste cose le devi sapere quando risolvi vari problemi, anche solo facendo quelli qui sul cms servono tante tecniche diverse. Di solito quando non riesci a risolvere qualcosa o in quel momento sei più stupido del solito (capita più del dovuto ) o è richiesto qualcosa che non conosci, e allora quando chiedi come risolverlo o cerchi indizi vari finisci per impararlo. Poi ci sono gli stage a Volterra, o impari o non passi
p.s. Lo spoiler sopra era per nascondere la stupidità dei miei scherzi
p.p.s. Si, ho usato uno spoiler per nascondere la spiegazione dello spoiler
Ma non sono a iscrizione libera, bisogna prendere la medaglia alle olimpiadi individuali giusto?
Ma scusate ordinare gli array in questo modo non è sempre vantaggioso rispetto al quicksort(), cioè se i valori che può contenere hanno un intervallo maggiore non cambia solo la memoria utilizzata, l’efficienza dovrebbe rimanere n invece che logn
Come fai a mettere uno spoiler ahhahaha[quote=“lukecavabarrett, post:9, topic:4660”]
dario rabin karp fulkerson warshall bellman landis ukkonen velskii fortune ford kirkpatrick mo adelson floyd
[/quote]
So a chi chiedere quando non so fare qualcosa hahahahahah
Avete mai vinto qualche gara voi?Quest’anno sono arrivato 6 alla nazionali delle olimpiadi a squadre(poteva andare molto meglioooo ) mentre a quelle individuali l’anno scorso ho passato loa fase scolastica ma sono uscito alle territoriali perche non avevamo fatto praticamente nulla di programmazione mentre quest anno ho passato la fase scolastica ma non ho partecipato alle territoriali perché in stage all’estero(ho provato a fare gli esercizi su cms è ho fatto 30/50 con cut off a 26 mi sembra ).
Per essere PO - e quindi partecipare agli stage di Volterra - occorre prendere una medaglia d’oro o d’argento ai Nazionali. In quanto a gare vinte ho fatto fullscore a GATOR e ABC, ma non contano , le cose di cui sono veramente fiero è l’essermi piazzato tre volte intorno al decimo posto alle COCI, e, dopo un estenuante stagione di stage a Volterra, essere risultato in seconda posizione attenendosi alla media armonica usata per selezionare la squadra IOI, e quindi molto orgoglioso di essermi qualficato
P.S: Se prendi un medaglia ai Nazionali, non puoi più fare le OIS
le COCI sono la versione aperta al pubblico delle gare nazionali croate, a cui partecipa gente da tutto il mondo, è ad un livello abbastanza alto. puoi trovare le versione passate su hsin.hr/coci
gli stage sono quattro, durano 5 giorni l’uno, e sono spiattellati lungo un intero anno
Aprofitto della discussione aperta per chiedere un consiglio su quale struttura utilizzare nel caso in cui voglio che la struttura sia ordinata ma composta da 2 valori per ogni cella, mi spiego meglio:per esempio in pacchetti corrotti io pensavo di salvare in un set i vari numero primi che ho riscontrato fino a questo momento ma voglio che ad ogni numero primo sia associato il numero in cui lo trovato la prima volta:
Con questo input :
6 10
10 7 4 9 5 6
mi servirebbe una struttura(possibilmente con la count/find ) che faccia queste operazioni:
10 lo scompongo e aggiungo nella struttura: (2,10)(5,10)
Con il prossimo numero diventerà (2,10)(5,10)(7,7)
e poi ancora (2,10)(3,9)(5,10)(7,7)
E cosi via, avevo pensato ad un set di pair , ma non credo posso essere implementato senza aggiungere metodi o operatori, perche altrimenti per esempio in base a quale valore dei due li ordina oppure su quale dei due opera la found. Qualche suggerimento
Comunque complimenti!!, deve essere figo essere davvero competitivo soprattutto se hai ancora la possibilità di fare le OII
Non ti ho detto tutta la storia, la complessità reale è O(N + K), dove K è la dimensione dell’intervallo dei valori possibili. Se K \ll Nper il potere dell’O grande possiamo considerare la complessità come O(N). Nel caso generico con valori a 32 bit, K = 2^{32} e quindi la complessità diventa proibitiva. Sparando un valore che mi sembra decente all’una e mezza di notte e con mezzo cervello addormentato, direi che un algoritmo NlogN conviene quando K > NlogN. In generale, a meno che N non sia proibitivamente grande, usa la sort() della STL.
Usa i tag [spoiler] e [/spoiler]
Ho fatto full score alle gator, ma direi che non conta. Per il resto ho preso un argento alle ultime nazionali, purtroppo non andrò a Teheran con cavabarrett, ma comunque quest’estate parteciperò alle Balkan in Moldova.
L’operatore di default applicato ai pair è sempre operator<, che per i pair confronta prima il primo membro e poi, se questo è uguale, il secondo. Se volessi ordinarli al contrario, nell’header <functional> trovi std::greater<T> che ordina in ordine decrescente e funziona sia sui tipi base che sui pair che su std::tuple
Ok grazie mille, quindi se implemento questo template accedo normalmente ai valori con .first o .second ma se utilizzo funzioni o li inserisco in strutture la funzione si basa sul primo valore giusto? Come se li inserisco in set li ordina per il .first e se uso una find() viene applicata sul .first?
Ho provato a implementarlo in pacchetti corrotti:https: cms.di.unipi.it/#/task/abc_checksum/statement ma mi da un errore di compilazione:
checksum.cpp:6:45: error: invalid declarator before ‘operator’
template < class T1,class T2> bool pair < T1,T2 > operator< (const pair < T1 , T2 > & other)
Alla fine quello che sto cercando di implementare consiste nel, per ogni valore scomporlo in numeri primi (guardo per ogni partendo da i=2 fino a i=sqrt(del valore stesso) se il modulo valore % i==0 )allora aggiungo in una coda temporanea un pair formato dai i, valore nel caso in cui la dimensione della coda temporanea fosse uguale a 0 vuol dire che il valore preso in considerazione è lui stesso un numero primo e allora aggiungo valore, valore alla coda. Infine cerco in set che è lo stesso per tutti i valori se i numeri primi che ho aggiunto nella mia coda temporanea non sono presenti nel set allora aggiungo il pair$(numeroprimo, valore)$, altrimenti se llo trovo ritorno il valore precedente che mi aveva gia fatto risultare quel numero primo
.
) o è richiesto qualcosa che non conosci, e allora quando chiedi come risolverlo o cerchi indizi vari finisci per impararlo. Poi ci sono gli stage a Volterra, o impari o non passi 
) mentre a quelle individuali l’anno scorso ho passato loa fase scolastica ma sono uscito alle territoriali perche non avevamo fatto praticamente nulla di programmazione mentre quest anno ho passato la fase scolastica ma non ho partecipato alle territoriali perché in stage all’estero(ho provato a fare gli esercizi su cms è ho fatto 30/50 con cut off a 26 mi sembra 
, le cose di cui sono veramente fiero è l’essermi piazzato tre volte intorno al decimo posto alle COCI, e, dopo un estenuante stagione di stage a Volterra, essere risultato in seconda posizione attenendosi alla media armonica usata per selezionare la squadra IOI, e quindi molto orgoglioso di essermi qualficato 