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 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).

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).

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.