Doua probleme de la runda 6 a concursului Algoritmus

(Categoria Competitii, autor(i) Cosmin)

Dupa incheierea brusca a concursului Algoritmus, ideile de rezolvare ale rundei 6 nu au mai aparut pe site. In acest articol va voi prezenta ideile de rezolvare la problemele la care eu am realizat solutiile oficiale.

Problema 1: Suprafata

Pentru a rezolva problema folosim paradigma liniei de baleiere folosita mult in rezolvarea problemelor de geometrie computationala (vezi si articolul arbori de intervale din sectiunea download pt alte exemple de probleme in care se foloseste linia de baleiere). Vom considera ca puncte eveniment toate punctele de intersectie intre oricare doua cercuri si punctele de y maxim si de y minim pentru un cerc. Noi avem nevoie numai de coordonata y a acestor puncte pe care o punem intr-un sir. Sortam acest sir ce are maxim n*(n-1) + 2*n coordonate distincte ( n*(n-1) provin din intersectii a cate doua cercuri iar celelalte 2*n din y maxim si y minim pentru fiecare cerc). Intre doua coordonate Y consecutive din vectorul sortat nu exista nici o intersectie intre cercuri. Intersectia unui cerc cu o banda determinata de Y_i si Y_i+1 este un fel de trapez curbat pe care ni-l putem imagina ca o paranteza deschisa si una inchisa. Pentru a determina aria intersectiei multimii de cercuri cu banda determinata de Y_i si Y_i+1 putem sa facem un algoritm care sorteaza intai "parantezele" si dupa aceea parcurge sirul sortat al parantezelor. Cand nivelul de imbricare e 0 inseamna ca tocmai am iesit din cercuri iar nivel de imbricare mai mare ca 0 inseamna ca suntem in interiorul intersectiei. De aici scoatem un algoritm liniar care ne determina intersectia cercurilor cu aceasta banda. Pentru a determina aria ocupata de un trapez curbat trebuie sa putem determina aria dintre coarda si arcul de cerc corespunzator, aceasta arie se poate gasi daca stim unghiul alfa ce se opune coardei pentru ca aceasta arie e diferenta dintre aria sectorului de cerc ( r*r*alpha/2) si aria triunghiului format dintre centrul cercului si coarda (r*r*sin alpha /2), unghiul alpha il aflam folosind functia arccos si cos alpha il determinam cu ajutorul teoremei lui Pitagora generalizate. O mica problema apare in sortarea parantezelor pentru ca daca parantezele provin din cercuri diferite dar le corespunde aceeiasi coarda atunci trebuie sa fim atenti la ordinea in care punem parantezele. Aceasta problema e rezolvata daca gasim un X3 pentru fiecare coarda numar ce reprezinta coordonata X a intersectiei parantezei repsective cu linia orizontala de ordonata (Y_i + Y_i+1) / 2. Am aratat astfel cum se realizeaza determinarea ariei reuniunii cercurilor cu o banda ce nu contine nici o intersectie in O(n log n). Din cauza faptului ca sunt in total maxim O(n²) benzi repetand algoritmul pe fiecare banda obtinem aria reuniunii
cercurilor in timp O(n³ log n).

Problema 4: Joc

Problema cere determinarea numarului maxim de drumuri disjuncte relativ la noduri pornind de la nodul A si terminandu-se in nodul B. Daca ar fi restrictia numai pentru muchii nu si pentru noduri atunci raspunsul ar fi egal cu fluxul maxim in reteaua de transport formata astfel: sursa e nodul A, destinatia e nodul B iar orice muchie (i,j) din graful initial e dublata in reteaua de transport (i,j) si (j,i) fiecare muchie avand capacitate 1. Acesta afirmatie e intiutiva, o demonstratie matematica a ei ar fi aplicarea teoremei clasice: fluxul maxim intr-o retea reziduala este egala cu taietura minima in acea retea si a teoremei lui Menger: numarul maxim de drumuri disjuncte relativ la muchii de la S la T este egal cu taietura minima.

Problema noastra mai are insa o dificultate, aceea ca trebuie sa nu avem acelasi nod in doua drumuri diferite. Aceasta problema o rezolvam dubland fiecare nod si muchiile ce intrau in nod intra acum in primul dintre cele doua noduri, muchiile ce ieseau ies acum din al doilea nod si mai adaugam o muchie intre primul nod si al doilea nod. Acum drumurile disjuncte relativ la muchii din aceasta retea corespund unor drumuri disjuncte relativ la noduri in prima retea.

Astfel am redus problema initiala la una de flux in graf pe graful transformat. Complexitatea algoritmului e O(n*m). Implementarea nu mai dubleaza nodurile la propriu ci foloseste c_i,i pentru a reprezenta muchia intre cele doua noduri ce reprezinta nodul i din graful initial.