Think About it: Hasta

È ora disponibile hasta il sesto episodio della rubrica TAI . Anche per questo esercizio, tra circa due settimane uscirà un editorial.
Ringraziamo @lukecavabarrett per aver fornito l’idea e l’ aiuto nella preparazione dell’esercizio e @edomora97 per aver debuggato anche l’anima per farlo funzionare.
Al prossimo problema o editorial di questo :stuck_out_tongue:

4 Mi Piace

Editorial

Con l’uscita di Luna Park, pubblichiamo l’editorial di hasta.

Problem statement

https://training.olinfo.it/#/task/tai_hasta/statement

Subtask 1

Casi d’esempio

Subtask 2

N ≤ 2 000, e istiga viene chiamata al più 2 000 volte

Trattiamo ogni query separatamente, considerando soltanto il subarray interessato.
Iniziamo contando per ogni classe sociale il numero di appartenenti; poi per ogni classe sociale contiamo se il numero di presenti è corretto.

int istiga(int l,int r) {
    std::vector<int> count(K,0);
    for(int i=l; i<=r; i++)count[V[i]]++;
    int ans = 0;
    for(int i=0; i<K; i++) if (count[i]==R[i]) ans+=R[i];
    return ans;
}

Per ogni query usiamo spazio O(K) e tempo O(N+K) = O(N).
Complessivamente usiamo spazio O(K) e tempo O(NQ).

Subtask 3

K ≤ 100, e istiga viene chiamata al più 70 000 volte

Ipotizziamo K sia particolarmente basso, e proviamo a migliorare la parte del conteggio della soluzione precedente (primo ciclo for).
Possiamo costruire per ogni classe sociale una qualsiasi struttura dati che possiamo usare per contare efficientemente quanti membri sono presenti in un arbitrario subarray. La soluzione per una singola query diventa quindi.

int istiga(int l,int r) {
    int ans = 0;
    for(int i=0; i<K; i++) if (data_structure[i].count_query(l,r)==R[i]) ans+=R[i];
    return ans;
}

Per ogni query usiamo spazio O(1) e tempo O(K) \cdot \text{count_query}.

Abbiamo diverse opzioni per la struttura dati per il conteggio:

Struttura Dati Spazio Tempo costruzione Tempo query
Segment Tree O(N) O(N) O(\log N)
Fenwick Tree O(N) O(N) O(\log N)
Prefix Sum O(N) O(N) O(1)

In questo caso le somme prefisse fanno al caso nostro, quindi pagheremo inizialmente tempo e spazio O(KN) per il preprocessing iniziale (ricorda che dobbiamo costruire una versione della struttura dati per ogni classe sociale) e tempo O(K) per query.
Complessivamente la nostra soluzione usa spazio O(KN) e tempo O(KN + KQ).

Subtask 4

r = N − 1

Vogliamo costruire la soluzione per ogni suffisso.
Partiamo dal fondo, ed aggiungiamo le persone da destra verso sinistra. Come cambia la soluzione aggiungendo una persona di classe sociale k?
Diciamo che questa persona è esattamente l’i-esima persona di tale classe sociale che abbiamo incontrato finora - in altre parole il suffisso considerato contiene esattamente i individui di classe k.

  • Se i < R_k, il valore della soluzione non cambia in quanto non abbiamo comunque abbastanza persone.
  • Se i = R_k, il numero di persone di classe k ha appena raggiunto il valore rivoluzionario, quindi il valore della soluzione sale di R_k.
  • Se i = R_k+1, il numero di persone di classe k, (che prima di quest’ultima aggiunta era esattamente rivoluzionario) smette di essere rivoluzionario (troppe persone) quindi il valore della soluzione scende di R_k.
  • Se i > R_k+1, il numero di persone di classe k era già troppo grande per fare rivoluzione, e quindi aggiungere persone non cambia la soluzione.

In questa maniera possiamo quindi possiamo semplicemente costruire tutti i suffissi in tempo e spazio O(N), e rispondere ogni query in O(1).

Notare come questa soluzione sia equivalente ad assegnare un valore ad ogni elemento (come sopra) e la risposta per una query sia nient’altro che la somma dei valori degli elementi in quel range. Può essere risolto con tutte e tre le strutture dati di cui sopra - in questo caso usando Suffix sums.

