Diferente pentru algoritmiada-2010/runda-3/solutii/intersect intre reviziile #15 si #25

Nu exista diferente intre titluri.

Diferente intre continut:

 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)] = max(din[i + k][j + (i * k)], din[i][j] + (i + 1) * k) .
h1(#Intersect). 'Intersect':problema/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 .

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.