h2. Problema 1
p<>. Se considera $N (N≤50 000)$ segmente in plan dispuse paralel cu axele OX si OY. Sa se determine care este numarul total de intersectii dintre segmente.
p<>. Se considera $N (N≤50 000)$ segmente in plan, dispuse paralel cu axele OX si OY. Sa se determine care este numarul total de intersectii dintre segmente.
p<>. In fisierul $_segment.in_$ se gaseste pe prima linie numarul $N$ de segmente, iar pe fiecare dintre urmatoarele $N$ linii cate patru numere naturale mai mici decat $50 000$, reprezentand coordonatele carteziene ale extremitatilor fiecarui segment.
Rezultatul se va scrie in $_segment.out_$.
p<>. Vom demonstra in continuare ca operatiile prezentate mai sus au complexitatea $O(log{~2~} N)$ pentru un arbore de $N$ intervale. Este posibil ca intr-un nod sa aiba loc apel atat in fiul stang cat si in cel drept. Acest lucru produce un cost aditional doar prima data cand are loc. Dupa prima "rupere in doua", oricare astfel de "rupere" nu va aduce cost aditional, deoarece unul din fii va fi mereu inclus complet in intervalul $[a,b]$. Cum inaltimea arborelui, pentru $N$ intervale, este $[log{~2~}N]+1$, complexitatea operatiilor va fi tot $O(log{~2~} N)$.
p<>. Pentru a retine in memorie un arbore de intervale pentru $N$ valori, vom aveam de nevoie de $N+N/2+N/4+N/8...=2*N-1$ locatii de memorie (sunt $2*N-1$ noduri). Deoarece arborele nu este complet, trebuie verificat de fiecare data daca fii unui nod exista in arbore (aceasta verificare a fost omisa in pseudocodul de mai sus), altfel s-ar incerca accesarea de valori din vector care nu exista. Daca memorie disponibila in timpul concursului este suficienta, se poate declara vectorul care retine arborele de intervale de lungime $2^K^$ astfel incat $2^K^≥2*N-1$, simuland astfel un arbore complet si nefiind necesare verificarile mentionate mai sus.
p<>. Pentru a rezolva in continuare problema, vom folosi un arbore de intervale pentru a simula in timp logaritmic operatiile facute inainte pe un vector obisnuit. Astfel, in fiecare nod din arborele din intervale vom retine cate capete exista in acel interval. Primele doua operatii vor fi implementate folosind procedura ACTUALIZARE() de mai sus pentru intervalul $[y,y]$ in arborele T(0, MAXC) si adunand $1$, respectiv scazand $1$ la fiecare nod actualizat. Cea de-a treia operatie poate fi realizata folosind procedura INTEROGARE() pe intervalul $[y{~1~},y{~2~}]$. Astfel complexitatea se reduce la $O(N*log{~2~} MAXC)$ Folosind aceeasi tehnica de "comprimare" a coordonatelor se poate obtine o complexitate $O(N*log{~2~} N)$.
In figura urmatoare este descrisa structura arborelui de intervale, dupa actualizarea pentru intervalele $[2,2]$, $[6,6]$ si $[9,9]$. Sunt marcate intervalele care conduc la obtinerea numarului de segmente intersectate de primul segment vertical, obtinute in urma interogarii pe intervalul $[0,8]$.
[poza]
h2. Problema 2 (Preluata de la IOI 1998, Ziua 2)
p<>. Se considera $N≤50 000$ dreptunghiuri in plan, fiecare avand laturile paralele cu axele $OX, OY$. Lungimea marginilor (contururilor) reuniunii tuturor dreptunghiurilor se va numi "perimetru". Sa se calculeze perimetrul celor $N$ dreptunghiuri.
p<>. In fisierul $drept.in$ se gaseste pe prima linie numarul $N$ de dreptunghiuri, iar pe fiecare din urmatoarele $N$ linii cate patru numere naturale mai mici ca $50 000$, reprezentand coordonatele carteziene ale coltului stanga sus, respectiv dreapta jos ale fiecarui dreptunghi. Rezultatul se va scrie in fiÅŸierul $drept.out$.
p<>. Timp maxim de executie: $1 secunda / test$
Exemplu:
|_. drept.in |_. drept.out |_. Figura |
|^. 3
3 8 8 3
6 10 12 6
12 4 15 1 |^. 44 | [poza] |
Folosind un rationament asemanator ca si la prima problema, constatam necesitatea unui algoritm de baleiere. Vom descompune problema in doua parti: prima data calculam perimetrul folosind doar laturile stanga si dreapta ale dreptunghiurilor pentru a calcula perimetrul pe $OY$; apoi putem sa rotim dreptunghiurile si folosind aceeasi procedura pt a calcula perimetrul pe $OX$, folosind doar laturile sus si jos ale dreptunghiurilor.
Fiecare latura (stanga sau dreapta) va fi un punct eveniment. Sortam laturile crescator dupa coordonata $x$ si parcurgem de la stanga la dreapta. Cand intalnim o latura stanga adaugam in starile dreptei de baleiere, intervalul de unitati ocupat de latura pe OY, iar cand intalnim o latura dreapta, eliminam din starile dreptei de baleiere intervalul de unitati ocupat de latura. Intre oricare doua puncte eveniment consecutive are loc o modificare a perimetrului total pe $OY$. Astfel, dupa fiecare actualizare a starilor dreptei de baleiere se va retine care este numarul de unitati adaugate pana in prezent (nu se tine cont daca o unitate este adaugata de mai multe ori). Vom aduna la perimetrul pe $OY$ total de fiecare data, diferenta absoluta intre numarul de unitati adaugate pana in prezent si valoarea imediat anterioara (dinaintea actualizarii). Asadar, este necesara o structura de date care se efectueze urmatoarele operatii in timp eficient (preferabil logaritmic):
* MARCHEAZA(a,b) : adauga intervalul $[a, b]$
* DEMARCHEAZA(a,b) : elimina intervalul $[a, b]$
* INTEROGARE() : returneaza numarul total de coordonate adaugate pana in prezent
p<>. Putem folosi un arbore de intervale pentru a obtine o complexitate $O(log{~2~} MAXC)$ sau $O(log{~2~} N)$ pentru primele doua operatii si $O(1)$ pentru ce-a de treia. In fiecare nod din arbore retinem de cate ori a fost marcat intervalul respectiv si cate unitati din intervalul respectiv au fost marcate. Primele doua operatii pot fi implementate folosind procedura ACTUALIZARE() iar a treia operatie va returna valoarea numarul de unitati care au fost marcate din radacina arborelui de intervale.
p<>. In figura urmatoare este descrisa structura arborelui de intervale, dupa adaugarea intervalelor $[3,8]$ si $[6,10]$ (un interval $[y1,y2]$ reprezinta intervalul de unitati $[y1, y2-1]$ din arbore).
[poza]
h2. Problema 3
p<>. Se dau $N≤100 000$ puncte in plan de coordonate numere naturale mai mici ca $2 000 000 000$. Sa se raspunda la $M≤1 000 000$ intrebari de forma "cate puncte din cele $N$ exista in dreptunghiul cu coltul stanga sus in $(x1,y1)$ si coltul dreapta jos in $(x2,y2)$?".
p<>. In fisierul $puncte.in$ se vor gasi pe prima linie numerele $N$ si $M$. Pe urmatoarele $N$ linii se vor gasi coordonatele punctelor. Pe urmatoarele $M$ linii se vor gasi cate patru numere naturale reprezentand coordonatele colturilor dreptunghiurilor.
p<>. In fisierul $puncte.out$ se vor gasi $M$ numere naturale reprezentand raspunsurile la întrebari.
p<>. Timp maxim de executie: $1 secunda / test$
p<>. Exemplu:
|_. puncte.in |_. puncte.out |_. Figura |
|^. 6 1
2 8
5 3
6 5
8 7
8 1
10 10
4 8 9 4 |^. 2 | [poza] |
p<>. Problema determinarii numarului de puncte din interiorul unui dreptunghi este o particularizare bidimensionala pentru problema numita in literatura de specialitate "Orthogonal Range Search". Varianta aleasa pentru acest caz consta intr-un arbore de intervale, care permite determinarea numarului de puncte din interiorul unui dreptunghi cu o complexitate $O(log{~2~}^2^ N)$.
p<>. Astfel, se sorteaza coordonatele $x$ ale punctelor si se construieste un arbore de intervale. Primul nivel al arborelui va contine toate coordonatele $x$. Cei doi fii ai lui vor contine prima jumatate, respectiv a doua jumatate a punctelor (sortate dupa coordonata $x$) si asa mai departe. Pentru fiecare interval de coordonate $x$, se mentin sortate coordonatele $y$ corespunzatoare punctelor care au coordonatele $x$ in intervalul respectiv. Astfel, memoria folosita este $O(N*log{~2~} N)$. Pentru a construi efectiv se foloseste o abordare asemanatoare algoritmului de sortare prin interclasare: in fiecare nod, pentru a obtine lista de coordonate $y$ ordonate, se interclaseaza listelele celor doi fii (deja ordonate). Cand se ajunge intr-o frunza, lista nodului este formata dintr-un singur punct.
p<>. Pentru fiecare dreptunghi, se executa cautarea in arborele de intervale pentru segmentul $[x1, x2]$ (deoarece se folosesc doar cele $N$ coordonate $x$ ale punctelor, se vor potrivi capetele acestui interval folosind cautarea binara la cea mai apropiata coordonata $x$ de fiecare capat). Pentru fiecare interval din arbore atins, se executa doua cautari binare printre coordonatele y corespunzatoare coordonatelor x din acel interval, pentru a determina cate puncte din intervalul respectiv se afla in intervalul $[y1, y2]$ (adica in interiorul dreptunghiului).
p<>. Complexitatea $O(log{~2~}^2^ N)$ poate fi redusa, folosind o metoda descoperita independent de Willard si Lueker in anul $1978$. Se observa ca pentru fiecare coordonata $y$ dintr-un nod, daca presupunem ca se efectueaza o cautare binara, atunci putem determina in timpul interclasarii pozitia din fiecare fiu pe care o va returna cautarea binara pentru aceeasi valoare. Este evident ca pentru o valoare $y$ dintr-un nod care a provenit dintr-un fiu in timpul interclasarii, exista o unica valoare maxima $y'$ din celalalt fiu astfel incat $y'≤y$. Asadar, tinem pentru fiecare valoare $y$ dintr-un nod doi indici care identifica pozitiile corespunzatoare efectuarii unei cautari binare in fii pentru valoarea $y$. Astfel, in timpul cautarii, in loc sa se efectueze cautari binare, se pot parcurge acesti indici, care oferă in $O(1)$ pozitia in lista cautata, reducand complexitatea totala la $O(log{~2~} N)$.
