Parallel binary search
Prerequisiti
- Ricerca binaria
- Risolvere un problema offline
Problema
Consideriamo il seguente problema LimitedMemorySeries1.
In breve il problema chiede date M query, per ogni query Q_i trovare il Q_i-esimo numero in un vettore X con N elementi.
N \leq 5000000
M \leq 100
0 \leq Q_i \leq N-1
0 \leq X_i \leq 1000000006
Limite di memoria: 1 MB
Nota
Il vettore X viene passato come tripla di valori x0, a, b e può essere generato nel seguente modo:
X[0] = x0
for i = 1 to n-1:
X[i] = (X[i-1] * a + b) % (10^9+7)
Soluzione
La soluzione naive consisterebbe nel ordinare il vettore X e per ognuna delle M query rispondere in tempo costante, tuttavia il limite di memoria non permette di allocare X.
Proviamo ad analizzare una soluzione diversa, cercando di non allocare il vettore X. Per ogni Q_i possiamo eseguire una ricerca binaria cercando il massimo y tale che il numero di elementi in minori di y sia minore di Q_i.
vector<int> Q;
bool valid(int idx, int y){
int cnt = 0;
int x = x0;
for(int i=0; i<n; i++){
if(x < y) cnt++;
x = next_x(x);
}
return Q[idx] < cnt;
}
Usando questa idea potremmo risolvere il problema facendo M ricerche binarie con una complessità pari a \mathcal O(M\cdot N\cdot \log MAXX).
Partendo da questa idea possiamo eseguire le M ricerche binarie in contemporanea. Ovvero mentre elaboriamo le N operazioni (aggiungere un numero) verifichiamo le condizioni delle M domande.
Nel nostro caso specifico dobbiamo prima ordinare le query in maniera tale che l_i \leq l_{i+1}. Successivamente per ognuno dei \log MAXX livelli, sia mid_i = (l_i + r_i) / 2, contiamo i valori di X \leq mid_i (possiamo fare questo in tempo costante usando le somme prefisse) e aggiorniamo i valori l_i e r_i di conseguenza.
In questo modo otteniamo una complessità finale pari a \mathcal O((N + M)\cdot \log MAXX).
Codice
const int MAXQ = 102;
using ll = long long;
const ll MOD = 1e9+7;
class LimitedMemorySeries1{
public:
int l[MAXQ];
int r[MAXQ];
ll check[MAXQ];
int cnt[MAXQ];
long long getSum(int n, int x0, int a, int b, vector<int> query) {
sort(query.begin(), query.end());
int m = query.size();
for(int i=0; i<m; i++) r[i] = MOD+1, l[i] = 0;
int logn = log2(MOD) + 1;
for(int i=0; i<logn; i++){
memset(check, 0, sizeof(check));
memset(cnt, 0, sizeof(cnt));
for(int j=0; j<m; j++){
check[j] = l[j] + (r[j] - l[j]) / 2;
}
ll x = x0;
for(int j=0; j<n; j++){
int idx = lower_bound(check, check + m, x) - check;
cnt[idx]++;
x = (x*(ll)a + b) % MOD;
}
for(int j=0; j<m; j++){
cnt[j+1] += cnt[j];
if(query[j] >= cnt[j]){ // cnt[i] = (numero gli x[i] <= check[i])
l[j] = check[j] + 1;
}else{
r[j] = check[j];
}
}
}
// risposta in l[i]
ll ans = 0;
for(int i=0; i<m; i++) ans += l[i];
return ans;
}
};
Pseudocodice (per il caso generale)
per logN volte:
inizializzare le variabili della ricerca binaria
per tutte le M domande:
se L[i] != R[i]:
mid = (L[i] + R[i]) / 2
aggiungi i in check[mid]
Per tutte le N operazioni op:
esegui_operazione(op)
per tutte le domande m in check[q]:
se m rispetta le condizioni:
R[m] = q
altrimenti:
L[m] = q + 1
Conclusioni
In generale la complessità di questa tecnica è \mathcal O(N\cdot X\cdot \log N), dove X dipende dal problema e dalla struttura dati utilizzata.
Esercizi
Meteors - easy
Make n00b_land Great Again! - medio