Comunque quello a cui mi riferivo era molto più semplice dell’unordered_map e garantisce \mathcal O(N), simile alla soluzione di @bortoz : Counting sort
1 Mi Piace
Dovrebbe essere \mathcal O, che ottieni scrivendo $\mathcal O$
1 Mi Piace
Il counting sort non funziona solo con intervalli piccoli?
La mia soluzione funziona fino a K ≤ 10^6.
La differenza rispetto al Counting Sort è che in quest’ultimo devi controllare tutti i valori da 0 a K-1. Mentre in questo caso devi solo controllare i valori di A.
In questo caso i valori vanno da 0 a 25 sottraendo la “a” ad ogni carattere
Sei rimasto un po’ indietro direi 
Perché? Stavo rispondendo al fatto che il counting sort funziona con soli valori piccoli e in questo caso i valori vanno da 0 a 25
Hai ragione ma non stavamo più parlando di Las Vegas.
Comunque spero che queste implementazioni soddisfino la tua domanda.
Adesso guardo meglio le funzioni e magari cerco un algoritmo che può essere implementato sugli array anche solo per vedere dove sta il risparmio di tempo 
Grazie mille comunque!!
Per confrontare in O(N) due vettori A e B lunghi N si può fare qualche magheggio con gli Hash. Diciamo che K è un numero piccolo e costante, ed abbiamo K funzioni f_1,f_2,\ldots,f_K, che prendono in input un elemento del vettore e ritornano un intero. È meglio sceglierle abbastanza varie, e che possano essere calcolate in O(1). Per ogni diversa f_i, confrontiamo f_i(A_1)+f_i(A_2)+\ldots+f_i(A_N) con f_i(B_1)+f_i(B_2)+\ldots+f_i(B_N), f_i(A_1)\oplus f_i(A_2)\oplus \ldots \oplus f_i(A_N) con f_i(B_1)\oplus f_i(B_2)\oplus \ldots \oplus f_i(B_N), f_i(A_1)\cdot f_i(A_2)\cdot \ldots \cdot f_i(A_N) \mod p con f_i(B_1)\cdot f_i(B_2)\cdot \ldots \cdot f_i(B_N) \mod p. Se ogni confronto ci dà esito positivo, dobbiamo concludere che è molto molto molto molto probabile che A = B. La complessità è quindi O(N \cdot K), ma essendo K costante sarà O(N).
Ovviamente non possiamo essere certi del risultato, per essere certi dobbiamo accettare un algoritmo O(N \log N). In fondo il senso dell’hashing Montecarlo è evitare confronti lunghi dando risposte di cui si è quasi sicuri, facendo un compromesso tra velocità è sicurezza. La maggior parte delle volte funziona.
Guardando un po’ in giro ho trovato questa guida dove a pagina 245 credo sia descritto questo argomento.
Parla dell’hashing polinomiale. Due array con gli stessi elementi in ordine diverse hanno diverso Hash polinomiale
Allora probabilmente non so leggere 
Ma sfugge qualcosa a me oppure se la somma dei valori dei vettori a e b ha lo stesso risultato anche la somma delle funzioni avrò tutte lo stesso risultato:
Escludendo che le funzioni eseguono solo una moltiplicazione altrimenti ovviamente se a e b hanno come somma s_a = s_b anche s_a*k==s_b
Ma anche aggiungendo delle somme:
A: 2 3 5 s_a=10
B 0 5 5 s_b=10
con:
int f1(int val)
{
return (val*3)+1;
}
int f2(int val)
{
return (val+1)*3;
}
s_f1 su a 7+10+16=33
s_f1 su b 1+16+16=33
s_f2 su a 9+12+18=39
s_f2 su b 3+18+18=39
E cosi via per ogni funzione f_i alla fine non equivale fare la somma e poi applicare la funzione sulla somma, e quindi nel caso in cui la somma sia uguale anche la somma delle funzioni risulta uguale
usando le f_1 ed f_2 definite da te, basta che i due vettori abbiano la stessa somma. Se invece mettiamo f_2(n) = n^2, non tutti i vettori con la stessa somma avranno stessa \sum\limits_{i=1}^N f_2(V_i).
e come ho detto, non è un metodo che garantisce la correttezza
È vero non ci avevo pensato
Piccola curiosità: fra qualche giorno ci saranno le IOI tu partecipi giusto?
sì. ho tanta paura 
.
1 Mi Piace
Ma la gara come è strutturata? Sono sempre 2 giorni con 3 problemi a giorno?
sì. 2 giorni, 3 problemi, 600 punti.