Editorial (non ufficiale) OII 2020

MrBrionix · 27 Novembre 2020, 2:56pm

Editorial (non ufficiale) OII 2020

In questo post proverò a descrivervi le mie soluzioni ai problemi che ho risolto partecipando al mirror delle OII 2020.

Prerequisiti

Sapere cos’è una deque (libreria in c++ che la implementa: <deque>): è una coda (a doppia estremità) che permette di guardare/aggiungere/eliminare un elemento davanti alla coda (operazioni front(),push_front() e pop_front()) e guardare/aggiungere/eliminare un elemento in fondo alla coda (operazioni back(),push_back() e pop_back()), ognuna di queste operazioni ha complessità \mathcal O(1). Ci servirà per il problema Candele;
conoscenze base sui grafi: sapere come memorizzare un grafo tramite liste di adiacenza e saper implementare l’Algoritmo di Dijkstra per cercare il cammino minimo. Ci servirà per il problema Candele;
Sapere cos’è una mappa (libreria in c++ che la implementa: <map>): le mappe sono delle strutture associative che memorizzano elementi formati da una combinazione di un valore chiave e un valore mappato. Ci servirà per il problema Ristorante e Compleanno;

//mappa in cui gli indici sono dei long long e i valori mappati sono degli interi
map<long long,int> f; 

/*crea un elemento di valore 42 che ha indice 3485342382 
(nota: viene usata memoria solo per allocare questo nuovo elemento, 
quindi non viene allocato spazio per gli elementi con indice compreso 
tra 0 e 3485342381) */
f[3485342382]=42;

conoscenze di programmazione dinamica: è una tecnica di risoluzione che consiste nella suddivisione del problema in sottoproblemi più piccoli (e più semplici) da risolvere. Ci servirà per il problema Compleanno.

Candele

Si consideri il seguente grafo: ciascun nodo rappresenta una candela e vi sia un arco diretto x\rightarrow y di peso t per ogni coppia di candele (x,y) tali che, dopo un eventuale accensione di x verrebbe accesa anche y dopo t secondi (la miccia di y è raggiungibile e ha distanza t dalla miccia di x). Ora si può notare come il problema chieda semplicemente la distanza minima di ogni candela dalla candela 0, che si può calcolare applicando dijkstra sul grafo che abbiamo costruito partendo dal nodo 0.

Però sorge una complicazione: il numero di archi da costruire può essere molto elevato (dell’ordine di N^2, dove N è il numero di candele) e quindi non è possibile costruirli tutti. Per risolverla è necessario notare che non sono davvero necessari tutti gli archi, ma per ogni candela x è necessario tenere solo i due archi che corrispondono alle due candele (che chiamiamo a e b) più vicine a destra e a sinistra che la accendono.

Dimostrazione

se la candela x (diversa da 0) viene accesa, allora almeno una candela tra a (la candela a destra più vicina che accende x) e b (la candela a sinistra più vicina che accende x) devono essere state accese in precedenza (e quindi sono sufficienti questi due archi per considerare l’accensione di x).
\square

Quindi è sufficiente tenersi questi \mathcal O(N) archi e applicare dijkstra su questo grafo.

Qualche spunto di implementazione (in pseudo codice)

ordino le candele rispetto alla posizione della miccia
q è una deque (di candele) inzialmente vuota 

for(int i=0;i<n;i++){
  while(candela[i] accende la candela che si trova in deque.back() ){
    creo un arco da candela[i] alla candela deque.back()
    q.pop_back();
  } 
  q.push_back(candela[i]);
}

In questo modo in \mathcal O(N) vado a creare tutti gli archi necessari che vanno da destra verso sinistra (per ogni candela ho messo l’arco relativo alla candela più vicina a destra che la accende). Per creare gli archi verso destra basta ripetere il procedimento invertendo l’array che contiene le candele.

