Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2020-03-20 13:08:20.
Revizia anterioară   Revizia următoare  

Solutii FMI No Stress 9 Warmup

Nane

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)

Asi

Observam usor ca numerele cautate sunt puteri de numere prime mai mici decat 10 la puterea a 6-a (de aici restrictia ca puterea sa fie cel putin 2). Vom folosi ciurul lui Eratostene pentru a determina aceste numere prime. Pentru fiecare numar prim, vom calcula puterile sale cu valoare mai mica decat 1012 (observam ca vom avea putine numere intrucat, cu cat creste valoarea numarului prim, cu atat scade puterea sa astfel incat sa fie mai mica decat 1012 ). Dupa ce am introdus toate aceste puteri intr-un vector, il vom sorta. Pentru a raspunde la query-uri, observam ca numarul elementelor valide mai mici sau egale decat B minus numarul elementelor valide mai mici decat A ne ofera numarul elementelor valide intre A si B; vom folosi cautare binara pentru aceste 2 pozitii in vectorul creat anterior, iar raspunsul va fi dat de diferenta dintre cele 2 pozitii.

Logik

Problema ne cere sa verificam pentru fiecare bit i daca exista o valoare a unei subsecvente valide care are 0 in bitul i, astfel facand operatia AND rezultatul va avea 0 pe bitul i.
Prima observatie care trebuie facuta este ca dupa ce faci AND cu valoarea unei subsecvente valide, nu mai este necesar sa faci AND cu alte subsecvente valide care o includ pe aceasta, deoarece nu se va schimba rezultatul.
Acest lucru se datoreaza faptului ca operatia OR nu schimba bitii de 1, eventual schimba biti de 0 in 1.
Acum, facand AND-ul tuturor numerelor pare (subsecventele de un element par sunt valide) va mai trebui sa verificam subsecventele valide care contin doar numere impare.
Cum toate subsecventele valide de numere impare contin cel putin o subsecventa valida de 2 numere impare, este de ajuns sa mai facem AND cu valoarea tuturor subsecventelor de 2 numere impare (2 numere impare consecutive).

Rusuoaica

In primul rand, putem sa vindem muchiile cu cost mai mare ca A pentru ca nu le vom folosi niciodata; daca vom avea nevoie de ele le putem cumpara cu cost fix A. Vom avea nevoie acum pentru fiecare componenta conexa formata cu muchiile ramase, de APM-ul sau. Dupa ce determinam APM-ul pentru fiecare componenta, la raspuns se va adauga (nr_comp_conexe - 1) * A pentru a le uni intr-un singur arbore. Putem implementa usor folosind paduri de multimi disjuncte si incercand muchiile pe rand in ordine sortata in functie de cost. Daca muchia va lega 2 componente conexe la un moment dat, o vom cumpara, altfel o vom vinde. La final putem determina cate muchii sa cumparam cu cost A, numarand cate radacini distincte avem in padurea de multimi disjuncte.

Vampir

