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.