Dopodichè applicare dijkstra partendo dal nodo 0 permette di calcolare il cammino minimo (che è il valore che viene richiesto dal problema) per ogni candela.

Ristorante

Chiamiamo gli array di antipasti, pizze e dessert rispettivamente array 1,2,3. Si consideri la seguente strategia:

Scegliamo X elementi dall’array a, poi finchè posso (ovvero finchè non ho già preso un piatto con lo stesso prezzo) prendo degli elementi dall’array b, poi finchè posso prendo gli elementi dall’array c. ((a,b,c) è una permutazione di (1,2,3))

Se si itera questa strategia su tutte le 3! permutazioni di (1,2,3) e su tutti i possibili valori di X, si troverà la soluzione al problema.

Dimostrazione

Diciamo che l’array v blocca l’array w se, incrementando di uno gli elementi presi nell’array w, andiamo a prendere un elemento che è già preso nell’array v (oppure, caso particolare, non posso incrementare di 1 gli elementi presi da w perché li ho già presi tutti)

Nella soluzione ottimale ovviamente ogni array è bloccato da un altro array, altrimenti potremmo aumentare gli elementi presi.

Quindi nella soluzione ottimale esiste una tripla (a,b,c) che è una permutazione di (1,2,3) tale che: c è bloccato da b, b è bloccato da a. (a sarà bloccato da qualcuno ma non ci interessa)

Questa soluzione con tripla (a,b,c) viene considerata se faccio la strategia:
Scegliamo X elementi dall’array a, poi finchè posso prendo degli elementi dall’array b, poi finchè posso prendo gli elementi dall’array c.
(Provando tutti gli X possibili)
\square

Quindi ora abbiamo ristretto il campo a 3!\cdot N casi da analizzare (3! sono le permutazioni e N i possibili valori di X). Ora si può notare come, data una permutazione (a,b,c), è possibile calcolare i piatti presi per tutti gli X possibili in \mathcal O(N\log N).

Infatti si supponga di calcolare inizialmente il numero di piatti presi seguendo la strategia con il massimo X possibile: basta scorrere l’array a e in modo greedy prendere il piatto se non è già stato preso un altro piatto con lo stesso prezzo (per fare questo controllo in \mathcal O(\log N) è necessario usare una mappa o un set), altrimenti passare all’array b e continuare a prendere i piatti finchè possibile e poi fare lo stesso con c. In questo modo viene calcolato X, il numero Y di piatti presi nel secondo array e il numero Z di piatti presi nel terzo array in \mathcal O(N\log N).

map<int,int> f;  //f[i] mi dirà quante volte ho preso un piatto con prezzo i
siano a,b,c i 3 array
int x=0,y=0,z=0;

while(x<N && f[a[x]]==0){ //finchè posso prendo i piatti dal primo array
  x++;
  f[a[x]]++;
}

while(y<N && f[b[y]]==0){ //poi passo al secondo
  y++;
  f[b[y]]++;
}

while(z<N && f[c[z]]==0){ //poi passo al terzo
  z++;
  f[c[z]]++;
}

Si può notare inoltre che se X diminuisce di uno, i valori di Y e Z possono solo aumentare, quindi non è necessario ricalcolarli da capo, ma semplicemente si può prendere il valore di Y ottenuto precedentemente e provare a vedere se può aumentare (andando a controllare solo il (Y+1)-esimo piatto) e lo stesso vale per Z.


x--; //ora calcoliamo il valore per un x più piccolo di uno
f[a[x]]--;

while(y<N && f[b[y]]==0){ //provo ad aumentare y
  y++;
  f[b[y]]++;
}

if(z<N && f[c[z]]==0){ //provo ad aumentare z
  z++;
  f[c[z]]++;
}

Il valore di X diminuisce sempre, quelli di Y e Z aumentano sempre quindi la complessità totale è \mathcal(N\log N) (il fattore \log N è dovuto alla complessità della mappa per controllare se esiste un elemento con un certo prezzo)

