h1. Solutii FMI No Stress 9 Warmup

h1. Solutii FMI No Stress 9

h2. "Nane":https://infoarena.ro/problema/nane

h2. "Freakadebunic":https://infoarena.ro/problema/freakadebunic

Problema aceasta se rezolva folosind "sliding window". Ce presupune rezolvarea: vom tine doi pointeri st si dr. Vom deterina la fiecare pas, cate secvente sunt valide si se termina cu pozitia dr. Daca secventa i - j cu i<j este valida, si secventa i+1 - j  datorita naturii operatiei OR. Va trebui sa aflam pentru fiecare pozitie t2, cea mai mica pozitie t1 pentru care secventa este valida; lungimea acestei secvente va fi t2-t1+1 si vom avea t2-t1+1 secvente valide practic. Revenind la st si dr; cand incrementam dr cu o unitate, suma OR de la st la dr va ramane la fel sau va creste, in consecinta va trebui sa incermentam si st pana cand suma OR de la st la dr va avea mai putin de K biti de 1. Putem face acest lucru optim folosind un vector de aparitii a bitilor. Cand incrementam dr, vom incrementa si in vectorul de aparitii fiecare bit de 1 al elementului de pe pozitia dr, iar cand vrem sa incrementam st, vom decrementa fiecare bit al elementului de pe pozitia st. Complexitate O(N*K)

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 in O(N^3); pentru 60p se va face LCA-ul cu RMQ in complexitate finala O(N^2 * logN). 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.