Подели па владај

Увод

Подели па владај (енгл. Divide and Conquer) је једна од најважнијих и најчешће коришћених техника за конструкцију алгоритама. Суштина технике крије се у томе да се велики проблем подели или разбије на мање делове које је лакше решити.

Техника подели па владај се одвија у три корака:

1. Подели (енгл. Divide) - Полазни проблем се дели на неколико мањих подпроблема који су истог типа као и оригинални проблем.
2. Владај (енгл. Conquer) - Сваки подпроблем се решава рекурзивно. Ако су проблеми довољно мали, тј. ако се ради о основном случају, онда се подпроблеми решавају директно.
3. Обједини (енгл. Combine) - Решења мањих подпроблема се спајају, тј. комбинују, да би се добило решење полазног великог проблема.

Приметимо да је подели па владај специјални случај индуктивно-рекурзивне конструкције алгоритама. И овде се такође ослањамо на индуктивну претпоставку да умемо да решимо подпроблем истог типа, али мање димензије. Не упуштамо се у то на који начин се подпроблем заиста решава, већ прихватамо да је већ решен. Приликом конструкције алгоритма, фокусирамо се на начин којим делимо проблем на подпроблеме и на начин којим решења подпроблема обједињујемо у решење полазног проблема.

У пракси, многи алгоритми се не ослањају на сва три описана корака.

• Поједини проблеми имају тривијалну поделу улазног проблема на подпроблеме (бинарна претрага, сортирање обједињавањем).
• Поједини алгоритми имају нетривијалну поделу на подпроблеме (пивотирање у алгоритму брзог сортирања).
• Неки алгоритми имају тежак корак обједињавања решења (обједињавање сортираних поднизова у алгоритми сортирања обједињавањем).
• Неки алгоритми имају тривијално обједињавање решења (брзо сортирање, бинарна претрага).

Независно од тога да ли им је подела или обједињавање тривијално, свим овим алгоритмима је заједничко да деле проблем на подпроблеме које затим рекурзивно решавају.

На крају, треба нагласити кључну карактеристику проблема који се могу решавати техником подели па владај. Проблеми морају бити такви да након поделе добијемо подпроблеме који се могу решавати у потпуности независно. Ово значи да решење једног подпроблема нема никакав утицај на решење другог подпроблема нити зависи на било који начин од решења неког другог подпроблема. У случају да то није испуњено и да постоји преклапање подпроблема, као на пример код израчунавања Фибоначијевих бројева, тада се подели па владај не може применити. Ако постоји преклапање подпроблема, тада се примењује динамичко програмирање

Подели па владај се најчешће користи за спуштање временске сложености са квадратне на логлинеарну. Погодно је за паралелизацију, јер се подпроблеми могу решавати независно. Међутим, рекурзивна природа оваквих алгоритама подиже меморијску сложеност и отежава разумевање и дебаговање. Такође, лоше дефинисање основног случаја или превелико уситњавање полазног проблема могу утицати на перформансе алгоритама.

Техника за конструкцију алгоритама подели па владај је подскуп индуктивно-рекурзивне технике за конструкцију алгоритама. Подели па владај алгоритми се најчешће конструишу приступом смањи за фактор, тј. у сваком кораку алгоритма полазни проблем делимо на подпроблеме тако што га поделимо на половине, трећине итд.

Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.

Задатак 1

Напиши програм који уређује (сортира) низ бројева неопадајуће (сваки наредни мора да буде већи или једнак од претходног) у $O(n \log n)$ временској сложености.

Улаз: Са стандардног улаза се уноси број $n$ ($1 \le n \le 5 \cdot 10^4$ ) а затим и $n$ природних бројева мањих од $2n$, сваки у посебном реду.

Излаз: На стандардни излаз исписати учитане бројеве у сортираном редоследу.

Решење

Два популарна алгоритма сортирања су заснована на овој техници. Први алгоритам којим ћемо се бавити се назива сортирање обједињавањем (енгл. merge sort). Алгоритам сортирања обједињавањем дели низ на две половине чије се дужине разликују највише за 1. Овај случај се јавља уколико је дужина низа непаран број, па се лева и десна половина морају разликовати за 1. Након поделе, алгоритам рекурзивно сортира леву и десну половину и затим обједињује сортиране половине у сортирани низ. За обједињавање је неопходно користити додатни, помоћни низ и на крају се обједињени низ копира у полазни низ. Излаз из рекурзије је случај једночланог низа. Случај празног низа не може да наступи осим ако је полазни низ празан. Кључна операција у овом алгоритму је операција обједињавања сортираних низова техником два показивача, што нам је познато од раније.

Стандардни трик за убрзавање алгоритма је алокација помоћног низа и његово коришћење кроз рекурзивне позиве. Описани алгоритам сортирања има гарантовану сложеност најгорег случаја $O(n \log n)$, што значи да је много бржа од функција заснованих на сортирању селекцијом или сортирању уметањем чија је сложеност $O(n^2)$. Имплементација је у наставку.

// помоћни метод који обједињује сортиране низове
static void merge(int[] a, int i, int m, int[] b, int j, int n, int[] c, int k)
{
    while (i <= m && j <= n)
        c[k++] = a[i] <= b[j] ? a[i++] : b[j++];
    while (i <= m)
        c[k++] = a[i++];
    while (j <= n)
        c[k++] = b[j++];
}
static void merge_sort(int[] a, int l, int d, int[] tmp)
{
    // ако низ има више од једног елемента
    if (l < d)
    {
        // одређујемо средњи индекс
        int s = l + (d-l)/2;
        // рекурзивно сортирамо леву половину
        merge_sort(a, l, s, tmp);
        // рекурзивно сортирамо десну половину
        merge_sort(a, s+1, d, tmp);
        // обједињујемо сортиране половине у помоћни низ
        merge(a, l, s, a, s + 1, d, tmp, l);
        // копирамо сортирани низ из помоћног у полазни
        for (int i = l; i <= d; i++)
            a[i] = tmp[i];
    }
}
static void merge_sort(int[] a)
{
    // креирамо помоћни низ 
    int[] tmp = new int[a.Length];
    // сортирамо низ
    merge_sort(a, 0, a.Length-1, tmp);
}