Ricapitolando la complessità della nostra soluzione è \mathcal O(k!N\log N), dove k è il numero di array (nel nostro problema si ha sempre k=3) e N il numero di elementi di ciascun array.

Compleanno

Facciamo qualche osservazione:

Possiamo assumere che nessuna operazione incolla avvenga subito dopo un’operazione aggiungi (perchè in tal caso scambiando l’ordine delle due operazioni il risultato rimarrebbe invariato);
Quindi possiamo assumere che ogni operazione copia sia seguita un certo certo numero x\geq 1 di operazioni incolla (altrimenti sarebbe inutile) e nessuna operazione incolla sia preceduta da un’operazione aggiungi;
Un’operazione copia seguita da X operazioni incolla equivale a moltiplicare il numero di emoji per X+1;
Un’operazione copia seguita da X operazioni incolla impiega complessivamente X+2 click.

Quindi il problema è equivalente a dire che, partendo da 0 emoji, dobbiamo ottenere N emoji (minimizzando il costo) usando le seguenti operazioni:

aggiungere un’emoji (questa operazione ha costo 1);
moltiplicare per un numero X\geq 2 il il numero di emoji attualmente presenti (questa operazione ha costo X+1)

Inoltre si può notare come non sia mai ottimale moltiplicare il numero di emoji presenti per un numero X>5 che non è primo.

Dimostrazione

Se X>5 non è primo, allora \exists y,z>1 tali che X=yz . Inoltre si ha che y+z<X:

yz>y+z \iff yz-y-z>0 \iff yz-y-z+1≥2 \iff (y-1)(z-1)≥2 e quest’ultima è sempre vera dato che x,y>1 e non posso essere entrambi 2 (visto che il loro prodotto è maggiore di 5).

Ma allora ne consegue che conviene sempre moltiplicare il numero di emoji prima per y (costo y+1) e poi per z (costo z+1), anzichè direttamente per X, dato che:
y+z<X
y+1+z+1\leq X+1 (quindi sicuramente si ottiene un costo uguale o minore)
\square

Inoltre si può dimostrare che non è mai necessario moltiplicare il numero di emoji per un certo X primo maggiore di 19. (La dimostrazione è lasciata al lettore)

Quindi ora è possibile fare una dp di questo tipo:
f(x)=costo minimo per ottenere x emojis

sapendo che le uniche operazioni sono: moltiplico per 2,3,4,5,7,11,13,17 o 19 il numero di emoji attuali (con rispettivo costo 3,4,5,6,8,12,14,18,20), oppure aggiungo una emoji (costo 1).
Quindi le transizioni della nostra dp saranno:

f(x)= min_{0\leq i<9}(f(\lfloor {x/val[i]} \rfloor)+val[i]+1+(x\%a[i]))
dove val[9]=\{2,3,4,5,7,11,13,17,19\}

faccio notare che ci sono dei corner case per gli x<5, in cui il costo minimo è semplicemente x. (se si usasse la transizione descritta sopra si otterrebbe x+1 come costo minimo) Questo è dovuto al fatto che nella strategia ottimale per ottenere x<5 emoji sono necessarie solo operazioni del tipo “aggiungi un’emoji”, senza moltiplicare il numero di emoji in nessuno momento.

Chiamando f(N) si otterrà il costo minimo.
Nota: nel problema viene chiesto esplicitamente anche la sequenza di operazioni, quindi oltre a salvare il numero minimo di operazioni è necessario tenere traccia anche dell’operazione da eseguire che consente di ottenere tale minimo, in modo da poter fare backtracking e ottenere la sequenza finale. Per salvare queste informazioni non è possibile usare un array (visto che i numeri arrivano fino a 10^{18}), ma si possono tenere in modo sparso usando una mappa.

Richiesta

