Solutii .com 2009, Runda 2

• Lista de probleme
• Intensitate
• NrDivUnique
• Harta3

Intensitate

Observaţia esenţială în rezolvarea problemei este faptul că nu ne interesează becurile legate în serie, trebuind să lucrăm doar asupra celor care sunt start/finish pentru o componentă în paralel. Astfel, becurile în serie se puteau elimina, menţinând un nr[ i ] = numărul becurilor legate în serie ce pot fi eliminate care precedă nodul i

Pentru 30p se putea folosi o abordare de tip backtracking, 0 dacă va trece curent electric printr-un nod sau 1 altfel. Intensitatea minimă maximă se calcula apoi cu ajutorul unui df. Punctajul putea fi obţinut cu optimizări minore.

În cazul soluţiilor ce aduc un scor mai mare, va trebui să reţinem pentru fiecare nod i o valoare next[ i ]. Astfel, pentru definiţia din enunţul problemei a unei componente în paralel, next[ A ] = B.

Vom ţine o dinamică c[ i ][ j ] = intensitatea minimă maximă pentru a aprinde j becuri între i şi next[ i ]. Pentru un nod fixat i vom calcula cele 2^x posibilităţi de a alege ramurile pe care vom aprinde becuri.

• Pentru teste în valoare de 50p vom căuta binar pentru nodul respectiv intensitatea minimă maximă de a reporni j becuri. Din fiecare ramură aleasă în configuraţia stabilită vom alege în O(logK) numărul maxim de becuri astfel încât soluţia să se încadreze în valoarea stabilită.

• În caz de 70p vom menţine A[ i ] = intensitatea minimă maximă pentru a aprinde i becuri dacă vom alege becuri doar de pe ramurile fixate. A-ul îl vom calcula cu un algoritm knapsack.

Pentru 100p observăm că nu ne interesează efectiv ramurile de pe care vom considera becuri în calculul dinamicii c. Astfel, vom putea extinde vectorul A din soluţia de 70p la o matrice bidimensională, A[ i ][ j ] = intensitatea minimă maximă pentru a reporni j becuri pe i ramuri. Această matrice o vom calcula tot asemănător problemei rucsacului.

Răspunsul va fi determinat de valorile 1 şi c[ 1 ][ k ].

Deşi complexitatea teoretică a acestei soluţii este O(N⁵), în practică se comportă mult mai bine, algoritmul rulând pe fiecare test in mai puţin de 0.1s.

NrDivUnique

Se rezolvă fiecare serie de intervale în parte. Pentru fiecare interval i, dacă B_i >= 2*A_i, se observă uşor că intervalul are exact B_i divizori. Pentru situaţia în care B_i < 2*A_i, se verifică fiecare număr j din intervalul [1,sqrt(B_i)] dacă este divizor al vre­unui număr din intervalul [A_i,B_i]. Pentru a verifica dacă un număr j este divizor al intervalului, calculăm x=A_i/j+1 (valoarea minimă x cu care se poate înmulţi j astfel încât x*j>=A_i) şi y=B_i/j (valoarea maximă y cu care se poate înmulţi j astfel încât y*j<=B_i). De asemenea, trebuie avut grijă, ca atunci când A_i îl divide pe j, să decrementăm pe x cu 1. Dacă x<=y, atunci j şi toate numerele din intervalul [x,y] sunt divizori al intervalului [A_i,B_i]. Desigur, trebuie acordată mare atenţie numerelor din toate intervalele [x,y] astfel încât să nu contorizăm o valoare de mai multe ori.
Complexitate: O(N*sqrt(B))

Harta3

Observăm că relaţiile între puncte ne determină componente conexe de noduri ce au distantă fixă între ele. De asemenea, aceste componente se pot pune consecutiv pe axa Ox fără a ieşi din intervalul [-1 000 000, 1 000 000]. Astfel, avem trei cazuri:

• A şi B nu fac parte din nicio componentă, în această situaţie răspunsul este 1. Vom considera A de coordonate -1 000 000 şi B de coordonate -999 999. Restul componentelor îl vom pune consecutiv imediat după B.

• A şi B fac parte din aceeaşi componentă. Distanţa dintre A şi B este fixă în acest caz, şi vom amplasa restul componenteleor conescutiv în intervalul de soluţie.

• A şi B fac parte din componente diferite. În acest caz, ne vom fixa distanţa dintre A şi B, şi vom verifica în O(N) daca putem alatura componenta lui A de componenta lui B fără să se suprapună. Soluţia va fi determinata de cea mai mică distanţă valida. Ca şi în cazurile precendente, componentele rămase se pot pune consecutiv in intervalul de solţie fără a se intersecta.

Complexitatea este deci O(raspuns * N), unde prin raspuns ne referim la distanţa minimă dintre A şi B.