Други алгоритам сортирања се назива брзо сортирање (енгл. quick sort). У сваком кораку алгоритма сортирања један елемент (обично називан пивот) се доводи на своје место у сортираном поретку. Да би након тога, проблем могао бити сведен на сортирање два мања подниза. Приликом довођења пивота на своје место потребно је груписати све елементе мање или једнаке од пивота лево од њега, а све елементе веће од пивота десно од њега (ако се низ сортира неопадајуће). То прегруписавање елемената низа, корак партиционисања, је кључни корак алгоритма брзог сортирања.

Партиционисање низа се врши техником два показивача. Алгоритам је сличан двобојци или тробојци. Фиксираћемо последњи елемент низа као пивот. Слично као у двобојци, одржавамо показивач на исправно место пивота. Крећемо од првог елемента низа и ако је текући елемент већи од пивота, прескачемо га. Ако је текући елемент мањи или једнак од пивота, померамо позицију пивота унапред и мањи елемент доводимо на то место. На крају, потребно је да пивота доведемо на место у низу које смо одредили.

Након партиционисања, рекурзивно сортирамо леви и десни подниз. Имплементација је у наставку.

// помоћни метод који размењије места елемената у низу
static void swap(int[] niz, int i, int j)
{
    int tmp = niz[i];
    niz[i] = niz[j];
    niz[j] = tmp;
}
// помоћни метод који ради пивотирање
static void particionisanje(int[] niz, int l, int r)
{
    // последњи елемент низа бирамо као пивот
    int x = niz[r];
    // претпостављамо да је пивот најмањи елемент низа
    int poz = l - 1;
    // у петљи пролазимо кроз елементе низа
    for (itn j = l; j < r - 1; j++)
    {
        // ако је текући елемент мањи од пивота
        if (niz[j] <= x)
        {
            // увећавамо позицију пивота
            poz++;
            // мањи елемент доводимо испред пивота
            swap(niz, poz, j);
        }
    }
    // на крају доводимо пивота на право место у сортираном низу
    swap(niz, poz+1, r);
    // враћамо позицију пивота
    return pos + 1;
}
static void quick_sort(int[] niz, int l, int r)
{
    // ако низ има више од једног елемента
    if (l < r)
    {
        // партиционишемо низ и одређујемо позицију пивота  
        int q = particionisanje(niz, l, r);
        // рекурзивно сортирамо елементе лево од пивота
        quick_sort(niz, l, q-1);
        // рекурзивно сортирамо елементе десно од пивота
        quick_sort(niz, q+1, r);
    }
}

Сложеност најгорег случаја овог алгоритма може бити квадратна тј. $O(n^2)$, ако се стално дешава да пивот дели низ на две неравномерне целине. Ипак, може се доказати да је просечна сложеност овог алгоритма $O(n \log n)$ и у пракси он показује веома добре резултате (за разлику од сортирања обједињвањем не троши се време на померање елемената између помоћног и главног низа).

Задатак 2

Постоји неколико мера које одређују средину дате серије бројева. Најпознатија је аритметичка средина тј. просек, међутим, она је прилично осетљива на грешке у подацима и неколико елемената који значајно одступају од осталих могу прилично да измене просек. На пример, просек бројева $3, 2, 1, 5, 4$ је $3$, међутим, ако им се дода број $99$, тада просек постаје око $19$, што је јако велика промена настала под утицајем само једног елемента, који може бити и резултат неке грешке у подацима. Зато се често разматра медијана која се добија тако што се низ сортира и посматра се средишњи елемент (ако је укупан број елемената непаран), тј. просек два средишња елемента (ако је укупан број елемената паран). На пример, ако се наша полазна серија сортира добија се $1, 2, 3, 4, 5$ и ту је средишњи елемент $3$ и он је уједно и медијана, а ако се придода и $99$, тада су два средишња елемента $3$ и $4$ и медијана је $3.5$. Написати функцију која одређује медијану дате серије бројева.

Улаз: У првој линији стандардног улаза налази се број $n$ ($1 \le n \le 10^5$) који представља број елемената серије чију медијану треба израчунати. У следећих $n$ линија се учитава један по један природан број који представљају елементе серије.

Излаз: На стандардни излаз исписати вредност медијане заокружене на 2 децимале.

Решење

Наивно решење би било да низ сортирамо и да само извучемо средњи елемент из сортираног низа. Међутим, задатак се може решити и значајно ефикасније. Задатак се може решити поступком који је модификација алгоритма брзог сортирања и који се назива алгоритам брзог избора (енгл. quick select). Поступак се ослања на чињеницу да у кораку партиционисања правимо поделу низа на две дисјунктне групе и да пивотирајући елемент доводимо на исправно место у сортираном низу. Дакле, ми треба да нађемо ону вредност која ће након пивотирања завршити на позицији $n/2$. Размотримо алгоритам детаљније.

Након партиционисања постоје три могућности. Нека је позиција пивота након партиционисања $p$. Једна је да се пивот налази баш на траженој позицији $n$, тј. да је $p = n$. У том случају функција враћа пивот и завршава са радом. Друга могућност је да је $n < p$ и тада се алгоритам примењује на део низа $[l, p − 1]$. На крају, трећа могућност је да је $n > p$ и тада се алгоритам примењује на део низа $[p + 1, r]$. Основна имплементација може бити рекурзивна (по узору на QuickSort функција прима параметре $l$ и $r$), међутим, пошто се у варијанти QuickSelect врши само један рекурзивни позив и то као репни, рекурзију је веома једноставно елиминисати.

