Lista de probleme 3

RAU-Gigel își serbează ziua alături de colegii săi de la clubul de informatică și vrea să le împartă bomboane. El are un număr dat de bomboane și ar vrea să știe dacă îi ajung și, dacă da, în câte moduri le poate împărți. Dar nu își amintește câți colegi are la cerc, are însă o informație care ar putea să îl ajute.

În urma petrecerii de ziua lui RAU-Gigel, copiii au primit atâtea bomboane încât au câștigat o energie debordantă – așa că l-au provocat pe RAU-Gigel la un concurs de … numărat!

Acestora li se dă o matrice cu N linii și M coloane, în care fiecare element este un număr natural nenul. Obiectivul lor este să determine câte submatrice (sub-dreptunghiuri formate din linii și coloane contigue) conțin exact K valori distincte.

RAU-Gigel și Praștie împodobeau bradul de Crăciun și s-au gândit că ar merge niște colinde. Căutând, au dat de cuvântul “carol”, care evident le-a amintit de orele de informatică. Cu asta și copacul din fața lor în minte, s-au gândit la următoarea problemă, pe care vă roagă să o rezolvați.

Se dă un arbore cu N noduri înrădăcinat în 1 și un șir A de lungime M , cu 1≤A[i]≤N. Definim nivelul unui nod ca fiind distanța față de rădăcină și strămoșul unui nod x ca fiind oricare nod y de pe drumul de la x la rădăcină. De asemenea, lca(V), unde V este un șir, reprezintă nodul de nivel maxim care este strămoș pentru toate nodurile din șirul V. Să se calculeze sumă după lca(V), unde V este fiecare subsecvență a șirului A.