@taulant (che ha partecipato alla gara ufficiale) è interessato a sapere un po di più sulla classifica prima di martedì, e mi ha chiesto di fare questo annuncio: se qualcuno ha fatto più di 100 in gara scrivetegli in privata.

Grazie a tutti e avvisatemi di eventuali typo o errori.

anon28322201 · 30 Novembre 2020, 10:36am

Faccio notare che in candele basta uno stack al posto della deque (lettura e scrittura avvengono dalla stessa parte del contenitore)

frakkiobello · 2 Dicembre 2020, 3:17pm

Propongo una soluzione alternativa, a mia detta più semplice, per risolvere candele:

L’idea principale è sfruttare la disposizione delle candele per simulare velocemente l’ordine in cui si accendono. Per iniziare è quindi necessario ordinare le candele per la loro coordinata ed individuare la prima candela accesa. Sono poi necessarie due code left e right (inizialmente vuote) che, durante un certo istante, contengono rispettivamente gli indici delle candele che permettono l’accensione delle candele alla sinistra e destra di quelle iniziale. Servono anche 2 indici:

l indice della candela spenta con coordinata massima alla sinistra della candela iniziale.
r indice della candela spenta con coordinata minima alla destra della candela iniziale.

Il procedimento inizia inserendo nella coda esatta(left se miccia della prima candela ha coordinata maggiore rispetto alla sua base, right in caso contrario) l’indice della prima candela accesa. Poi fino a quando le 2 code non si sono svuotate oppure ho già acceso tutte le candele procedo facendo:

Prendo il primo elemento della coda left, sarà una candela che è già stata accesa che si espande verso sinistra e provo a verificare se mi permette di accendere la candela in posizione l. Se non me lo permette (la base della candela con indice in testa alla coda left ha coordinata maggiore rispetto alla miccia della candela in posizione l) allora elimino quell’indice dalla coda left (infatti significa tale candela non mi permette di accendere altre candele a sinistra) e ripeto il controllo con l’indice successivo. Mi fermo quando trovo l’indice di una candela che copre quella in posizione l oppure quando svuoto la coda:
- Se ho svuotato la coda allora significa che per il momento non ho nessun modo per accendere la candela in posizione l e quelle alla sua sinistra. E quindi aspetto che qualche candela che non ho ancora accesso (e che quindi non è ancora nelle code) alla destra della candela iniziale permetta di accendere tali candele.
- Se invece ho trovato l’indice che cercavo allora saprò in che istante si accenderà la candela l, infatti la candela in testa alla coda left , supponiamo abbia indice x sarà già stata accesa all’istante T[x] (notare come tali indici vengono infatti inseriti nelle code soltanto quando sono stati accesi) e conoscendo la distanza tra le 2 candele posso calcolare dopo quanti istanti da T[x] si accenderà anche la candela in posizione l.
  Ora devo quindi usare inserire la candela l in una delle 2 code e decrementare l, ed avrò due casi:
  - Se la candela l ha la miccia con coordinata maggiore rispetto alla sua base, significa che anche essa si svilupperà verso sinistra, allora dovrò controllare se la sua base abbia coordinata inferiore rispetto alla base della candela x, in tal caso sostituirò x con l in testa alla coda left in quanto è come se virtualmente spostassi la base della candela x fino alla base della candela l.
  - Se la candela l invece ha la miccia con coordinata inferiore rispetto alla sua base, significa che si svilupperà verso destra, allora sarà sufficiente aggiungere in fondo alla coda right l’indice l.

Ripeto tale procedimento, e quello simmetrico per la coda right e l’indice r fino a quando non mi è più permesso accendere altre candele, le candele che non saranno state accese saranno dunque irraggiungibili (capita se svuoto left e right prima di arrivare a l = -1 oppure r=N (0-based)), mentre per le altre avrò trovato l’istante in cui si accendono.