// помоћни метод који размењује места елемената у низу
static void swap(int[] niz, int i, int j)
{
    int tmp = niz[i];
    niz[i] = niz[j];
    niz[j] = tmp;
}
// помоћни метод који ради пивотирање
static void particionisanje(int[] niz, int l, int r)
{
    // последњи елемент низа бирамо као пивот
    int x = niz[r];
    // претпостављамо да је пивот најмањи елемент низа
    int poz = l - 1;
    // у петљи пролазимо кроз елементе низа
    for (itn j = l; j < r - 1; j++)
    {
        // ако је текући елемент мањи од пивота
        if (niz[j] <= x)
        {
            // увећавамо позицију пивота
            poz++;
            // мањи елемент доводимо испред пивота
            swap(niz, poz, j);
        }
    }
    // на крају доводимо пивота на право место у сортираном низу
    swap(niz, poz+1, r);
    // враћамо позицију пивота
    return poz + 1;
}
static int quick_select(int[] niz, int l, int r, int k)
{
    // све док постоји макар један елемент
    while (l <= r)
    {
        // одређујемо позицију пивота
        int q = particionisanje(niz, l, r);
        // ако је она позиција коју тражимо, прекидамо претрагу
        if (q == k) 
            return niz[q];
        // ако је тражена позиција лево од пивота, ажурирамо десну границу
        else if (k < q)
            r = q - 1;
        // ако је тражена позиција десно од пивота, ажурирамо леву границу
        else
            l = q + 1;
    }
    // реда ради, не може никад да се деси
    return -1;
}
static double medijana(int[] niz)
{
    // одређујемо дужину низа
    int n = niz.Length - 1;
    // одређујемо средњи елемент низа
    int srednji = quick_select(niz, 0, n - 1, n/2);
    // ако је низ непаран, средњи елемент је медијана
    if (n % 2 == 1)
        return srednji;
    // ако није
    else {
        // одређујемо елемент поред њега
        int srednji1 = quick_select(niz, 0, n-1, n/2 - 1);
        // и рачунамо медијану као аритметичку средину
        return (srednji + srednji1)/2.0;
    }
}

Као и у случају алгоритма QuickSort и сложеност алгоритма QuickSelect зависи од тога колико среће имамо да пивот равномерно подели интервал $[l, r]$. Ако би се у сваком кораку десило да пивот упадне на средину интервала, укупан број поређења и размена био би $O(n)$ (заиста, у првом кораку то се ради $n$ пута, у другом $n/2$, у трећем $n/4$ и тако даље, а збир тих елемената се одозго може ограничити са $2n$). Са друге стране, ако би пивот стално био близак неком од два краја интервала $[l, r]$, тада би сложеност алгоритма била $O(n^2)$ (заиста, у првом кораку бисмо имали $n$ поређења, у другом $n − 1$, у трећем $n − 2$ што у збиру даје $n(n + 1)/2$).

Задатак 3

Ученик је радио $n$ задатaкa и за сваки задатак je добио одређени број поена. Одредити збир поена на $k$ задатака које је најбоље урадио.

Улаз: У првој линији стандардног улаза унети природан број $n$ ($1 \le n \le 10^6$) - број задатака које је ученик радио, у другој природан број $k$ ($1 \le k \le n$) - број задатака које је најбоље урадио, а затим у следећих $n$ линија број поена које је добио на задацима.

Излаз: Укупан број поена које је освојио на $k$ најбоље оцењених задатака.

Решење

Директно решење задатка је сортирати низ поена, па затим сабрати $k$ задатака са највише поена. Сложеност решења је $O(n \log n)$, јер сортирање доминира. Наивно решење је у наставку:

static int zbir_k_najboljih(int[] poeni, int k)
{
    // сортирамо низ неопадајуће
    Array.Sort(poeni);
    // саберемо последњих k елемената низа
    int z = 0;
    for (int i = poeni.Length - 1; i > n - 1 - k; i--)
        z += poeni[i];
    // враћамо резултат
    return z;
}

Друго могуће решење је модификација сортирања избором. Сортирање избором у свакој итерацији на позицију $i$ доводи $i$-ти најмањи елемент. Након $n$ таквих итерација добићемо сортиран низ. Нама треба само првих $k$ највећих елемената низа, па алгоритам можемо да модификујемо тако да низ сортира опадајуће, тј. да на позицију $i$ доводи $i$-ти највећи елемент, и тако да не извршава комплетно сортирање, већ да се заврши након $k$ итерација.

static void swap(int[] niz, int i, int j)
{
    int tmp = niz[i];
    niz[i] = niz[j];
    niz[j] = tmp;
}
static int zbir_k_najboljih(int[] poeni, int k)
{
    // збир је на старту 0
    int z = 0;
    // k пута извршамо унутрашњу петљу сортирања избором
    for (int i = 0; i < k; i++)
    {
        // одређујемо позицију највећег елемента у репу низа
        int max = i;
        for (int j = i + 1; i < n; i++)
        {
            if (niz[j] > max)
                max = j;
        }
        // максимални елемент доводимо на позицију i
        if (i != max)
            swap(niz, max, i);
        // увећавамо збир
        z += niz[i];
    }
    // враћамо резултат
    return z;
}

Задатак можемо да решимо и применом QuickSelect алгоритма. Корак партиционисања ће довести пивот на одговарајуће место у сортираном низу, док ће сви елементи пре пивота бити мањи, а елементи иза пивота већи од њега. Модификоваћемо корак партиционисања тако да подели низ да прво иду елементи већи од пивота, затим пивот и онда елементи мањи од пивота. Да бисмо решили задатак, довољно је да елементе распоредимо тако да испред позиције $k$ буду сви већи елeменти, нема потребе да они буду сортирани. Дакле, искористићемо QuickSelect алгоритам да одредимо елемент на позицији $k$. Имплементација је у наставку.

static void swap(int[] niz, int i, int j)
{
    int tmp = niz[i];
    niz[i] = niz[j];
    niz[j] = tmp;
}
static int particionisanje(int[] poeni, int l, int d)
{
    // за пивота узимамо последњи елемент низа
    int tmp = poeni[d];
    // претпостављамо да је пивот испред свих елемената
    int poz = l - 1;
    // пролазимо кроз елементе низа
    for (int i = l; i <= d; i++)
    {
        // ако је текући елемент већи или једнак од пивота
        if (niz[i] >= tmp)
        {
            // увећавамо позицију пивота
            poz++;
            // и елемент који је већи доводимо на ту позицију
            swap(niz, poz, i);
        }
    }
    // на крају, позиционирамо пивота на његово место
    niz[poz+1] = tmp;
    // враћамо резултат
    return poz + 1;
}
static void quick_select(int[] poeni, int l, int d, int k)
{
    // ако постоји макар један елемент
    if (l < d) 
    {
        // партиционишемо низ
        int q = particionisanje(poeni, l, d);
        // ако је пивот на правом месту, прекидамо рекурзију
        if (q == k)
            return;
        // ако је тражени елемент испред позиције пивота
        else if (k < q)
            // потрагу настављамо у левом поднизу
            quick_select(poeni, l, q - 1, k);
        // иначе настављамо у десном поднизу
        else 
            quick_select(poeni, q + 1, d);
    }
}
static int zbir_k_najboljih(int[] poeni, int k)
{
    // прво прерасподелимо низ тако да $k$-ти највећи елемент буде 
    // на одговорајућој позицији и сви већи од њега испред 
    quick_select(poeni, 0, niz.Length - 1, k);
    // саберемо првих k највећих елемената низа
    int z = 0;
    for (int i = 0; i < k; i++)
        z += poeni[i];
    // враћамо резултат
    return z;
}

