bq. Deci contribuţia problemei ăsteia la concurs a fost o coloană de $0$ adaugată în clasament?
Deşi problema pare să ceară fie o dinamică, fie un back optimizat până ajungi să dispreţuiesti autorul ca entitate prezentă pe Pământ, soluţia e de fapt destul de mişto. În general, problemele de colorare în sine sunt NP-complete, i.e se 'presupune':http://en.wikipedia.org/wiki/P_%3D_NP_problem ca nu admit soluţie în timp polinomial. Nu prea bag mâna în foc că acest caz particular este de asemenea NP, însă presupun că cel puţin problema de numărare a colorărilor este. (Dacă mă contraziceţi, aş fi chiar entuziasmat *:D*).
Deşi problema pare să ceară fie o dinamică, fie un back optimizat până ajungi să dispreţuiesti autorul ca entitate prezentă pe Pământ, soluţia e de fapt destul de mişto. În general, problemele de colorare în sine sunt NP-complete, i.e se 'presupune':http://en.wikipedia.org/wiki/P_%3D_NP_problem ca nu admit soluţie în timp polinomial. Nu prea bag mâna în foc că acest caz particular este de asemenea NP-Complete^*^, însă presupun că cel puţin problema de numărare a colorărilor este. (Dacă mă contraziceţi, aş fi chiar entuziasmat *:D*).
Să rezolvăm o variantă mai simplă a problemei. Să presupunem că nu există două caractere $?$ alăturate. Astfel, culoarea unui anumit semn de întrebare nu afecteaza colorarea altui semn de întrebare. Putem deci răspunde cu o formula.
$ANS = p1 * p2 * p3 * ... pk$ unde $pi$ este numărul de posibilităţi de a colora al $i-lea$ semn de întrebare.
Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate căsuţele albe au doar vecini negri iar căsuţele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare $?$ de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare $?$ numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că $K$, numărul de $?$, este mai mic sau egal cu $18$, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât $9$, fie cel de semne de întrebare negre este mai mic sau egal decat $9$. Obţinem astfel o complexitate de timp $O(5 ^ (K / 2) * K)$.
Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate celulele albe au doar vecini negri iar celulele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare $?$ de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare $?$ numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că $K$, numărul de $?$, este mai mic sau egal cu $18$, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât $9$, fie cel de semne de întrebare negre este mai mic sau egal decat $9$. Obţinem astfel o complexitate de timp $O(5 ^ (K / 2) * K)$.
h2. 'Triangles':problema/triangles
