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. 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. 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]$.

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.