Задатак 4

Са брода се виде зграде на обали велеграда. Дуж обале је постављена координатна оса и за сваку зграду се зна позиција левог краја, висина и позиција десног краја. Написати програм који израчунава силуету града.

Силуета је део-по-део константна функција и одређена је интервалима константности $(-\infty, x_0)$, $[x_0, x_1)$, $[x_1, x_2)$, $\ldots$, $[x_{n−1}, +\infty)$, одређеним тачкама поделе $x_0 < x_1 < \ldots < x_{n−1}$ и вредностима $0, h_0 ,\ldots, h_{n−2}$ и $h$ функције на сваком од интервала.

$$\begin{aligned} \quad & 0 & \quad & h_0 & \quad & h_1 & \quad & \ldots & \quad & h_{n-2} \quad & 0 \\ - \infty & \quad & x_0 & \quad & x_1 & \quad & x_2 & \quad & \ldots \quad x_{n-2} & \quad \quad \quad x_{n-1} \quad 0 \end{aligned}$$

Подразумевамо да су крајње тачке $−\infty$ и $+\infty$ и да су вредности на тим интервалима једнаке нули. Дакле, део-по-део константна функција се може представити помоћу $n$ тачака $x_0, \ldots, x_{n−1}$ и $n−1$ вредности $h_0, \ldots, h_{n−2}$. Једноставности ради ми ћемо овакве функције представљати помоћу $n$ уређених парова $(x_0, h_0)$, $(x_1, h_1)$, $\ldots$, $(x_{n−2}, h_{n−2})$ и $(x_{n−1}, 0)$. Дакле, наш алгоритам прима низ уређених тројки који описује појединачне зграде, а враћа низ уређених парова који описује силуету.

Улаз: Са станадардног улаза се учитава број зграда $n$, а затим, у $n$ наредних линија по три цела броја раз- двојена са по једним размаком: леви крај зграде, десни крај зграде и висина зграде.

Излаз: На стандардни излаз исписати силуету описану преко низа промена висина.

Пример

Нека је дат следећи улаз:

$$\begin{aligned} 4 & \\ 1 & 4 & 4 \\ 4 & 5 & 5 \\ 4 & 7 & 6 \\ 0 & 9 & 2 \end{aligned}$$

Тада као излаз треба да произведемо следеће:

$$\begin{aligned} 0 & 2 \\ 1 & 4 \\ 4 & 6 \\ 7 & 2 \\ 9 & 0 \end{aligned}$$

Визуелно то можемо приказати на следећи начин:

Лева страна слике представља улазне податке, тј. координате зграда у описаном формату. Десна страна слике представља силуету града, тј. визуелни приказ део-по-део функције $h$.

Решење

Задатак се може лако решити применом технике подели-па-владај. Логика решења је врло слична алгоритму сортирања обједињавањем. Потребно је да улазни низ зграда поделимо на пола, да рекурзивно одредимо силуете левог и десног подпроблема и затим да те две силуете објединимо. Стратегија решавања би била следећа:

1. Базни случај - Основни случај је једна једина зграда описана тројком $(l,r,h)$ која има једноставну силуету $(l,h)$, $(r,0)$.
2. Индуктивна хипотеза - Умемо да одредимо силуету проблема величине $\frac{n}{2}$.
3. Индуктивни корак (конструкција) - Полазни проблем величине $n$ ћемо преполовити на два мања подпроблема величине $\frac{n}{2}$ чије силуете умемо да одредимо према индуктивној хипотези. Након одређивања силуета подпроблема, остаје нам да та решења објединимо. Обједињавање можемо да урадимо по узору на корак обједињавања из сортирања обједињавањем. Укратко, стратегија обједињавања је следећа: пролазимо истовремено кроз обе силуете с лева на десно и одржавамо тренутно највећу висину оба скупа.

Силуете можемо да представимо као листу уређених парова. Сваки пар као први елемент може да чува $x_{i}$ координату, а као други елемент може да чува висину $h_i$ придружену координати. Ако су нам дате две силуете $S_1$ и $S_2$, можемо их објединити следећим поступком заснованим на техници два показивача:

• Бројачи - Првој силуети $S_1$ придружујемо бројач $i$, а другој силуети $S_2$ придружујемо бројач $j$.
• Пратимо висине - У коду одржавамо две променљиве $h_1$ и $h_2$ које редом представљају текуће висине силуета $S_1$ и $S_2$.
• Бирамо минимум - Упоређујемо $x$ координате парова на позицијама $i$ и $j$:
  • Ако је $x_{i} < x_{j}$, тада ажурирамо $h_1$ и померамо бројач придружен $S_1$ унапред.
  • Ако је $x_{j} < x_{i}$, тада ажурирамо $h_2$ и померамо бројач придружен $S_2$ унапред.
  • Ако је $x_{i} = x_{j}$, тада ажурирамо $h_1$ и $h_2$ и померамо унапред оба бројача.
• Рачунамо максималну висину - У сваком кораку, висина силуете је $\max (h_1, h_2)$.
• Провера непотребних тачака - Тачку додајемо у силуету само ако је њена коначна висина $\max (h_1, h_2)$ различита од висине претходне тачке у обједињеној листи.

