Descriere_sol_IOI2018

DESCRIEREA SOLUȚIILOR IOI 2018
I.	PROBLEMA BENZINĂRII
	Observăm că o nouă stație de benzină va fi construită în mijlocul celei mai lungi secvențe situate între două stații de benzină consecutive (casa în mijloc, dacă secvența conține un număr impar de case sau prima dintre cele două din mijloc dacă secvența conține un număr par de case.
	Pentru a obține un algoritm în timp logaritmic, toate secvențele care au la un moment dat lungimea maximă trebuie procesate simultan.
	Observăm că pentru construirea oricărei stații de benzină pe o secvență de lungime maximă, valoarea S se va diminua cu aceeași valoare, astfel încât secvența succesivă de valori S obținută în timpul procesului de construcție a stațiilor de benzină pe secvențele cu lungimea respectivă va forma o progresie aritmetică. Este suficient să știm câte stații de benzină de fiecare tip există la un moment dat și câte stații de fiecare tip există după ce toate benzinăriile au fost construite pe secvențe cu lungimea maximă.
Prin utilizarea acestei proceduri de fiecare dată când începem să construim un nou set de stații de benzină, vor exista secvențe de cel mult 3 lungimi diferite.
De exemplu, dacă inițial avem N = 57, în timp vom obține următoarea evoluție:
1.	O secvență de lungime 57 se transformă în două secvențe de lungime 28.
2.	Cele două secvențe cu lungimile 28 se transformă în două secvențe de lungime 14 și două de lungime 13.
3.	Cele două secvențe ale lungimii 14 se transformă în două secvențe de lungime 7 și în două de lungime 6 => avem două de lungime 13, două de 7 și două de 6
4.	Cele două secvențe de lungime 13 se transformă în 4 de lungime 6 => avem două din 7 și 6 din 6
5.	Cele două din 7 se transformă în 4 din 3 => avem 6 din 6, 4 din 3
6.	6 din 6 se transformă  în 6 din 3 si 6 din 2 => avem 10 din 3, 6 din 2
7.	10 din 3 transforma în 20 din 1 => avem 6 din 2 și 20 din 1
8.	6 din 2 se transformă în 6 din 1 => avem 26 din 1
9.	Cele 26 de stații de benzină sunt construite și întregul proces este terminat.

II.	PROBLEMA OPȚIUNI

	O primă soluție este calculul valorii D [i] [j] = minimul numărul de pași pentru atingerea poziției i, j. Recurența este D [i] [j] = D [i-1] [j-1] + D [i-1] [j-1] + D [i + 1] [j-1]. Restricția pentru numărul de coloane nu permite ca această soluție să funcționeze în timpul necesar (ca memorie, pot fi utilizate numai ultimele 2 coloane, deci se pot folosi  doi vectori). Având matricea periodică cu L
rânduri și coloane K, vom avea următorul pre-calcul:
	D [p][i] [j] = numărul minim de pași pentru îmbinarea matricelor 2^p și pentru a porni de la rândul i și coloana 1 din primul rând matricile p și pentru a ajunge la rândul j și coloana k din
ultimul. Pentru calcularea valorilor D [p][j] [j] folosim valorile D [p-1] [i] [] și D [p-1] [] [j], considerând că din ultima coloană din D [p-1] [i] [] trecem pe prima dintre D [p-1] [] [j].
	După calcularea valorilor D, vom determina mai întâi M ca fiind cel mai mare multiplu K mai mic sau egal cu C si vom folosi valorile D [bit] [] [], în care bitul reprezintă pozițiile unui bit de 1 în scrisul lui M în baza 2. Pentru zona formată din coloanele de la M + 1 la C, putem scrie dinamica primei soluții.

III.	PROBLEMA KST

Notăm d[n][k] = numărul de variante în care, având un interval de n valori consecutive, le plasăm pe k din acestea în rădăcina unui arbore, iar restul n-k în sub-arborul determinat de k + 2 sub-arbori KST determinați de valorile fixate.
Observații:

1. Soluția problemei este d[N][K] unde N și K sunt valorile citite.
2. Dacă n> K și k = 0 înseamnă că, într-adevăr, se află într-un sub-arbore pe care tocmai am început să-l construim. Primul lucru pe care trebuie să-l fac este să pun K din valorile n în rădăcina sub-arborelui. Apoi, d[n][0]=d [n][K]
3. Dacă n <k avem prea puține valori pentru a finaliza valorile k care sunt încă necesare în rădăcină, deci vom lua d[n][k]=0;
4. Dacă n <K și n=k atunci vom folosi toate valorile n pentru completarea rădăcină, deci vom lua d[n][k]=1
5. Dacă n <K și k = 0 înseamnă că tocmai am început să construim un nou KST sub-arbore cu noduri mai mici decât K, deci nu putem construi mai mult decât o frunză, deci vom lua            d[n][k]=1
Observațiile tratează toate cazurile particulare în care putem spune direct cât trebuie să fie d[n][k].
Cazul care rămâne este cel în care n> k și k> 0.
Considerăm dou subcazuri:
1. Cazul în care k este impar
	Fixăm una dintre valorile n ea fiind valoarea medie dintre valorile k care trebuie plasate în rădăcină. Vor rămâne i valori mai mici și j valori mai mari decât cea aleasă și i + j = n-1. Trebuie să alegem valorile k /2 din primele i pentru valorile rădăcinii și k / 2 din ultimele j pentru rădăcină. Se obțin d [n] [k] = suma pentru i + j = n-1 din d [i] [k/2]* d [j] [k/2]
2. Cazul în care k este par:
	Vom fi9xa una dintre cele n valorile ca fiind cea mai mică dintre valorile k pe care le punem în rădăcină. Rămân i valori mai mici, din care nu trebuie să punem pe niciuna în rădăcină și j mai mari, din care trebuie să punem k-1 în rădăcină. Vom obținem:
d[n][k] = sumă pentru i+j=n-1 din d[i][0]*d[i][k-1]



	Pentru fiecare k și n fixate, dinamica are complexitatea O (n). Dar n ia toate valorile de la 1 la N, deci un alt O (N). De la un k impar, trecem la k/2 și pentru un k par trecem la k-1 care este impar, de aceea vom trece la (k-1)/2. Rezultă că numărul valorilor k pe care le trecem este O (log K). Complexitatea finală va fi O (N * N * log K).
	Dinamica funcționează bine cu memoizarea, care tratează separat cazurile particulare ale lui n și k și face apel la valorile necesare pentru cazul general în dinamică. Memoria necesară ar fi O (N log K), dar pentru simplificarea implementării, putem declara matricea dinamic d [1001] [1001] din care vom folosi rândurile N și coloanele log K.

IV.	PROBLEMA SUSJOS

	Pentru a găsi secvența ordonată crescător de lungime maximă după prima componentă și ordonată descrescător după a doua componentă, vom sorta secvența într-o ordine crescătoare după prima componentă, apoi vom folosi algoritmul pentru generarea celei mai lungi sub-secvențe descrescătoare, după a doua componentă. Sortarea poate fi făcută cu complexități O (n) sau O (nlogn), cea mai lungă secvență crescătoare fiind obținută cu complexitatea O (n logn) sau O (n ^ 2). În concluzie, complexitatea soluției este O (n ^ 2) pentru 75 de puncte și O (nlogn) pentru 100 de puncte.

V.	PROBLEMA FLORI

	Facem 2 DFS pentru fiecare dintre literele alfabetului.
	În primul rând, vom calcula costul minim pentru fiecare sub-arbore al arborelui, astfel încât dacă un nod este inclus, toți descendenții săi sunt incluși.
	În al doilea rând, folosind valorile din primul DFS, vom calcula costul minim, luând în considerare fiecare dintre noduri ca locație pe care o vom reuni. Formal, atunci când calculăm valoarea pentru un nod x, va trebui să luăm în considerare valorile calculate pentru fiecare nod care nu este descendent al nodului x și, de asemenea, suma cantităților. În concluzie, soluția minimă pentru un nod x este suma soluției pentru fiecare nod care nu este descendent al nodului x + valoarea lui dp[x].

VI.	PROBLEMA MAP

	Considerăm graful asociat hărții, în care vârfurile reprezintă țări. Există o margine între două țări dacă sunt vecini. Gradul maxim al unui vârf din acest grafic nu poate fi mai mare de 8.
	Observăm că un vârf cu o valoare mai mică de 4 poate fi întotdeauna pictat indiferent de culorile vecinilor săi. În consecință, vom folosi următorul algoritm.
Toate nodurile cu un grad mai mic de 4 sunt introduse într-o stivă de așteptare și vor fi șterse din grafic. Astfel, gradele altor noduri vor scădea, iar noi noduri vor apărea cu un grad sub 4, pe care le vom introduce în teancul în ordinea apariției lor. Această procedură, aplicată în mod repetat, va elimina toate vârfurile grafului.
În cele din urmă, vârfurile introduse în stivă vor fi colorate într-o culoare care nu a existat până în acel moment între culorile vecinilor. Această metodă seamănă cu o sortare topologică.
Complexitatea algoritmului este O (m * n).