Per convincerci del fatto che un procedimento come questo funzioni bisogna notare come l’ordine degli indici nelle code left /right siano ordinati rispetto a quanto prima permetterebbero alla candele alla sinistra/destra della candela iniziale di accendersi.
Per esempio se quando stiamo analizzando l essa si espande a destra verrà inserita in coda a right infatti è quella che permetterebbe alle candele alla destra di quella iniziale di accendersi più tardi, infatti delle candele accese attuali è la più lontana da quella a destra, e quindi quella che ci impiegherà più tempo per raggiungerle. Viceversa quando la candela l va verso sinistra allora allora è come se la inserissi in testa alla coda perché inizia ad espandersi contemporaneamente alla candela x che era quella che permetteva alle candele a sinistra di accendersi più presto possibile(infatti era in testa alla coda).

Analizziamo quindi la complessità dell’algoritmo. Supponendo di avere un insieme di N candele, allora avrò la parte iniziale di ordinamento con complessità O(NlogN), per capire la complessità della simulazione invece basta notare come ogni indice sia inserito in una delle code solo una volta, ed essendo le operazioni utilizzate implementate in tempo costante, si ottiene una complessità di tempo finale di O(NlogN). Per quanto riguarda la memoria, ricordandoci del ragionamento appena fatto, sappiamo che le dimensioni delle code non possono superare N e si ha quindi un utilizzo di memoria pari a O(N).

MrBrionix · 24 Dicembre 2020, 5:10pm

Un po in ritardo, ma ecco la dimostrazione riguardo alla complessità computazionale del problema compleanno.

La programmazione dinamica proposta era la seguente:

f(x)= min_{0\leq i<9}(f(\lfloor {x/val[i]} \rfloor)+val[i]+1+(x\%a[i]))
dove val[9]=2,3,4,5,7,11,13,17,19

ora andiamo ad analizzare (e trovare) il numero di x diverse che verranno chiamate durante la ricorsione (ovvero il numero di stati della nostra soluzione).

Step 1

Dati N,a,b interi positivi vale:
\lfloor\frac{\lfloor\frac{N}{a}\rfloor}{b}\rfloor = \lfloor\frac{\lfloor\frac{N}{b}\rfloor}{a}\rfloor

Dimostrazione

sia Y=\lfloor\frac{N}{a}\rfloor, allora \exists y: 0\leq y<a \land Ya+y = N
sia X= \lfloor\frac{\lfloor\frac{N}{a}\rfloor}{b}\rfloor, allora \exists x : 0\leq x < b \land Xb+x = \lfloor\frac{N}{a}\rfloor = Y

ne consegue che
N = Ya+y = (Xb+x)a+y = abX+xa+y

dato che 0\leq x<b e 0\leq y<a, si ha che 0\leq xa+y\leq a(b-1)+a-1 = ab-1.
Quindi xa+y è il resto e X il quoziente della divisione di N/ab, ovvero X = \lfloor\frac{N}{ab}\rfloor.

Ne risulta che \lfloor\frac{\lfloor\frac{N}{a}\rfloor}{b}\rfloor=\lfloor\frac{\lfloor\frac{N}{b}\rfloor}{a}\rfloor=\lfloor\frac{N}{ab}\rfloor.
\square

Step 2

Durante la ricorsione vengono visitate tutte e sole le x per cui \exists a,b,c,d,e,f,g,h\geq 0 : \lfloor \frac{N}{2^a3^b5^c7^d11^e13^f17^g19^h}\rfloor=x

Dimostrazione

Per calcolare una certa f(x) si chiamano ricorsivamente i seguenti valori:
f(\lfloor \frac{x}{2}\rfloor),f(\lfloor \frac{x}{3}\rfloor),f(\lfloor \frac{x}{4}\rfloor),f(\lfloor \frac{x}{5}\rfloor),f(\lfloor \frac{x}{7}\rfloor)f(\lfloor \frac{x}{11}\rfloor),f(\lfloor \frac{x}{13}\rfloor),f(\lfloor \frac{x}{17}\rfloor),f(\lfloor \frac{x}{19}\rfloor)

