Confrontare due array in O(n), è possibile?

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 :joy:

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 :smile:

Grazie mille comunque!!:blush:

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 :joy:

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 :smile:

Piccola curiosità: fra qualche giorno ci saranno le IOI tu partecipi giusto?

sì. ho tanta paura :cry::cry::cry::cry:.

1 Mi Piace

Ma la gara come è strutturata? Sono sempre 2 giorni con 3 problemi a giorno?

sì. 2 giorni, 3 problemi, 600 punti.