In primul rand, trebuie sa observam ca punctele de pe zona sigura sunt la distanta manhattan egala cu L/2 fata de origine (|x|+|y|=L/2 pentru orice punct (x,y) din zona sigura) si acestea sunt toate punctele cu aceasta proprietate.
Pentru un K fixat, dispozitivul de teleportare te poate duce dintr-un punct (x1,y1) in orice punct (x2,y2) care e la distanta manhattan egala cu K fata de (x1,y1) si x1!=x2 si y1!=y2.
Dar, Daniel va alege mereu o teleportare cu cost minim, deci dintr-un punct (x1,y1) Daniel se va putea duce in orice punct (x2,y2), astfel incat |x1-x2|+|y1-y2|=K si B(|x1-x2|,|y1-y2|) este minim.
Deci trebuie sa gasim minimul lui B(i,j) cu i+j=K, i>=1 si j>=1. Pentru orice i si j alegem, numitorul fractiei este constant, deci trebuie sa le alegem astfel incat sa minimizam numaratorul fractiei.
Astfel, deoarece K este par, putem observa ca B(K/2,K/2) ne va da minimul functiei. Deci, Daniel se va putea teleporta dintr-un punct (x,y) in (x+K/2,y+K/2) sau (x-K/2,y+K/2) sau (x+K/2,y-K/2) sau (x-K/2,y-K/2).
Daca Daniel este intr-un punct (x,y) care e la distanta manhattan D fata de origine dupa o teleportare acesta va ajunge intr-un punct (x1,y1) care e la distanta manhattan D+K sau D-K fata de origine.
Cum Daniel pleaca din origine (care e la distanta manhattan 0) oricum ar folosi teleportarile acesta va ajunge intr-un punct (x,y) cu distanta manhattan fata de origine divizibla cu K.
Pentru a ajunge in zona sigura acesta trebuie sa ajunga la un punct cu distanta manhattan egala cu L/2, deci L/2 trebuie sa fie divizibil cu K => pentru prima cerinta trebuie sa afisam toti divizorii pari al lui L/2.
Daca L/2 este impar, nu va avea divizori pari, deci raspunsul va fi -1 pentru ambele cerinte.
De exemplu, pentru un K divizor par al lui L/2, un posibil drum este (0,0) -> (1*(K/2),1*(K/2)) -> (2*(K/2),2*(K/2)) -> .. -> ((L/2K)*(K/2),(L/2K)*(K/2)).
Pentru cerina 2 trebuie sa gasim drumul de cost minim dintre toti K gasiti la cerinta 1. Pentru un K fixat costul drumului minim este (L/2K)*B(K/2,K/2), daca notam functia asta cu B' observam ca este strict descrescatoare de la 2 pana la L/2, deci minimul functiei va fi cand K este maxim, respectiv L/2.
Raspunsul pentru cerinta 2 este B(L/4,L/4). (Se poate observa usor ca minimul este cand K este maxim deoarece factorialul de la numitor creste foarte repede).

Sunmihai

Acesta problema se rezolva cu metoda programarii dinamice. Vom calcula dp[i][j] - costul minim pentru a avea pe ultima piesa din domino valoarea din dreapta j, trecand prin primele i domino-uri date. Vom folosi notatia: v1[i] - valoarea din stanga a celui de-al i-lea domino dat initial si v2[i] - valoarea din dreapta. Dp1[v21] este 0 pentru ca nu aplicam nicio operatie primului domino, iar dp1[v11] este maxim A (v1[i] poate fi egal cu v2[i]), pentru ca intoarcem domino-ul; restul tabloului de dinamica il vom initializa cu o valoare mare. Ajunsi la a i-a piesa putem sa abordam in urmatorul fel: vrem sa o pastram exact cum e, iar dp[i][v2[i]] va fi dp[i-1][v1[i]]; vrem sa o intoarcem, iar dp[i][v1[i]] va fi dp[i-1][v2[i]] + A (atentie cand v1[i]=v2[i]), o scoatem cu cost B, iar dp[i][j] va fi egal cu dp[i-1][j] sau adaugam o piesa cu cost C. Piesa de tip C are sens sa fie adaugata doar cand vrem sa pastram a i-a piesa si nu avem anterior o piesa de care sa o legam, adica dp[i-1][v1[i] / v2[i]] este valoarea aceea mare cu care am initializat tabloul. Putand insera o piesa cu orice valori v1 si v2, nu ne intereseaza care sunt acestea si vom insera piesa dupa o configuratie dp[i-1][j], nu conteaza cine este j (de la 1 la 100), cu dp valoarea minima. Dp[i][v2[i]] va fi dp[i-1][j] (minim) + C. Raspunsul se va afla in min(dp[n][v1[i]], dp[n][v2[i]]).

Negot

Aceasta este o aplicatie de flux maxim, insa exista o solutie care se misca mai bine folosind cuplaj maxim in graf bipartit.
Pentru flux: vom crea un nod 0 sursa si vom crea N muchii de capacitate K. Toate muchiile de la producator la magazin au capacitate 1. Vom crea, de altfel, si un nod destinatie si M muchii de capacitate 1 de la magazine la destinatie.
Pentru cuplaj: putem "clona" un producator de K ori si fiecare clona sa o cuplam cu maxim 1 magazin. Restrictiile permit crearea efectiva a N*K noduri cu tot cu muchiile aferente, insa pentru o solutie performanta vom tine un vector de aparitii al fiecarui nod dintre cele N. Frecventa petru fiecare nod nu trebuie sa fie mai mare decat K in timp ce cuplam.