quindi, dato l’input N del problema, verranno visitati tutti e soli gli stati x per cui:
\exists a_1,a_2,\dots,a_k \in \{2,3,4,5,7,11,13,17,19\} : \Biggr\lfloor \frac{\overset{\lfloor \frac{\lfloor \frac{N}{a_1} \rfloor}{a_2}\rfloor}{\vdots}}{a_k}\Biggr\rfloor= x

ma applicando la proprietà dimostrata nello step 1 per k-1 volte si ha che \Biggr\lfloor \frac{\overset{\lfloor \frac{\lfloor \frac{N}{a_1} \rfloor}{a_2}\rfloor}{\vdots}}{a_k}\Biggr\rfloor=\lfloor\frac{N}{a_1a_2\dots a_k}\rfloor e dato che a_1,a_2,\dots,a_k \in \{2,3,4,5,7,11,13,17,19\} allora \lfloor\frac{N}{a_1a_2\dots a_k}\rfloor è della forma \lfloor \frac{N}{2^a3^b5^c7^d11^e13^f17^g19^h}\rfloor, quindi gli x visitati sono tutti e soli quelli di questo tipo.
\square

Step 3

Considerando le assunzioni del problema (N\leq 10^{18}), il numero di stati visitati è al più 7039193.

Dimostrazione

Dallo step 2 possiamo dedurre che, fissato N, il numero di stati raggiunti è al massimo uguale al numero di interi della forma 2^a3^b5^c7^d11^e13^f17^g19^h che sono minori o uguali a N. (potrebbero essere anche di meno, poichè due numeri x e y con codesta forma potrebbero portare allo stesso valore \lfloor \frac{N}{x} \rfloor = \lfloor \frac{N}{y} \rfloor).
Questo bound sul numero di stati visitati è debolmente crescente all’aumentare di N, ne consegue che il caso con il bound peggiore (e il cui valore sarà pari al numero massimo di stati ottenibili per un N\leq 10^{18} qualsiasi) è proprio quello con N massimo, ovvero N=10^{18}.
Si consideri il seguente codice:

unsigned long long cont=0;
unordered_map<unsigned long long,bool> freq;
for(unsigned long long a=1;a<=n;a*=2ull){
	for(unsigned long long b=a;b<=n;b*=3ull){
		for(unsigned long long c=b;c<=n;c*=5ull){
			for(unsigned long long d=c;d<=n;d*=7ull){
				for(unsigned long long e=d;e<=n;e*=11ull){
					for(unsigned long long f=e;f<=n;f*=13ull){
						for(unsigned long long g=f;g<=n;g*=17ull){
							for(unsigned long long h=g;h<=n;h*=19ull){
								cont++;
								freq[n/h]=true;
								if(n/h<19)break; //controllo per l'overflow
							}
						}
					}
				}	
			}
		}
	}
}
cout<<cont<<"\n";
cout<<freq.size()<<"\n";

la variabile cont alla fine dell’esecuzione avrà valore pari a tutti i numeri della forma 2^a3^b5^c7^d11^e13^f17^g19^h minori o uguali a N (che sarebbe il nostro bound), mentre freq.size() avrà valore pari agli stati diversi visitati (ovvero tutti i valori ottenibili come \lfloor \frac{N}{2^a3^b5^c7^d11^e13^f17^g19^h}\rfloor).

Per N=10^{18} si ha cont = 7039193 quindi il numero di stati per qualunque altro N\leq 10^{18} è sempre minore o uguale a questo numero, in particolare per N=10^{18} (e presumibilmente anche per tutti gli altri input possibili) il numero esatto di stati visitati è molto minore (freq.size()=844958).
\square

In conclusione possiamo dire che questo approccio per il problema compleanno ha una complessità corretta per un time limit di 3 secondi.