# Think About it: mle

**URL:** <https://forum.olinfo.it/t/think-about-it-mle/5853>\
**Category:** Algoritmi\
**Created:** [23 Ottobre 2019, 2:30pm UTC](https://forum.olinfo.it/t/think-about-it-mle/5853 "2019-10-23T14:30:11Z")\
**Posts on this page:** 1\
**Showing post:** 2

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [4 Novembre 2019, 5:01pm UTC](https://forum.olinfo.it/t/think-about-it-mle/5853/2 "2019-11-04T17:01:26Z")

</div>

# Editorial

Con la pubblicazione del nuovo esercizio [scavi](https://forum.olinfo.it/t/think-about-it-scavi-fortunati/5875), colgo l’occasione per pubblicare l’editorial su murale analizzando i suoi vari subtask.

## Subtask 1 ( 0 pt)

Nulla di particolare da notare oltre quello già indicato nelle spiegazioni dei vari casi d’esempio nella traccia.

## Subtask 2 ( 5 pt)

Il secondo **subtask** è molto semplice, basta realizzare ogni modifica cosi come ci sono state assegnate.

Complessità: O(N \* Q)

```auto
#include <bits/stdc++.h>

using namespace std;

void Colora(int N, int Q, vector <int> &A, vector <int> &B, vector <int> &C, vector <int> &murale){
	for(int i = 0; i < N; i++){
		murale[i] = 0;
	}
	for(int i = 0; i < Q; i++){
		for(int j = A[i]; j <= B[i]; j++){
			murale[j] = C[i];
		}
	}
	return;
}

```

## Subtasks 3, 4, 5 (10, 10, 15 pt)

Riprendiamo per un attimo la soluzione del **subtask 2** , cosa notate? Si riesce facilmente a notare che la modifica che determina la colorazione di una sezione è l’ultima query che la considera. Notato ciò possiamo usufruire delle caratteristiche di questi **subtasks** , cioè che ogni query ha termine nell’estremo opposto. Quindi per ogni sezione dobbiamo essere in grado di conoscere l’ultima modifica che la riguarda, e uno dei tanti modi per farlo è utilizzare un vettore per i prefissi e uno per i suffissi. Consideriamo per il momento il **subtask 3** , per ogni query si assegna alla B[i]-esima posizione del vettore dei suffissi l’indice della query. Ora per conoscere la query finale della i-esima sezione non dobbiamo far altro che aggiornare da destra verso sinistra il valore di ogni suffisso. Il valore dell’i-esimo suffisso è il valore massimo tra i-esima posizione e i + 1-esima posizione del suffisso. Per il **subtask 4** non dobbiamo far altro che eseguire le stesse operazioni al contrario per i prefissi e nel **subtask 5** prendere il valore massimo tra i suffissi e prefissi.

Complessità: O(N + Q)

```auto
#include <bits/stdc++.h>

using namespace std;

void Colora(int N, int Q, vector <int> &A, vector <int> &B, vector <int> &C, vector <int> &murale){
    // suffissi
	vector <int> suffix(N,-1);
	for(int i = 0; i < Q; i++){
		if(A[i] == 0){
			suffix[B[i]] = i;
		}
	}
	for(int i = N - 2; i >= 0; i--){
		suffix[i] = max(suffix[i],suffix[i + 1]);
	}
    // prefissi 
	vector <int> preffix(N,-1);
	for(int i = 0; i < Q; i++){
		if(B[i] == N - 1){
			preffix[A[i]] = i;
		}
	}
	for(int i = 1; i < N; i++){
		preffix[i] = max(preffix[i],preffix[i - 1]);
	}
    // si prende il valore massimo
	for(int i = 0; i < N; i++){
		int index = max(suffix[i],preffix[i]);
		if(index == -1){
			murale[i] = 0;
		}else{
			murale[i] = C[index];
		}
	}
}

```

## Subtask 6 (20 pt)

Nel **subtask 2** abbiamo notato come solo l’ultima modifica che riguarda l’i-esima sezione ha effetto mentre nei **subtasks 3, 4, 5** si è visto come raggiungere una complessità O(N) elaborando solo una volta una sezione; ma come possiamo utilizzare queste osservazioni per risolvere questo **subtask**? La via più semplice è di modificare il modo con cui elaborare una volta sola le sezioni, trasformando il problema in uno di ricerca e rimozione. La struttura dati che ci aiuta nel nostro scopo è il [set](http://www.cplusplus.com/reference/set/set/) che permette ricerca e rimozione di un elemento in tempi logaritmici. Eseguendo le query dall’ultima alla prima cerchiamo il primo elemento utile e lo rimuoviamo fin quando non usciamo dal range della query attuale. Prima di rimuovere l’elemento segniamo il colore alla query.

Complessità: O(N log N + Q)

```auto
#include <bits/stdc++.h>

using namespace std;

void Colora(int N, int Q, vector <int> &A, vector <int> &B, vector <int> &C, vector <int> &murale){
	for(int i = 0; i < N; i++){
		murale[i] = 0;
	}
	set <int> da_dipingere;
	set <int>::iterator it = da_dipingere.begin();
	for(int i = 0; i <= N; i++){
		da_dipingere.insert(it,i);
	}
	for(int i = Q - 1; i >= 0; i--){
		it = da_dipingere.lower_bound(A[i]);
		while((*it) <= B[i]){
			murale[*it] = C[i];
			it = da_dipingere.erase(it);
		}
	}
}

```

### Piccola sfida

In quanti modi diversi riuscite a risolvere questo subtask? Io ne ho trovati 4 😛

## Subtask 7 (40 pt)

Eccoci all’ultimo **subtask** del problema, le osservazioni fondamentali sono sempre le stesse. Cosa bisogna fare rispetto al **subtask 6** per ottenere il 100? Bisogna modificare il modo con cui effettuare le operazioni di ricerca e di rimozione. Consideriamo di dover colorare la sezione i, qual’è il successivo da colorare? Potrebbe essere i + 1 oppure il successivo di i + 1 oppure il successivo del successivo del successivo… e cosi proseguendo. In questo modo abbiamo creato un grafo direzionato in cui ogni sezione punta alla prossima da colorare. Per evitare di ripercorre sezioni già visitate, pian piano che visitiamo questo grafo cambiamo la sezione su cui punta quella attuale.

Complessità: O(N log N + Q) con fattori costanti molto più bassi della precedente soluzione.  
Provate a scriverlo 😛

# Conclusioni

Come vedete, risolvere i piccoli **subtask** di un problema aiuta nella risoluzione di quello generale. Il problema generale non è altro che l’unione di tutte le sue istante specifiche.

Spero che questo piccolo editorial vi sia piaciuto, per ogni dubbio basta lasciare un piccolo commento e il prima possibile cercherò di rispondervi 😃

## Update:

Ringrazio per la discussione sotto al post, e mi dispiace non essere intervenuto. Mi ha fatto molto piacere vedervi attivi e fornire risposte molto esaustive. Detto ciò mi scuso per l’errore nella complessità per l’ultimo subtask. Mi ricordavo fosse lineare e non logaritmica 😶  
Mi faccio perdonare linkado una pagina che offre molte informazioni sulla struttura dati utilizzata che dovevo confrontare fin dall’inizio [dsu](https://cp-algorithms.com/data_structures/disjoint_set_union.html)😅

---

_[View the full topic](https://forum.olinfo.it/t/think-about-it-mle/5853)._