// дефинишемо помоћни тип података којим представљано зграду
class Zgrada
{
    // зграда је дефинисана левом и десном границом и висином
    public int X_Levo {get;set;}
    public int X_Desno {get;set;}
    public int Visina {get;set;}
    // конструктор
    public Zgrada(int a, int b, int h)
    {
        X_Levo = a;
        X_Desno = b;
        Visina = h;
    }
}
// помоћни тип којим представљамо тачку на силуети
class Tacka
{
    // свака тачка силуете је описана коодинатом и висином
    public int X {get;set;}
    public int Visina {get;set;}
    // конструктор
    public Tacka(int x, int h)
    {
        X = x;
        Visina = h;
    }
}
// помоћни метод који обједињава две силуете
static List<Tacka> objedini(List<Tacka> siluetaLevo, List<Tacka> siluetaDesno)
{
    // на почетку, резултујућа силуета је празна
    List<Tacka> rezultat = new List<Tacka>();
    int i = 0, j = 0;
    int h1 = 0, h2 = 0;
    // пролазимо кроз обе силуете истовремено
    while (i < siluetaLevo.Count && j < siluetaDesno.Count>) 
    {   
        // резултујућа тачка од интереса
        int x; 
        // ако је тачка од интереса у левој силуети
        if (siluetaLevo[i].X < siluetaDesno[j].X)
        {
            // памтимо њену координату и висину и прелазимо на следећу тачку
            x = siluetaLevo[i].X;
            h1 = siluetaLevo[i].Visina;
            i++;
        }
        // ако је тачка од интереса у десној силуети
        else if (siluetaLevo[i].X > siluetaDesno[j].X)
        {
            // памтимо њену координату и висину и прелазимо на следећу тачку
            x = siluetaDesno[j].X;
            h2 = siluetaDesno[j].Visina;
            j++;
        }
        // ако тачка у левој и десној силуети имају исту координату
        else 
        {
            // памтимо координату и висине у силуетама
            x = siluetaLevo[i].X;
            h1 = siluetaLevo[i].Visina;
            h2 = siluetaDesno[j].Visina;
            // померамо оба бројача
            i++;
            j++;
        }
        // налазимо већу од две висине
        int maxH = Math.Max(h1, h2);
        // и ако је резултат празан или се текућа тачка разликује од претходне
        if (rezultat.Count == 0 || rezultat[rezultat.Height - 1].Visina != maxH)
        {
            // додајемо нову тачку у резултујућу силуету
            rezultat.Add(new Tacka(x, maxH));
        }
    }
    // копирамо преостале тачке леве силуете
    while (i < siluetaLevo.Count)
    {
        rezultat.Add(new Tacka(siluetaLevo[i].X, siluetaLevo[i].Visina));
        i++;
    }
    // копирамо преостале тачке десне силуете 
    while (j < siluetaDesno.Count)
    {
        rezultat.Add(new Tacka(siluetaDesno[j].X, siluetaDesno[j].Visina));
        j++;
    }
    // враћамо резултат
    return rezultat;
}
static List<Tacka> odredi_siluetu(Zgrada[] niz, int l, int d)
{
    // ако се ради о једној тачки, тј. основном случају
    if (l == d)
    {
        // креирамо силуету
        List<Tacka> silueta = new List<Tacka>();
        silueta.Add(new Tacka(niz[l].X_Levo, niz[l].Visina));
        silueta.Add(new Tacka(niz[l].X_Desno, 0));
        // и враћамо резултат
        return silueta;
    }
    // иначе, одређујемо средњу тачку
    int m = l + (d-l)/2;
    // рекурзивно одређујемо силуету леве половине
    List<Tacka> siluetaLevo = odredi_siluetu(niz, l, m);
    // рекурзивно одређујемо силуету десне половине
    List<Tacka> siluetaDesno = odredi_siluetu(niz, m + 1, d);
    // обједињујемо решења подпроблема у решење проблема
    return objedini(siluetaLevo, siluetaDesno);
}
static List<Tacka> odredi_siluetu(Zgrada[] niz)
{
    return odredi_siluetu(niz, 0, niz.Length - 1);
}

Временска сложеност решења је $O(n \log n)$. Број подела у алгоритму је једнак $O(\log n)$, а обједињавање у свакој подели ће нас коштати $O(n)$, што ће укупно бити $O(n \log n)$. Просторна сложеност је $O(n)$ због низа у којем чувамо резултујеће тачке које формирају силуету. Критични детаљ алгоритма је обједињавање две силуете које се мора одрадити у линеарном времену, ако желимо да постигнемо наведену временску сложеност.

Задатак 5

Напиши програм који одређује колико у низу има инверзија, тј. позиција $0 \le i < j < n$, таквих да је $a_i > a_j$ .

Улаз: Са стандардног улаза се уноси број $n$ ($1 \le n ≤ 10^5$) и затим $n$ целих бројева, сваки у посебном реду.

Излаз: На стандардни излаз исписати само тражени број инверзија.

Решење

Грубом силом задатак можемо врло лако да решимо. Потребно је само да упоредимо елементе низа по принципу сваки са сваким. Сложеност наивног решења је $O(n^2)$

static int broj_inverzija(int[] niz)
{
    int br = 0;
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i + 1; j < niz.Length; j++)
        {
            if (niz[i] > niz[j])
                br++;
        }
    }
    return br;
}

Задатак можемо врло лако да решимо и техником подели па владај. Стратегија је следећа:

1. Базни случај - Празан и једноелементни низ не могу имати инверзије, па је тада резултат 0.
2. Индуктивна хипотеза - Умемо да одредимо број инверзија проблема величине $\frac{n}{2}$.
3. Индуктивни корак (конструкција) - Полазни проблем величине $n$ ћемо преполовити на два мања подпроблема величине $\frac{n}{2}$ чије бројеве инверзија умемо да одредимо према индуктивној хипотези. Након одређивања решења подпроблема, остаје нам да та решења објединимо. Број инверзија решења једнак је збиру инверзија у подпроблемима увећаном за број парова таквих да први елемент припада левом поднизу, други елемент припада десном поднизу и први елемент је већи од другог.

