Intersect

Cea mai importanta observatie ce ajuta la rezolvarea acestei probleme este ca avand i drepte deja desenate si adaugand o dreapta noua neparalela cu nici una din cele i dinainte se vor forma i intersectii noi si i + 1 zone noi in care este impartita foaia. In continuare daca avem i drepte deja desenate si adaugam k drepte noi paralele intre ele dar neparalele cu nici una din cele i drepte deja desenate se vor forma i * k intersectii noi, si (i + 1) * k zone noi in care este impartita foaia. Asadar problema se poate rezolva prin progamare dinamica. Fie din [ i ] [ j ] numarul maxim de zone in care poate fi impartita foaia astfel incat sa fi desenat i drepte ce se intersecteaza in j puncte, sau 0 in caz ca i drepte nu pot forma j intersectii. Valoarea initiala a aceste dinamici va fi din [ 0 ][ 0 ] = 1 . Vom porni de la dimensiunile mai mici ale dinamicii ( adica vom parcurge starile dinamicii in ordine crescatoare dupa i si apoi j ) . Daca suntem in starea din [ i ] [ j ] < > 0 , vom incerca sa desenam k noi drepte paralele intre ele dar neparalele cu nici una din cele i deja desenate si vom actualiza din [ i + k ] [ j + ( i * k ) ] = maxim ( din[ i + k ][ j + ( i * k ) ], din[ i ] [ j ] + (i + 1) * k ) .
O alta observatie utila ar fi ca numarul maxim de zone in care poate fi impartit planul de i drepte ce formeaza j intersectii este unic determinat de i si j si este egal cu i + j + 1 . Ajutandu-ne de aceasta observatie trebuie doar sa stim daca i drepte pot forma j intersectii si putem schimba dinamica in din[i][j] este 1 sau 0 daca i drepte se pot intersecta in j puncte, si astfel putem reduce memoria folosind stari pe biti. Acest lucru nu era necesar pentru a obtine punctaj maxim.
Solutia aceasta are complexitatea N^3 .

Soluţie alternativă
Având în vedere că numărul maxim de zone în care poate fi împărţit planul de i drepte ce formează j intersecţii este unic determinat, pentru a afla o anumită configuraţie (i, j) este necesar să calculăm maxim i configuraţii. Astfel, vom calcula doar configuraţiile necesare, folosind memoizarea. Această soluţie are complexitatea O(T*N)