Complessivamente la nostra soluzione usa spazio O(N) e tempo O(N+Q).

Nota: Se al posto di R_i ogni classe sociale avesse un intervallo rivoluzionario [L_i, R_i] una soluzione simile potrebbe essere creata assegnando diversamente i pesi. Questa variante può essere adattata anche alle soluzioni dei subtasks successivi. La descrizione completa è lasciata come semplice esercizio al lettore.

Subtask 5

istiga viene chiamata con r crescente.

Consideriamo la soluzione descritta per il subtask precedente i.e. assegnare ad ogni persona un valore tale che la risposta sia la somma del suffisso, ed immaginiamo che arrivi una nuova persona in fondo alla fila, di classe sociale k. Vogliamo correggere i valori per rispondere ai suffissi di questa nuova fila.
Siccome il valore di un elemento è esclusivamente in funzione del numero di elementi della stessa classe sociale alla sua destra, tutti i valori degli elementi con classe sociale \neq k rimarranno invariati. Se consideriamo solo gli elementi di classe sociale k, vediamo che i loro valori shifteranno a destra di una posizione. Essendo al più 2 gli elementi con valore diverso da zero, al massimo 3 elementi della classe sociale k cambieranno valore.
Dopo aver aggiornato i valori come descritto, la risposta per un suffisso sarà ancora la somma dei valori del suffisso stesso.
Necessitiamo quindi di una struttura dinamica che supporti le seguenti operazioni:

  • modificare il valore di un elemento
  • calcolare la somma di un suffisso

Avendo tale struttura possiamo partire con una fila vuota, e man mano che dobbiamo processare query con r crescente aggiungiamo le persone a destra della fila, e rispondiamo con la somma del suffisso appropriato. Per comodità inizializziamo a 0 tutti gli elementi fuori dalla fila attuale.

data_structure p;
int last_added;

void inizia(N){
    p = data_structure.zeros(N);
    last_added = -1;
}

int istiga(int l,int r){
    while(last_added < r)estendi_destra();
    return data_structure.suffix_sum(l);
}

void estendi_destra(){
    // TODO:
    // Aggiungi il cittadino in posizione last_added e aggiorna i valori
    // dei cittadini della stessa classe sociale. Può essere utile tenere
    // per ogni classe sociale un std::vector con gli indici dei cittadini
    // di tale classe sociale incontrati finora.
    ++last_added;
}

Per quanto riguarda la struttura dati, consideriamo le nostre opzioni:

Struttura Dati Spazio Tempo costruzione Tempo query Tempo update
Segment Tree O(N) O(N) O(\log N) O(\log N)
Fenwick Tree O(N) O(N) O(\log N) O(\log N)
Prefix Sum O(N) O(N) O(1) O(N)

Effetturemo O(N) updates (3N al massimo) e Q queries.
Questo esclude chiaramente Prefix sums, e ci fa scegliere Segment Tree o Fenwick Tree - l’ultimo è praticamente più performante ed usa meno memoria, ma entrambi garantiscono la stessa complessità.

Complessivamente la soluzione usa spazio O(N) e tempo O(N\log N + Q \log N).

Subtask 6

Nessuna limitazione specifica.

Vogliamo estendere la soluzione descritta per il subtask precedente per il caso generico. Nel subtask 5 sfruttavamo la proprietà di poter incrementare r in O(\log N) per rispondere online le query ricevute. Se ricevessimo una query con r inferiore al prefisso per il quale abbiamo attualmente costruito la struttura dati che ne risolve i suffissi, ci troveremmo nella situazione di dover in qualche modo tornare indietro nel tempo a quando il prefisso costruito era di lunghezza desiderata.

Ci accorgiamo come la soluzione è semplice se ci è concesso di viaggiare nel tempo: iniziamo costruendo la struttura dati per tutti i prefissi (N chiamate ad estendi_destra nel codice sopra), e per ogni query [l,r] ricevuta viaggiamo nel tempo all’istante in cui la struttura dati gestiva il prefisso [0,r] e rispondiamo con la somma del suffisso [l,\ldots).