Кључни детаљ који треба да приметимо у конструкције јесте да израчунавање броја парова можемо много лакше да урадимо ако би подпроблеме сортирали. Њихова сортираност неће променити број парова који су инверзије, али ће нама олакшати њихово бројање. Тада бисмо број инверзија могли врло лако да одредимо у кораку обједињавања из сортирања обједињавањем. Сортирање и бројање можемо да објединимо у један алгоритам на врло једноставан начин.

static int objedini(int[] a, int i, int m, int[] b, int j, int n, int[] tmp, int k)
{
    // на старту, број инверзија је нула
    int br = 0;
    // пролазимо елемент по елемент кроз поднизове
    while (i <= m && j <= n)
    {
        // ако се не ради о инверзији само копирамо елементе
        if (a[i] <= b[j])
            tmp[k++] = a[i++];
        // инверзија
        else 
        {
            // увећавамо бројач
            // елемент b[j] је у инверзији са свим елементима испред
            // a[i], а тих елемената има (m - i + 1)
            br +=  m - i + 1;
            // копирамо елемент у резултујући низ
            tmp[k++] = b[j++];
        }
    }
    // у реповима низова не може бити инверзија
    // па их само копирамо
    while (i <= n)
        tmp[k++] = a[i++];
    while (j <= n)
        tmp[k++] = b[j++];
    // враћамо резултат
    return br;
}
static int broj_inverzija(int[] niz, int l, int d, int[] tmp)
{
    // скуп са 1 или 0 елемената нема инверзија
    if (l >= d)
        return 0;
    // одређујемо средњи индекс
    int m = l + (d-l)/2;
    // рекурзивно одређујемо број инверзија у левој половина
    int inverzijeLevo = broj_inverzija(niz, l, m, tmp);
    // рекурзивно одређујемо број инверзија у десној половина
    int inverzijeDesno = broj_inverzija(niz, m+1, d, tmp);
    // рекурзивно одређујемо број инверзија након обједињавања
    int brojParova = objedini(niz, l, m, niz, m+1, d, tmp, l);
    // копирамо сортиран низ назад у полазни
    for (int i = 0; i < niz.Length; i++)
        niz[i] = tmp[i];
    // укупан број инверзија је збир три резултата
    return inverzijeLevo + inverzijeDesno + brojParova;
}
static int broj_inverzija(int[] niz)
{
    // помоћни низ који користимо за обједињавање
    int[] tmp = new int[niz.Length];
    // 
    return broj_inverzija(niz, 0, niz.Length - 1, tmp);
}

Временска сложеност приказаног алгоритма једнака је временској сложености сортирања обједињавањем, тј. $O(n \log n)$.

Задатак 6

Напиши програм који одређује највећи збир неког сегмента (подниза узастопних елемената) датог низа.

Улаз: Са стандардног улаза се уноси број $n$ ($1 \le n ≤ 50000$), а затим $n$ целих бројева између $−10$ и $10$, сваки број у посебном реду.

Излаз: На стандардни излаз испиши тражени збир.

Решење

Наивно, задатак можемо да решимо испитивањем свих сегмената. Потребне су нам три петље. Прве две ће дефинисати границе сегмента, а последња ће рачунати сам збир сегмента.

static int segment_maks_zbira(int[] niz)
{
    int maks = int.MinValue;
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i; j < niz.Length; j++)
        {
            int zbir = 0;
            for (int k = i; k <= j; k++)
                zbir += niz[k];
            if (zbir > maks)
                maks = zbir;
        }
    }
    return maks;
}

Временска сложеност приказаног решења је $O(n^3)$ и лако се може снизити на $O(n^2)$. Потребно је само да уочимо неефикасност израчунавања збира сегмента. Много је ефикасније да збир сегмента рачунамо инкрементално. Инкрементално решење је у наставку:

static int segment_maks_zbira(int[] niz)
{
    int maks = int.MinValue;
    for (int i = 0; i < niz.Length; i++)
    {   
        int zbir = 0;
        for (int j = i; j < niz.Length; j++)
        {
            zbir += niz[j];
            if (zbir > maks)
                maks = zbir;
        }
    }
    return maks;
}

Временску сложеност решења можемо даље поправити применом технике подели па владај. Стратегија је следећа:

1. Базни случај - Празан низ има збир 0.
2. Индуктивна хипотеза - Умемо да одредимо сегмент највећег збира проблема величине $\frac{n}{2}$.
3. Индуктивни корак (конструкција) - Полазни проблем величине $n$ ћемо преполовити на два мања подпроблема величине $\frac{n}{2}$ чије сегменте највећих збирова умемо да одредимо према индуктивној хипотези. Након одређивања решења подпроблема, остаје нам да та решења објединимо. Све сегменте полазног низа можемо да поделимо на три групе:
   • Сегменте у левој половини низа чији смо највећи сегмент већ одредили.
   • Сегменте у десној половини низа чији смо највећи сегмент већ одредили.
   • Сегменте који садрже средишњи елемент низа које тек треба да испитамо. Сегменте који садрже средишњи елемент можемо лако да испитамо. Крећемо од једночланог сегмента који садржи само средишњи елемент и инкрементално се ширимо налево додајући један по један елемент и рачунајући текући максимум, а затим крећемо од максималног сегмента проширеног налево и инкрементално га проширујемо једним по једним елементом надесно, тражећи нови максимум.

Решење проблема биће сегмент највећег збира из ове три групе. Имплементација је у наставку.

static int segment_maks_zbira(int[] niz, int l, int d)
{
    // празан низ има збир 0
    if (l > d)
        return 0;
    // одређујемо средишњи елемент
    int m = l + (d-l)/2;
    // рекурзивно одређујемо сегмент највећег збира у левој половини
    int maksLevo = segment_maks_zbira(niz, l, m-1);
    // рекурзивно одређујемо сегмент највећег збира у десној половини
    int maksDesno = segment_maks_zbira(niz, m+1, d);
    // инкрементално одређујемо највећи сегмент на лево који садржи средњи елемент
    int zbirSredina = niz[m];
    int maksSredina = zbirSredina;
    for (int i = m - 1; i >= l; i--)
    {
        zbirSredina += niz[i];
        if (zbirSredina > maksSredina)
            maksSredina = zbirSredina;
    }
    // инкрементално одређујемо највећи сегмент на десно који садржи средњи елемент
    zbirSredina = maksSredina;
    for (int i = m + 1; i <= d; i++)
    {
        zbirSredina += niz[i];
        if (zbirSredina > maksSredina)
            maksSredina = zbirSredina;
    }
    // резултат је највећи од те три вредности
    return Math.Max(maksSredina, Math.Max(maksLevo, maksDesno));
}
static int segment_maks_zbira(int[] niz)
{
    return segment_maks_zbira(niz, 0, niz.Length - 1);;
}

