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). Puteti gasi mai multe despre aceasta formula cautand pe un motor de cautare "stars and bars combinatorics".

h2. "Aliniere":https://infoarena.ro/problema/aliniere
 
Se observa ca, pentru a putea obtine un vector sortat in urma interschimbarii secventelor date, trebuie ca secventele in sine sa fie sortate. Deci trebuie sa eliminam de la inceput toate secventele nesortate. Precalculam vectorul st[i] = prima pozitie pos <= i care nu respecta proprietatea de vector sortat (v[pos] >= v[pos-1]), astfel: st[i] = st[i-1], daca v[i] >= v[i-1] sau i, altfel. Pentru fiecare secventa [a, b] verificam daca st[b] > a, caz in care eliminam secventa. Acum, pentru a putea obtine un vector sortat din secventele ramase, se observa ca intervalele date de capetele lor nu trebuie sa se intersecteze. Mai exact, secventa [a, b] se intersecteaza cu [c, d] daca intervalele (v[a], v[b]) si (v[c], v[d]) au cel putin un punct comun. Pentru a gasi numarul maxim de intervale care nu se intersecteaza se aplica problema spectacolelor. Atentie, insa, la cazul in care o secventa este formata dintr-un singur element, deoarece vectorul trebuie sortat crescator si NU strict crescator (cand sortam dupa capatul dreapta, in caz de egalitate trebuie sa sortam dupa capatul stanga).
Pentru 30 de puncte se pot incerca toate modurile de a pastra secvente cu backtracking.
Pentru 60 de puncte putem testa daca secventele sunt crescatoare in O(lungime secventa)
 

h2. "Pandemie":https://infoarena.ro/problema/pandemie
Pentru a obtine 100 de puncte este necesara o implementare in O(NlogN) sau log patrat bine implementata.

Rămâne acum să vedem cum putem număra numărul de inversiuni. O primă soluţie ar fi chiar să observăm că algoritmul bubblesort rezolvă optim (în sensul că va da numărul minim de swap-uri) problema de mai sus, să aplicăm bubblesort pe Bt şi să numărăm numărul de swap-uri. Această soluţie are complexitate O(N ^ 2) şi ar trebui să obţină 70-80 de puncte.
Pentru 100p va trebui să numărăm inversiunile mai inteligent, folosind un arbore indexat binar/arbore de intervale sau algoritmul mergesort, însă ideile din spatele lor nu le voi mai prezenta în acest articol, ele putând fi găsite printr-o simplă căutare pe google. Astfel se obţine complexitatea dorită O(NlogN). De menţionat că şi o soluţie în O(Nsqrt(N)) ia punctaj maxim.

h2. "Foametea":https://www.infoarena.ro/problema/foametea
 
Problema este împărţită în 4 subtask-uri, fiecare putând fi abordat în moduri diferite.
Pentru subtask-ul 1 putem folosi o percurgere bfs / algoritmul lui Lee, întrucât costurile pe muchii sunt egale cu 1.
Pentru subtask-ul 2 putem parcurge graful in ordinea rezultata din sortarea topologica, deoarece se garanteaza ca graful primit este DAG. Vom retine pentru fiecare nod, t[i] (timpul minim de a ajunge în nodul i) = min{t[j] + l}, unde j are proprietatea că se află la adancime cu 1 mai mica în graf faţă de nodul i, iar l este lungimea muchiei ce uneste j cu i.
Subtask-ul 3 se reduce la problema clasica a aflării drumului cel mai scurt dintre două noduri, care se poate rezolva aplicând algoritmul lui Dijkstra, sau Bellman-Ford.
Pentru rezolvarea ultimului subtask vom extinde ideea de la subtaskul precedent. Va trebui să luăm în calcul faptul că putem ajunge întru-un nod cu un număr variabil de sarmale în traistă. Vom reţine rezultatele intermediare în t[i][j] = timpul minim în care am ajuns în nodul i cu j sarmale. Astfel, pentru Dijkstra, vom folosi stări de tipul {nod, timp, nrSarmale} cu semnificaţia că am ajuns în nodul nod în timp unităţi de timp şi cu nrSarmale în traistă. Dintr-o stare vom trece în următoarele, luând în calcul toate cantităţile posiblile de sarmale pe care le putem aveam în traistă. Rezolvarea cu Bellman-Ford se bazează pe aceeaşi idee. În final, rezultatul va fi min(t[n][j]).
 

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.

Pentru o submultime de factori primi distincti ai lui K: P1, P2, .. , Pi vom calcula numarul de lanturi care au costul divizibil cu P1 * P2 * .. * Pi. Pentru a calcula acest numar vom face aceeasi dinamica ca inainte, doar ca vom folosi doar muchiile care au valoarea divizibila cu P1 * P2 * .. * Pi, acest lucru ne asigura faptul ca orice lant va avea costul divizibil cu P1 * P2 * .. *Pi.
Vom adauga sau vom scadea acest numar de lanturi gasit pentru o submultime fixata in functie de paritatea numarului de elemente al submultimii.
Rezultatul va fi = Numarul de lanturi posibile - Numarul de lanturi cu costul mai mare strict ca 1.

Complexitatea este: O((N + M) * 2^9^) timp cu O(N) memorie

Complexitatea este: O((N + M) * 2^9^) timp cu O(N + M) memorie

public

protected