Solutii FMI No Stress 9

Freakadebunic

Pentru problema aceasta se puteau obtine 2 punctaje partiale: pentru 30p se ia fiecare pereche de noduri alese de Paula si pentru acestea se caulta LCA-ul (cel mai apropiat stramos comun) intr-un mod brut, urcand pe nivele; pentru 60p se va face LCA-ul cu RMQ. Solutia de 100 se bazeaza pe observatia: un nod este un LCA a 2 noduri marcate de Paula, daca acestea se afla in subarbori a 2 fii diferiti (+ cazul cand nodul actual este marcat de Paula; pentru a fi marcat si de Bunic, e necesar ca un singur subarbore al unui fiu sa contina nod marcat de Paula). Complexitatea este O(N), putand calcula pentru fiecare nod cati subarbori ai fiilor au noduri marcate de Paula printr-un DFS. 

Hagi

Prima observatie este faptul ca distribuirea golurilor nu este legata de distribuirea asisturilor. Problema ne cere practic numarul de partitionari diferite ale golurilor, respectia ale asisturilor, iar raspunsul este produsul acestor 2 partitionari. Daca vrem sa distribuim N goluri la K echipe, vom avea combinari de N+K-1 luate cate K-1 (aceeasi logica pentru asisturi). Mai multe detalii pentru aceasta formula puteti citi aici: stars and bars combinatorics(combinatorics)