Задатак 7

У датом скупу тачака у равни одредити колико је растојање између две тачке које су међусобно најближе.

Улаз: Са стандардног улаза се уноси број тачака $n$ ($1 \le n \le 50000$), а затим у наредних $n$ редова координате тачака (два цела броја између $−10^9$ i $10^9$ , раздвојена размаком).

Излаз: На стандардни излаз исписати тражено растојање, заокружено на пет децимала.

Решење

Наивно решење је врло једноставно. Потребно је само да упоредимо све парове тачака и да нађемо пар на најмањем растојању. Алгоритам се своди на двоструку петљу.

class Tacka
{
    public double X {get; set;}
    public double Y {get; set;}

    public Tacka(double x, double y)
    {
        X = x; 
        Y = y;
    }

    public double Rastojanje(Tacka t)
    {
        double dx = X - t.X;
        double dy = Y - t.Y;
        return Math.Sqrt(dx*dx + dy*dy);
    }
}
public double min_rastojanje(Tacka[] niz)
{
    double min = double.MaxValue;
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i + 1; j < niz.Length; j++)
        {
            double r = niz[i].Rastojanje(niz[j]);
            if (r < min)
                min = r;
        }
    }
    return min;
}

Ефикасније решење можемо добити применом технике подели па владај, тј. декомпозицијом проблема на подпроблеме.

Базни случај представља ситуација у којој имамо мање од четири тачке, јер њих не можемо поделити у две половине у којима постоји бар по један пар тачака (а ако у скупу немамо бар $2$ тачке, најмање растојање није јасно дефинисано). У том случају решење налазимо поређењем растојања свих парова тачака (пошто је тачака мало, овај корак је сложености $O(1)$).

Скуп тачака можемо једном вертикалном линијом поделити на две отприлике истобројне половине. Ако тач- ке сортирамо по координати $x$, вертикална линија може одговарати координати средишње тачке. Рекурзивно одређујемо најмање растојање у првој половини (то су тачке лево од вертикалне линије) и у другој половини (то су тачке десно од вертикалне линије). Најближи пар је такав да су:

1. Обе тачке у левој половини,
2. Обе тачке у десној половини,
3. Једна тачка је у левој, а друга у десној половини.

За прва два случаја већ знамо решења и остаје да се размотри само трећи.

Нека је $d_l$ минимално растојање тачака у левој половини, $d_r$ минимално растојање тачака у десној половини, а $d$ мање од та два растојања. Ако вертикална линија има $x$-координату $x$, тада је могуће одбацити све тачке које су лево од $x-d$ и десно од $x+d$, јер је њихово растојање до најближе тачке из супротне половине сигурно веће од $d$. Потребно је испитати све преостале тачке, тј. све тачке из појаса $[x − d, x + d]$, проверити да ли међу њима постоји неки пар тачака чије је растојање строго мање од $d$ и вредност $d$ ажурирати на вредност најмањег растојања таквог пара тачака. Проблем је што у најгорем случају њих може бити пуно (могуће је да се свих $n$ тачака нађе у том појасу) и ако испитујемо све парове, долазимо у најгорем случају до око $\frac{n^2}{4}$ поређења (ако је пола тачака лево, а пола десно од линије поделе). Ипак, проверу је могуће организовати тако да се провери само мали број парова тачака.

Једноставности ради ћемо претпоставити да истовремено разматрамо све тачке унутар појаса $[x − d, x + d]$, без обзира са које стране вертикалне линије се налазе (унапред знамо да је провера тачака које су са исте стране вертикалне линије поделе непотребна, али не може нарушити коректност, док год смо сигурни да се пореде и сви потребни парови тачака са различите стране те линије). Сваку тачку $A$ из појаса је довољно упоредити са оним тачкама које леже унутар круга са центром у тачки $A$ и полупречником $d$, што омогућава значајна одсецања. Припадност кругу није једноставно проверити и зато уместо њега можемо разматрати квадрат странице дужине $2d$ на чијој се хоризонталној средњој линији налази тачка $A$. Тиме ће одсецање бити за нијансу мање него у случају круга, али ће детектовање тачака које припадају том правоугаонику бити веома једноставно. То ће бити све оне тачке из појаса којима је координата y у интервалу $[y_A − d, y_A + d]$. Описани случај приказан је на следећој слици.

Даље смањење броја поређења можемо добити ако приметимо да сваки пар обрађујемо два пута (једном док обрађујемо тачке у околини прве, а једном док обрађујемо тачке у околини друге тачке). Можемо једноставно закључити да је довољно сваку тачку поредити само са оним тачкама које се налазе на истој висини као она или изнад ње. Дакле, сваку тачку је потребно упоредити само са тачкама чије $x$ координате леже унутар интервала $[x−d, x+d]$ и чије $y$ координате леже унутар интервала $[y_A , y_A +d]$. Први услов можемо обезбедити тако што пре поређења све тачке из појаса ширине $d$ око вертикалне линије поделе издвојимо у посебан низ (за то нам је потребно $O(n)$ додатне меморије и времена). Други услов ефикасније можемо обезбедити ако све тачке тог помоћног низа сортирамо по координати $y$ за шта нам је потребно време $O(y \log n)$ и затим тачке обрађујемо у неопадајућем редоследу $y$ координата. За сваку тачку $A$ обрађујемо само тачке које се налазе иза ње у сортираном низу и обрађујемо једну по једну тачку све док не наиђемо на тачку чија је координата $y$ већа или једнака $y_A + d$ (она од тачке $A$ не може бити на мањем растојању од $d$).

