1. http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en
Reducerea complexitatii, transformarea problemei intr-una de construire a unui arbore binar.

2. http://code.google.com/codejam/contest/dashboard?c=32001#s=p0&a=3

2. http://code.google.com/codejam/contest/dashboard?c=32001#s=p0&a=3 (Boolean tree, programare dinamica simpla pe arbore binar.

3. http://code.google.com/codejam/contest/dashboard?c=32001#s=p3&a=3

3. http://code.google.com/codejam/contest/dashboard?c=32001#s=p3&a=3 (PermRLE, permutari cu N*2^N)

4. http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1

4. http://code.google.com/codejam/contest/dashboard?c=32010#s=p3&a=3 (problema cu DP pe matrici, aplicam ridicarea la putere pt calcul rapid)

 
5. http://code.google.com/codejam/contest/dashboard?c=32010#s=p3&a=3

5. http://infoarena.ro/problema/doipatru (joc cu solutie DP, stare in 6 dimensiuni)

h2. Sugestii Silviu

Observăm că un număr este urât dacă dă cel puţin o dată restul 0 la împărţirea la numerele 2, 3, 5, 7. O abordare a problemei este parcurgerea tuturor variantelor de inserare şi calcularea celor 4 resturi, verificând dacă cel puţin unul este 0.
Vom folosi aritmetica modulară pentru a obţine o soluţie mai eficientă a problemei. Vom împărţi cele 3^N-1^ variante în clase, fiecare clasă reprezentând toate numerele care dau resturile $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$ la împărţirea la cele 4 numere. Calculând pentru fiecare clasă numărul de numere generate, rezultatul final va fi suma valorilor calculate pentru toate clasele pentru care cel puţin un rest este egal cu 0. Intuim că putem utiliza clasele de resturi într-o soluţie cu programare dinamică.

Vom utiliza şirul auxiliar $V[i][j]$ reprezentând numărul format prin concatenarea cifrelor de pe poziţiile consecutive $i, i+1, ..., j$ din şirul dat, fără inserarea unor semne între cifre. De exemplu, @V[2][4] = 234@. Dacă notăm cu $C[i][r{~2~}][r{~3~}][r{~5~}][r{~7~}]$ numărul de variante formate cu primele *i* cifre pentru care clasa de resturi este $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$. Observăm că orice astfel de variantă se obţine dintr-o variantă cu $j < i$ cifre după care adăugam + sau - apoi concatenăm restul cifrelor până la *i* fără semne. Dacă resturile pentru varianta cu *j* cifre erau $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$ atunci resturile pentru varianta nouă sunt:
<tex> $(r_2', r_3', r_5', r_7') = ((r_2 +/- V[j+1][i])\% 2, (r_3 +/- V[j+1][i])\% 3, (r_5 +/- V[j+1][i])\% 5, (r_7 +/- V[j+1][i])\% 7)$</tex>.

Vom utiliza şirul auxiliar $V[i][j]$ reprezentând numărul format prin concatenarea cifrelor de pe poziţiile consecutive $i, i+1, ..., j$ din şirul dat, fără inserarea unor semne între cifre. De exemplu, @V[2][4] = 234@. Dacă notăm cu $C[i][r{~2~}][r{~3~}][r{~5~}][r{~7~}]$ numărul de variante formate cu primele *i* cifre pentru care clasa de resturi este $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$. Observăm că orice astfel de variantă se obţine dintr-o variantă cu $j < i$ cifre după care adăugam + sau - apoi concatenăm restul cifrelor până la *i* fără semne. Dacă resturile pentru varianta cu *j* cifre erau $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$ atunci resturile pentru varianta nouă $(r'{~2~}, r'{~3~}, r'{~5~}, r'{~7~})$ sunt:
<tex> $r_2' = (r_2 +/- V[j+1][i])\% 2% 2)$</tex>
<tex> $r_3' = (r_3 +/- V[j+1][i])\% 2% 3)$</tex>
<tex> $r_5' = (r_5 +/- V[j+1][i])\% 2% 5)$</tex>
<tex> $r_7' = (r_6 +/- V[j+1][i])\% 2% 7)$</tex>

Atunci numărul total de variante cu *i* cifre este suma după toate valorile *j* ale numerelor de variante cu *j* cifre:
<tex> $C[i][r_2'][r_3'][r_5'][r_7'] = \sum_{j<i} C[j][r_2][r_3][r_5][r_7]$ </tex>

                        C[i][r_2][r_3][r_5][r_7] = 0;
                        pentru j = 0, i - 1 execută
                            C[i][r_2][r_3][r_5][r_7] += C[j][(r_2 + 2 - V[j+1][i])%2)][(r_3 + 3 - V[j+1][i])%3)]

                                                                             [(r_5 + 5 - V[j+1][i])%5)][(r_7 + 7 - V[j+1][i])%7)];

                                                            [(r_5 + 5 - V[j+1][i])%5)][(r_7 + 7 - V[j+1][i])%7)];

                            C[i][r_2][r_3][r_5][r_7] += C[j][(r_2 + V[j+1][i])%2)][(r_3 + V[j+1][i])%3)]

                                                                             [(r_5 + V[j+1][i])%5)][(r_7 + V[j+1][i])%7)];

                                                            [(r_5 + V[j+1][i])%5)][(r_7 + V[j+1][i])%7)];

                        sfârşit pentru;
                        dacă i == N şi (r_2 == 0 sau r_3 == 0 sau r_5 == 0 sau r_7 == 0)

    returnează S;
==

O problemă în abordarea precedentă este calcularea matricii V, ale cărei valori devin foarte mari şi ies din precizia tipurilor de date disponibile. O soluţie posibilă este calcularea câte unei matrici de sume modulo R pentru fiecare rest R, adica a 4 matrici V_2, V_3, V_5 si V_7 ale resturilor împărţirii valorilor lui V la cele 4 numere prime. Folosind aritmetica modulară, aceste matrici pot fi calculate direct, fără a calcula V. Altă variantă este utilizarea teoremei chineze a resturilor, prin care un sistem de ecuaţii modulo câteva numere prime între ele poate fi redus la o ecuaţie modulo produsul numerelor date. În cazul nostru, numerele sunt prime, deci putem aplica teorema. Astfel, putem reduce problema resturilor împărţirii la (2, 3, 5, 7) la problema restului împărţirii la 2*3*5*7=210, deci fiecare clasa (r_2, r_3, r_5, r_7) se reduce la un rest R < 210. Modificăm pseudocodul astfel:

O problemă în abordarea precedentă este calcularea matricii $V$, ale cărei valori devin foarte mari şi ies din precizia tipurilor de date disponibile. O soluţie posibilă este calcularea câte unei matrici de sume modulo $R$ pentru fiecare rest $R$, adica a 4 matrici $V{~2~}$, $V{~3~}$, $V{~5~}$ si $V{~7~}$ ale resturilor împărţirii valorilor lui $V$ la cele 4 numere prime. Folosind aritmetica modulară, aceste matrici pot fi calculate direct, fără a calcula $V$. Altă variantă este utilizarea teoremei chineze a resturilor, prin care un sistem de ecuaţii modulo câteva numere prime între ele poate fi redus la o ecuaţie modulo produsul numerelor date. În cazul nostru, numerele sunt prime, deci putem aplica teorema. Astfel, putem reduce problema resturilor împărţirii la $(2, 3, 5, 7)$ la problema restului împărţirii la $2*3*5*7=210$, deci fiecare clasa $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$ se reduce la un rest $R < 210$. Modificăm pseudocodul astfel:

== code(cpp)    |
    pentru i = 1, N execută