Diferente pentru
pd intre reviziile
#72 si
#71
Nu exista diferente intre titluri.
Diferente intre continut:
TODO:
1. Reparat link de la ugly numbers
2. Facut poza la Drilling
Plan de atac (probleme-candidat):
@inter[ i ][ j ]@ = <tex>\displaystyle\arg \max_{i \le k \le j}\{opt[i][k-1] \le opt[k+1][j]\} </tex>
Se observă că $inter[i][j]$ nu reprezintă altceva decât indicele $k$ tratat in paragraful precedent.
De asemenea, $inter$ poate fi calculată în $O(N^2)$ observând o proprietate simplă: <tex>$ inter[i][j-1] \le inter[i][j] \le inter[i+1][j] $</tex>. Aceasta reiese imediat din monotonia lui $opt$ discutată mai sus. Pseudocodul pentru calculul lui $inter$ este:
== code(cpp) |
Algoritmul este:
iniţializează opt, inter şi r
pentru len = 1, N execută
pentru i = 1, N - len + 1 execută
j = i + len - 1;
calculează opt[i][j]
pentru k = inter[i][j-1], inter[i+1][j] execută
dacă opt[i][k-1] <= opt[k+1][j] atunci
inter[i][j] = k;
sfârşit_pentru;
sfârşit_pentru;
sfârşit_pentru;
Sfârşit.
==
De menţionat că trebuie avut grijă la cazul când $len$ este mai mic ca $3$. Pseudocodul prezentat mai sus este orientativ.
Să vedem acum de ce această modalitate de calcul a lui $inter$ duce la o complexitate de $O(N^2)$.
Alternativ, se poate căuta binar $inter[i][j]$ pentru orice $[i,j]$.
De asemenea, $inter$ poate fi calculată în $O(N^2)$ observând o proprietate simplă: <tex>$ inter[i][j-1] \le inter[i][j] \le inter[i+1][j] $</tex>. Aceasta reiese imediat din monotonia lui $opt$ discutată mai sus. Alternativ, se poate căuta binar $inter[i][j]$ pentru orice $[i,j]$.
Acum vine ideea decisivă pentru a reduce complexitatea loop-ului: pentru a afla $opt[i][j]$, este suficient să aflăm minimul dintre 2 valori:
Astfel, am redus complexitatea loopului interior de la $O(N)$ la $O(logN)$.
h3(#problema-2). Problema 2: 'Ugly numbers':http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1 (Google Code Jam 2008, Round 1C)
bq. Un număr se numeşte *urât* dacă este divizibil prin oricare dintre numerele prime de o singură cifră, mai exact $2, 3, 5, 7$. Se dă un şir de $N$ cifre. Între fiecare 2 cifre consecutive se poate insera unul dintre semnele + sau -. Dacă nu se inserează un semn, cele 2 cifre sunt concatentate astfel încât să se obţină un număr. Pentru un şir dat de cifre si o variantă de a adăuga semne, prin evaluarea expresiei matematice obţinute prin inserarea semnelor se obţine un număr, numit numărul generat. Să se calculeze câte dintre cele $3^N-1^$ variante de a insera semnele generează numere urâte.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.