Quello che dobbiamo fare è quindi modificare la struttura dati per consentire query nel passato. Entriamo nel campo della persistenza, ovvero disegnare strutture dati che mantengono gli stati passati in esse.

Ciò che possiamo utilizzare è la persistenza funzionale, cioè invece che sovrascrivere la struttura dati, ne creiamo una copia con le nuove informazioni, preservando la versione precedente. Nel caso generale questo può essere inconveniente in quanto può richiedere la copia di molti dati, ma nel caso del Segment Tree possiamo copiare in maniera economica.

Immaginiamo di implementare i Segment Tree in memoria, dove ogni nodo è del tipo

struct node{
    int sum; // somma dei valori nel sottoalbero
    int l,r; // range di competenza del nodo
    node *left,*right; // i due figli del nodo
};

Immaginiamo di voler modificare il valore in posizione i. Senza perdita di generalità, assumiamo di voler incrementare il valore di \Delta. Come abbiamo detto prima, vogliamo creare un nuovo segment tree dove l’unica differenza rispetto al precedente sarà questo incremento.
Iniziamo creando la radice del nuovo segment tree: l,r saranno uguali, mentre sum avrà valore old_root->sum+\Delta.
Senza perdita di generalità, assumiamo che i cada nell’intervallo gestito dal figlio sinistro della radice. Questo significa che tutto il sottoalbero destro della radice rimarrà invariato, ed invece che crearne una copia possiamo semplicemente assegnare new_root->right = old_root->right;. Ricorriamo similmente sul sottoalbero sinistro. A conti fatti solo i nodi nel percorso dalla radice alla foglia che rappresenta i avranno cambiato valore, e quindi ci basterà riallocare quei nodi, e relinkarli ai sottoalberi lasciati immutati. Per effettuare tale operazione abbiamo dovuto quindi allocare O(\log N) nodi aggiuntivi e costruire il nuovo albero in tempo O(\log N).
Possiamo quindi costruire per ogni prefisso il Segment Tree che lo risolve in tempo e spazio O(N \log N), e rispondere ogni query identificando la versione su cui vogliamo eseguire la query in O(1) ed eseguendo una query su tale Segment Tree in O(\log N).

Complessivamente la soluzione usa spazio O(N \log N) e tempo O(N\log N + Q \log N).

Caso d’esempio con Persistent Segment Tree

  • Consideriamo V = [2, 2, 2, 1, 2, 2] e per ogni classe sociale k abbiamo R_k = 3.
    Per gestire [], costruiamo un PST di soli zero (bianco).

  • Aggiungendo elementi a destra, il primo cambiamento di peso avviene a [2, 2, 2] - il 2 in posizione 0 cambia valore da 0 a 3.
    Costruiamo un altro PST con la modifica (azzurro).

  • Il cambiamento successivo avviene inserendo un ulteriore 2 (V = [2,2,2,1,2]); il secondo 2 (posizione 1) cambia valore da 0 a 3, mentre il primo 2 (posizione 0) cambia valore da 3 a -3.
    Costruiamo un primo PST con la prima modifica (verde)


    Ed uno con la seconda modifica (arancione).

  • L’aggiunta dell’ultimo 2 fa shiftare ulteriormente i valori: il primo 2 va a 0, il secondo 2 va a -3, il terzo 2 va a 3.
    Prima modifica (terzo 2 da 0 a 3) (giallo)


    Seconda modifica (secondo 2 da 3 a -3) (rosso)

    Terza modifica (primo 2 da -3 a 0) (viola).

Statistiche

tai_hasta si aggiudica il primo posto come l’esercizio più difficile della rubrica con solamente 6 persone ad averlo risolto, 16 ad averlo provato, 22 soluzioni corrette e 408 soluzioni inviate al momento della scrittura dell’editorial.

Conclusioni

Un ringraziamento a @frakkiobello e @zJack1342 per l’aiuto nel transformare questa idea in un problema; ed anche a @wil93 per l’aiuto tecnico.

Appendice

Per gli interessati a questo ambito in maniera più ampia, un’interessante lezione del prof. Demaine sulla persistenza, che va ben oltre gli scopi di questo problema.

Persitent Data Structures | MIT 6.851 Advanced Data Structures, Spring 2012 | Prof. Erik Demaine

Video on MIT OCW

6 Mi Piace