# Las Vegas(Insegna) **URL:** \ **Category:** Aiuto\ **Created:** [9 Marzo 2020, 6:16pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091 "2020-03-09T18:16:43Z")\ **Posts on this page:** 18\ **Page:** 1
**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\ **Post date:** [9 Marzo 2020, 6:16pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/1 "2020-03-09T18:16:43Z")
Scusate mi potreste dare una mano a capire dove sbaglio nel problema “insegna”,avendo la febbre ora(non è corona state tranquilli) non riesco ad essere tanto lucido mi potreste aiutare,vi lascio di seguito il codice: ```auto #include using namespace std; int main(){ ofstream out("output.txt"); ifstream in("input.txt"); long long int N; in>>N; string s,s1,s2,s3; in>>s>>s1; long long int i=0; bool A=false; while(N/2-i!=0 && A==false){ s2=s.substr(0,N/2-i); s3=s.substr(N/2-i,N-(N/2+i)); if(s1.find(s2)!=-1 && s1.find(s3)!=-1){ A=true; } else{ i++; } } while(N/2+i!=N && A==false){ s2=s.substr(0,N/2+i); s3=s.substr(N/2+i,N-(N/2-i)); if(s1.find(s2)!=-1 && s1.find(s3)!=-1){ A=true; } else{ i++; } } if(A==true){ out<<1; } else{ out<<0; } } ``` Se vi servono dei chiarimenti sulla mia idea chiedete,grazie in anticipo. ---
**Author:** ![alep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/f19dbf/32.png) [@alep](https://forum.olinfo.it/u/alep)\ **Post date:** [9 Marzo 2020, 10:22pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/2 "2020-03-09T22:22:28Z")
non ti so dire esattamente quale sia l’errore, se vuoi un hint ti posso dire che io l’ho risolto con un piccolo escamotage usando una sola data structure e un controllo. ---
**Author:** ![fl0rian](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fl0rian/32/2336_2.png) [@fl0rian](https://forum.olinfo.it/u/fl0rian)\ **Post date:** [10 Marzo 2020, 8:03am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/3 "2020-03-10T08:03:34Z")
Potresti spiegare a parole cosa fa il tuo codice? In ogni caso, dato che la lunghezza massima delle stringhe è 5000, potresti fare cosi : - fissi una stringa s1 e controlli se è uguale a s2, se si stampi 1. - altrimenti ruota a sx o a dx la stringa s2 e ripeti il ciclo. - se ritorni al s2 di partenza (dopo n rotazioni) stampa 0. “ciao” ruotato a sx di 1 -\> “iaoc” ---
**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\ **Post date:** [10 Marzo 2020, 10:09am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/4 "2020-03-10T10:09:10Z")
Ora l’ho risolto il problema però sarei curioso di sapere che tecnica hai usato ---
**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\ **Post date:** [10 Marzo 2020, 10:10am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/5 "2020-03-10T10:10:23Z")
Sisi ho fatto una cosa del genere ma leggermente diversa e ho preso 100 però anche questa idea è validissima ---
**Author:** ![alep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/f19dbf/32.png) [@alep](https://forum.olinfo.it/u/alep)\ **Post date:** [10 Marzo 2020, 10:18am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/6 "2020-03-10T10:18:14Z")
ho inserito le due stringhe(char per char) in 2 multiset distinti,(nel caso non lo sapessi puoi confrontarli con un if(multi1 == multi2)) se possiedono gli stessi elementi restituisce 1 altrimenti 0 ---
**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\ **Post date:** [10 Marzo 2020, 10:32am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/7 "2020-03-10T10:32:35Z")
a ok ho capito,molto bella questa idea ---
**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\ **Post date:** [10 Marzo 2020, 10:37am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/8 "2020-03-10T10:37:23Z")
sempre per curiosità cosa ha di diverso o in più un multiset da un set? ---
**Author:** ![alep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/f19dbf/32.png) [@alep](https://forum.olinfo.it/u/alep)\ **Post date:** [10 Marzo 2020, 10:41am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/9 "2020-03-10T10:41:27Z")
in un set non ci possono essere ripetizione di caratteri o interi etc… nel multiset puoi invece avere ripetizioni di valori inseriti. entrambi vengono sortati all’inserimento di un valore. esempio: hai un array {3,4,4,2} se inserisci l’array nel set avrai {2,3,4} se lo inserisci nel multiset avrai {2,3,4,4} (esistono anche gli unordered\_set e unordered\_multiset, penso tu possa intuire la loro funzione) ---
**Author:** ![Mat0k3](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/35a633/32.png) [@Mat0k3](https://forum.olinfo.it/u/Mat0k3)\ **Post date:** [10 Marzo 2020, 10:43am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/10 "2020-03-10T10:43:11Z")
ah ok capito,si le strutture di tipo unordered gia le conoscevo,grazie mille ---
**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\ **Post date:** [10 Marzo 2020, 11:42am UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/11 "2020-03-10T11:42:09Z")
Se vi può interessare esiste anche una soluzione in O(N), in pratica quando devo capire se `arolap` è una rotazione di `parola` mi basta cercare `arolap` nella stringa `parolaparola`, questo può essere fatto usando [KMP](https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/) o [Rabin-Karp](https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching/) (dipende dalla vostra [religione](https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/)). Comunque non ho capito la soluzione di @alep, così non controlla solo che una sia l’anagramma dell’altra? ---
**Author:** ![alep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/f19dbf/32.png) [@alep](https://forum.olinfo.it/u/alep)\ **Post date:** [10 Marzo 2020, 12:36pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/12 "2020-03-10T12:36:41Z")
```auto char l; multiset w,c; int N; cin>>N; for(int i=0;i>l; w.insert(l); } for(int i=0;i>l; c.insert(l); } if(w==c){ cout<<1; }else{ cout<<0; } ``` questa è la mia sol ---
**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\ **Post date:** [10 Marzo 2020, 1:06pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/13 "2020-03-10T13:06:18Z")
Ahem, è sbagliata 😅 Cioè in teoria se hai ```auto 4 aabb abab ``` La risposta dovrebbe essere 0, il tuo codice dovrebbe rispondere 1, mi sembra assurdo che non ci sia un tc del genere tra gli input. Anyway se vuoi sbizzarrirti con gli anagrammi c’è un [problema](https://training.olinfo.it/#/task/writing/statement) carino 😉 (nel quale tra l’altro credo che un multiset non sia abbastanza efficiente) ---
**Author:** ![alep](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/f19dbf/32.png) [@alep](https://forum.olinfo.it/u/alep)\ **Post date:** [10 Marzo 2020, 1:10pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/14 "2020-03-10T13:10:13Z")
wow, mi era sorto qualche dubbio quando sottoposi ma non credevo fosse veramente sbagliata, comunque proverò a vedermi quel problema che mi hai consigliato(nonstante mi sia ripromesso di lasciar stare i problemi con le stringhe), grazie mille ---
**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\ **Post date:** [10 Marzo 2020, 1:13pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/15 "2020-03-10T13:13:33Z")
Ma figuati, felice di aiutare (comunque per me i problemi con le stringhe non sono per niente male 🌚, a meno che non richiedano di implementare un suffix tree obv) ---
**Author:** ![mauro\_losmauro](https://forum.olinfo.it/user_avatar/forum.olinfo.it/mauro_losmauro/32/2910_2.png) [@mauro\_losmauro](https://forum.olinfo.it/u/mauro_losmauro)\ **Post date:** [10 Marzo 2020, 1:14pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/16 "2020-03-10T13:14:05Z")
Rispetto a quei algoritmi, a livello computazionale quanto è peggiore la funzione della STL std::is\_permutation()? ---
**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\ **Post date:** [10 Marzo 2020, 1:29pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/17 "2020-03-10T13:29:33Z")
Eh purtroppo non conosco nel dettaglio le implementazioni, tuttavia con N abbastanza grandi `is_permutation` comincia a perdere molto, avendo complessità N^2 contro la NlogN dell’inserire gli elementi nel multiset. Comunque se stai cercando la velocità un multiset è eccessivo, basta sortare le stringhe con `std::sort(stringa.begin(),stringa.end())` e poi compararle (complessità sempre NlogN ma con fattori costanti minori), oppure potresti usare algoritmi più efficienti quando l’alfabeto è piccolo, come il counting sort O(N + grandezza\ alfabeto). ---
**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\ **Post date:** [10 Marzo 2020, 3:03pm UTC](https://forum.olinfo.it/t/las-vegas-insegna/6091/18 "2020-03-10T15:03:05Z")
KMP e Rabin-Karp sono entrambi lineari quindi O(N), `is_permutation()` è O(N^2) quindi con un time-limit di 1s KMP e Rabin-Karp si fermano quando N vale qualche milione, con O(N^2) ti fermi a qualche miglialia.