h2. "PS":https://www.infoarena.ro/problema/ps

Problema se poate modela ca un graf bipartit in care cele doua multimi de noduri sunt reprezentate de elevi, respectiv de probleme, iar aparententa in tema sunt muchiile. Ce ramane de facut este sa vedem daca gasim o multime de muchii astfel incat toate nodurile apar o singur data. Daca o putem gasi, atunci aceasta este solutia in care un elev rezolva o singura tema. Altfel, putem afisa orice solutie simpla in care asociem problemele oricarui elev, caz in care un elev va rezolva $2$ probleme. O particularitate al grafului creat este ca gradul fiecarui nod este cel mult $2$. Partea de cuplaj poate fi rezolvata cu algoritmi clasici de cuplaj maxim in graf bipartit si se poate demonstra ca vor gasi solutia in timp $O(N)$. Totusi, aceasta parte se poate rezolva si mai simplu. Este clar ca putem include muchiile asociate unui nod de grad $1$ in multimea de cuplaj. Le alegem pe acestea si apoi le scoatem din graf. Este clar ca acest proces poate crea si alte noduri de grad $1$. Vom continua sa le adaugam in cuplaj. Cand se termina aceasta procedura, este clar ca toate nodurile ramase au grad $2$. Rezolvam pe rand aceste componente conexe. Acest tip de graf admite un cuplaj perfect trivial si il putem reduce la prima problema daca ne fixam o muchie pe care o adaugam in cuplaj.

Problema se poate modela ca un graf bipartit in care cele doua multimi de noduri sunt reprezentate de elevi, respectiv de probleme, iar aparententa in tema sunt muchiile. Ce ramane de facut este sa vedem daca gasim o multime de muchii astfel incat toate nodurile apar o singur data. Daca o putem gasi, atunci aceasta este solutia in care un elev rezolva o singura tema. Altfel, putem afisa orice solutie simpla in care asociem problemele oricarui elev, caz in care un elev va rezolva $2$ probleme. O particularitate al grafului creat este ca gradul fiecarui nod este cel mult $2$. Partea de cuplaj poate fi rezolvata cu algoritmi clasici de cuplaj maxim in graf bipartit si se poate demonstra ca vor gasi solutia in timp $O(N)$. Totusi, aceasta parte se poate rezolva si mai simplu. Este clar ca putem include muchiile asociate unui nod de grad $1$ in multimea de cuplaj. Le alegem pe acestea si apoi le scoatem din graf. Este clar ca acest proces poate crea si alte noduri de grad $1$. Vom continua sa le adaugam in cuplaj. Cand se termina aceasta procedura, este clar ca toate nodurile ramase au grad $2$. Rezolvam pe rand aceste componente conexe. Acest tip de graf admite un cuplaj perfect trivial si il putem reduce la prima problema daca ne fixam o muchie pe care o adaugam in cuplaj.
 
h2. "Pudge":https://www.infoarena.ro/problema/pudge
 
Putem observa ca Pudge cu cat arunca hook-ul mai in stanga de pozitia lui, timpul in care hook-ul ajunge pe axa Ox creste, deci inamicii se vor deplasa mereu mai spre dreapta decat erau inainte. Astfel, observam ca un inamic fixat intra in raza hook-ului la un punct (X1, 0) in care Pudge poate arunca hook-ul si iese din raza hook-ului la un punct (X2, 0), X2 <= X1, deci doar in intervalul [X2 + 1, X1] acest inamic va fi in raza hook-ului. Daca Pudge se afla in punctul (X, Y) si arunca hook-ul in punctul (X0, 0), timpul hook-ului sa ajunga pe axa Ox este sqrt((X-X0) * (X-X0) + Y * Y), iar singurul termen care variaza din aceasta formula este X0. Astfel, pentru fiecare inamic vom cauta binar punctul X0 in care acesta intra in raza hook-ului si punctul X0 in care acesta iese din raza hook-ului, si vom creea un vector de evenimente de tipul (X, tip): daca tip e 1 inseamna ca de la pozitia X un inamic intra in raza hook-ului, iar daca tip e -1 inseamna ca de la pozitia X un inamic iese din raza hook-ului. Parcurgem acest vector de evenimente si vom sti la fiecare pas cati inamici prinde Pudge daca arunca hook-ul in punctul respectiv prin adunarea variabilelor "tip" din vector, iar raspunsul este maximul acestor valori.
(Atentie la cautarea binara deoarece pot exista erori de precizie din cauza radicalului, acestea pot fi rezolvate prin izolarea radicalului si ridicarea la patrat a inegalitatii pentru a scapa de acesta, sau putem lua un epsilon foarte mic pentru a verifica egalitatile)