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.

h2. "Operatie":https://infoarena.ro/problema/operatie

h2. "PermutariAB":https://www.infoarena.ro/problema/permutariab

Metoda 1:
Observam ca numerele de pe pozitiile impare sunt practic date in input (w[2*k+1][2*k+1] = v[2*k+1][2*k+1] = v[2*k+1]). Ne ramane sa determinam numerele de pe pozitiile pare. In continuare vom arata cum se poate determina v[[$0$]].
 
Vom afla pe rand toti bitii lui v[[$0$]]. Pentru inceput ne vom baza de implicatia v[[$0$]] -> v[[$1$]] = w[[$0$]][[$1$]]. Stim ca daca bitul de la pozitia _i_ al lui v[[$1$]] este 0, atunci bitul lui v[[$0$]] de la pozitia _i_ va fi egal cu negatia bitului de la pozitia _i_ al lui w[[$0$]][[$1$]] (din legea dupa care functioneaza implicatia logica). Daca bitul de la pozitia _i_ al lui v[[$1$]] este 1, atunci stim doar ca bitul lui w[[$0$]][[$1$]] nu poate fi 0. In cazul in care acest lucru se intampla afisam -1.
Analog luam in calcul implictia v[[$1$]] -> v[[$0$]] = w[[$1$]][[$0$]]. Daca bitul de la pozitia _i_ al lui v[[$1$]] este 1, atunci bitul lui v[[$0$]] de la pozitia _i_ va fi egal cu bitul de la pozitia _i_ al lui w[[$1$]][[$0$]] (tot din legea implicatiei logice). Daca bitul de la pozitia _i_ al lui v[[$1$]] este 0, iar cel al lui w[[$1$]][[$0$]] este 0 vom afisa -1.
 
Observam ca prima implicatie ne determina in mod unic bitii lui v[[$0$]] ai caror corespondenti in v[[$1$]] sunt 0. A doua implicatie determina in mod unic bitii lui v[[$0$]] ai caror corespondenti in v[[$1$]] sunt 1. Prin urmare stim ca exista un singur numar v[[$0$]] care satisface implicatiile de mai sus. Astfel stim ca problema are cel mult o solutie.
Dupa ce aflam analog toate numerele de pe pozitiile pare mai trebuie doar sa verificam daca solutia este valida (este posibil sa nu respecte operatiile de xor sau sa nu respecte alte implicatii in afara de cele cu v[[$1$]]).
Complexitate: O(N^2 + N * B)
 
Metoda 2:
Observam ca este suficient sa aflam doar primele 4 numere. Restul se pot deduce pe baza operatiilor de xor. De exemplu: v[4*k] = w[[$0$]][4*k] ^ v[[$0$]].
Putem determina numerele bit cu bit. Pentru fiecare pozitie avem 2^4 = 16 modalitati de a alege bitii de pe pozitia respectiva ai primelor 4 numere. Pentru fiecare modalitate generam bitii pentru celelalte N numere (folosind regula de mai sus) si verificam daca formeaza o solutie valida.
Complexitate: O(N^2 * B). Solutia se va incadra in timp datorita constantei relativ mici.
 
h2. "PermutariAB":https://www.infoarena.ro/problema/permutariab
 
Un lucru foarte interesant la această problemă este faptul că o putem reduce la a sorta crescător o permutare. Mai exact, vom transforma permutarea B într-o permutare Bt astfel încât aplicând aceleaşi operaţii de swap, în aceeaşi ordine, necesare sortării în ordine crescătoare a permutării Bt pe permutarea B, să obţinem permutarea A. Acum rămâne de văzut cum construim permutarea Bt. Să ne uităm la permutarea A, să luam un indice 1 <= i <= N şi să constatăm că pe poziţia i se află o valoare x (i.e. A[i] = x). Deci, după aplicarea operaţiilor de swap aferente transformării lui B în A, valoarea x trebuie să se afle pe poziţia i. Astfel, în Bt, pe poziţia j care are B[j] = x, în Bt vom pune valoarea i (i.e. Bt[j] = i), astfel spunându-ţi "Bă, eu vreau ca valoarea de pe poziţia j să ajungă pe poziţia i după efectuarea swap-urilor". Lucrul care face asta este ordonarea crescătoare a permutării Bt. În continuare, voi face afirmaţia că numărul minim de swap-uri necesar sortării permutării Bt este egal cu numărul de inversiuni ale permutării Bt, afirmaţie pe care am să o demonstrez în cele ce urmează. Readuc aminte faptul că o inversiune este o pereche de indici (i, j) cu i < j şi A[i] > A[j]. De aici rezultă ca numărul de inversiuni ale unei permutări sortate (permutarea identică) are 0 inversiuni şi este unica permutare cu 0 inversiuni. Să analizăm ce efecte are o operaţie de swap:
 
1) Dacă Bt[i] < Bt[i + 1] şi facem swap între ele, numărul de inversiuni va creşte cu 1.
2) Dacă Bt[i] > Bt[i + 1] şi facem swap între ele, numărul de inversiuni va scădea cu 1.
 
Evident că vom vrea să efectuăm swap-uri care vor scădea numărul de inversiuni, deoarece vrem să ajungem la 0 inversiuni cât mai repede. Deci, cum un swap poate scădea cu maxim 1 numărul de inversiuni, rezultă că numărul minim de swap-uri necesare pentru a sorta permutarea este egal cu numărul de inversiuni ale permutării. Q.E.D.
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.
 
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 <tex> \sqrt{(X-X0) * (X-X0) + Y * Y} </tex>, 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)
 
h2. "Tenerife":https://www.infoarena.ro/problema/tenerife
 
Problema ne da un graf orientat aciclic unde nodurile sunt cluburile si muchiile sunt strazile dintre cluburui si ne cere sa calculam numarul de lanturi de cost 1. Costul unui lant este dat de cel mai mare divizor comun dintre valorile muchiilor de pe lant si o valoare K. Vom calcula numarul de lanturi de cost mai mare strict ca 1, deoarece vom vedea ca e mai usor sa calculam aceasta valoare, iar numarul de lanturi de cost 1 va fi numarul de lanturi posibile minus numarul de lanturi de cost mai mare strict ca 1.
Vom face sortarea topologica a grafului si numarul de lanturi posibile il vom calcula cu ajutorul programarii dinamice:
 
Dp[nod] = numarul de lanturi care incep din nod cu minim 2 noduri
Iar recurenta va fi: Dp[nod] = Suma din (Dp[vec] + 1), unde vec este un vecin al lui nod
Numarul de lanturi posibile este egal cu Suma din Dp[nod], pentru orice nod.
 
Acum trebuie sa calculam numarul de lanturi cu costul mai mare strict ca 1. Putem observa ca orice lant are costul egal cu cel mai mare divizor dintre (K, alte numere) => costul unui lant este divizibil cu cel putin un factor prim al lui K.
Pentru fiecare factor prim P al lui K putem calcula numarul de lanturi care au costul divizibil cu P, astfel vom afla numarul de lanturi cu costul mai mare strict ca 1. Pentru a nu lua in considerare un lant de mai multe ori ne vom folosi de principiul includerii si excluderii pe factorii primi distincti ai lui K.
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 + M) memorie

public

protected