Одредимо сложеност претходног алгоритма. Алгоритам се састоји од два рекурзивна позива за двоструко мању димензију низа тачака и фазе добијања крајњег резултата на основу резултата рекурзивних позива и додатне анализе тачака у појасу $[x − d, x + d]$. Већ смо констатовали да издвајање тачака централног појаса захтева $O(n)$ меморије и времена и да сортирање тих тачака по координати $y$ захтева додатних $O(n \log n)$ корака. Остаје још да се процени сложеност угнежђених петљи у којима се пореде тачке унутар појаса. Иако делује да је сложеност квадратна, елементарним геометријским резоновањем доказаћемо да је сложеност тог корака линеарна тј. $O(n)$ и да се у сваком кораку спољашње петље унутрашња петља може извршити само веома мали број пута (доказаћемо да је тај број извршавања ограничен одозго са $7$, мада је у пракси он често и доста мањи од тога и за насумично генерисане тачке та петља се најчешће извршава $0$, $1$ или евентуално $2$ пута).

За сваку тачку $A$ можемо конструисати $8$ квадрата димензије $d/2$, као што је приказано на следећој слици (квадрати су уписани у појас $[x − d, x + d]$, у два реда од по четири квадрата и тачка $A$ лежи на доњој ивици доњих квадрата).

Највеће растојање између две тачке унутар неког квадрата се постиже када они леже у његовим наспрамним теменима, а пошто је дужина дијагонале квадрата странице $d/2$ једнака $d^2/2 \approx 0.70711 \cdot d$, растојање између сваке две тачке унутар истог квадрата је строго мање од $d$. Пошто сви квадрати леже било потпуно са леве стране вертикалне линије поделе, било са њене десне стране унутар сваког од квадрата се може наћи највише једна тачка нашег скупа (у супротном би се, било са леве, било са десне стране централне линије поделе, налазио пар тачака са растојањем строго мањим од $d$, што је контрадикторно са дефиницијом величине $d$). То значи да се изнад тачке $A$ може налазити највише $7$ тачака које припадају осталим квадратима (сама тачка $A$ већ припада једном од квадрата) и да се све остале тачке које су изнад $A$ налазе и изнад наших квадрата, што значи да им је растојање од $A$ сигурно веће од $d$ (јер им је вертикално растојање веће од $d$) и њих није потребно разматрати.

Тачке које су са исте стране линије поделе као и тачка $A$ можемо просто прескочити у телу унутрашње петље и тако уштедити на рачунању њиховог растојања од тачке $A$, али експерименти показују да та уштеда није осетна. Друга могућност за имплементацију је да не чувамо све тачке из појаса у истом скупу, већ да их поделимо у два појаса и да затим обрадимо прво све тачке из левог појаса гледајући растојања у односу на наредне највише $4$ тачке из десног појаса, а затим да обрадимо све тачке из десног појаса гледајући растојања у односу на највише $4$ тачке из левог појаса (јер у супротном појасу постоји $4$ квадрата димезије $d/2$, за које смо доказали да не могу да садрже две тачке истовремено). Имплементација на тај начин је мало компликованија, а експерименти не указују на значајне добитке.

Мастер теоремом се може показати да је временска сложеност описаног алгоритма $O(n \log^2 n)$. Имплементација је у наставку.

// помоћни тип података за представљање тачака
class Tacka
{
    public double X {get; set;}
    public double Y {get; set;}
    // коснтруктор
    public Tacka(double x, double y)
    {
        X = x; 
        Y = y;
    }
    // помоћни метод који рачуна растојање
    public double Rastojanje(Tacka t)
    {
        double dx = X - t.X;
        double dy = Y - t.Y;
        return Math.Sqrt(dx*dx + dy*dy);
    }
}
public double min_rastojanje(Tacka[] niz)
{
    double min = double.MaxValue;
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i + 1; j < niz.Length; j++)
        {
            double r = niz[i].Rastojanje(niz[j]);
            if (r < min)
                min = r;
        }
    }
    return min;
}
static double najblize_tacke(Tacka[] tacke, int l, int d, Tacka[] pojas)
{   
    // ако скуп има мање од 4 тачке
    if (r - l + 1 < 4)
    {
        // пешачки рачунамо растојање
        double min = double.MaxValue;
        for (int i = l; i < d; i++)
        {
            for (int j = i + 1; j <= d; j++)
            {
                double r = niz[i].Rastojanje(niz[j]);
                if (r < min)
                    min = r;
            }
        }
        return min;
    }
    else 
    {
        // у супротном одређујемо средишњу тачку
        int m = l + (d - l)/2;
        // рекурзивно одређујемо тачке на најмањем растојању у левом поднизу
        double d1 = najblize_tacke(tacke, l, m, pojas);
        // рекурзивно одређујемо тачке на најмањем растојању у десном поднизу
        double d2 = najblize_tacke(tacke, m + 1, d, pojas);
        // рачунамо ширину појаса
        double d = Math.Min(d1, d2);
        // дефинишемо границе појаса
        double dl = tacke[m].X - d;
        double dd = tacle[m].X + d;
        // издвајамо тачке у појасу
        int k = 0;
        for (int i = l; i <= d; i++) 
        {
            if (dl <= tacke[i].X && tacke[i].X <= dd>)
            {
                pojas[k++] = tacke[i];
            }
        }
        // тачке у појасу сортирамо по у координатама
        Array.Sort(pojas, 0, k, (x,y) => {
            return x.Y.CompareTo(y.Y);
        })
        // ручно одређујемо најмање растојање узимајући у обзир тачке из појаса        
        for (int i = 0; i < k; i++)
        {
            for (int j = i + 1; j < k && pojas[j].y - pojas[i].y < d; j++)
            {
                double r = pojas[i].Rastojanje(pojas[j]);
                if (r < d)
                    d = r;
            }
        }
        // враћамо резултат
        return d;
    }
}
static double najblize_tacke(Tacka[] tacke)
{
    // помоћни низ за чување тачака у појасу
    Tacka[] pojas = new Tacka[tacke.Length];
    // сортирамо тачке по х координатама
    Array.Sort(tacke, (x,y) => {
        return x.X.CompareTo(y.X);
    });
    // одређујемо најмање растојање између тачака у скупу
    return najblize_tacke(tacke, 0, tacke.Length - 1, pojas);
}