Збирови префикса и разлике суседних елемената / Техника два показивача

Увод

Збирови префикса и разлике суседних елемената

Збирови префикса и разлике суседних елемената су још једна елементарна техника која може да нам помогне да снизимо временску сложеност алгоритма. Ове две технике су инверзне једна другој и због тога ћемо их посматрати истовремено. Уместо теоријског објашњења, позабавићемо се карактеристичним примером проблема чије се решење може убрзати применом збирова префикса.

Нека је дат низ бројева $4, 2, 3, 1, 5, 6, 9, 2$. Потребно је да израчунамо парцијалне збирове елемената низа на позицијама из следећих интервала $[3,5]$, $[2,7]$, $[4,6]$. Ради јаснијег записа, тражене збирове можемо да обележимо са $S_{l,d}$, при чему $l$ означава леву границу подниза и $d$ означава десну границу подниза. Пратећи уведену нотацију добићемо следеће:

$$\begin{aligned} S_{3,5} &= 1 + 5 + 6 = 12 \\ S_{2,7} &= 3 + 1 + 5 + 6 + 9 + 2= 26 \\ S_{4,6} &= 5 + 6 + 9 = 20 \end{aligned}$$

Проблем са наивним решењем је у томе што сваки парцијални збир $S_{l,d}$ рачунамо испочетка. Да бисмо решење убрзали потребно је да уочимо следеће:

$$\begin{aligned} S_{0,l} &= \sum_{i=0}^{l} a_i \\ S_{0,d} &= \sum_{i=0}^{d} a_i \\ S_{l,d} &= \sum_{i=l}^{d} a_i = \sum_{i=0}^{d} a_i - \sum_{i=0}^{l-1} a_i \end{aligned}$$

Дакле, да бисмо рачунање парцијалних збирова учинили операцијом у константном времену потребно је да за сваку позицију у низу знамо њен збир префикса. Прецизније, за сваку позицију $0 \le k < n$ у низу треба да одредимо збир $\sum_{i=0}^{k} a_i$. Да бисмо решили задатак, нама нису потребне оригиналне вредности низа, већ само збирови префикса. Због тога, можемо да извршимо промену репрезентације низа (препроцесирање) тако што ћемо инкрементално израчунати збирове префикса на следећи начин:

static int[] izracunaj_zbirove_prefiksa(int[] niz)
{
    int[] zbirovi_prefiksa = new int[n];
    zbirovi_prefiksa[0] = niz[0];
    for (int i = 1; i < niz.Length; i++) 
    {
        zbirovi_prefiksa[i] = zbirovi_prefiksa[i-1] + niz[i];
    }
    return zbirovi_prefiksa;
}

Приказано израчунавање креира нови низ који ће садржати збирове префикса. У случају да нам у задатку нису потребне оригиналне вредности елемената низа, израчунавање збирова префикса можемо да урадимо и у месту, тј. да изменимо вредности елемената у полазном низу:

static void izracunaj_zbirove_prefiksa_u_mestu(int[] niz)
{
    for (int i = 1; i < niz.Length; i++) 
    {
        niz[i] += niz[i-1];
    }
}

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

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

• Низ збирова префикса полазног можемо израчунати у линеарној сложености.
• Важи и обрнуто, тј. од низа префикса, у линеарној сложености можемо израчунати елементе оригиналног низа.
• Важи и тврђење јаче од претходног. Сваки конкретни елемент низа можемо наћи у константној сложености, одузимањем два суседна збира префикса, тј. израчунавањем разлике суседних елемената.

Одавде можемо лако закључити да нема потребе да чувамо и полазни низ и низ збирова префикса. Прецизније, прелазак на збирове префикса је само промена репрезентације података и ништа више. Променом репрезентације, добили смо израчунавње тражених збирова сегмената у константном времену, тј. s = niz[d] - niz[l-1], чиме смо укупну сложеност решења спустили са квадратне на линеарну.

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

Техника два показивача

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

На почетку излагања, треба напоменути да термин “показивач” у називу технике заправо представља бројач. Такође, алгоритми засновани на овој техници не морају бити ограничени на само два бројача. Назив који би у потпуности осликао смисао технике би био “техника два или више бројача”.

Техника два показивача обухвата широку класу ефикасних алгоритама који су карактерисани постојањем две или више бројачких променљивих, које се крећу кроз елементе неког низа (често сортираног) или низова. Главне карактеристике тих бројача и начина обиласка су следеће:

• Бројачи се крећу у истом смеру - Вредност оба бројача се у сваком кораку или увећава или смањује. Ниједан бројач током извршавања алгоритма неће променити свој смер. Упоредите ово са класичним угнежденим петљама у којима се вредност бројача унурашње петље враћа на почетак са сваком новом итерацијом спољашње петље. Кључна разлика је у начину на који управљамо бројачима.
• Бројачи се крећу у сусрет један другом - Честа идеја у техници два показивача јесте обилазак низа са два краја, тј. један бројач се стално повећава, а други бројач се стално смањује. Опет, кључно је то да се вредности свих бројача монотоно мењају, тј. не смемо доћи у ситуацију да вредност било ког од бројача мало расте, мало опада или обрнуто.
• Сваки елемент низа се разматра само коначан број пута који не зависи од дужине низа - Ово својство је последица управљања бројачима. У случају наивних угнеждених петљи сваки елемент низа ћемо разматрати онолико пута колика је величина низа, што директно води ка алгоритму квадратне сложености. У алгоритмима заснованим на техници два показивача, сваки елемент низа ћемо разматрати коначан број пута, који не зависи од величине низа, па ће укупна временска сложеност најчешће пасти за читав ред величине.

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

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

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

Задатак 1

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

Улаз: Са стандардног улаза се уноси број дана $n$ ($1 \le n \le 100000$), а затим у наредном реду $n$ целих бројева између $0$ и $100$, раздвојених са по једним размаком, који представљају зараде током $n$ дана. Након тога се уноси број упита $m$ ($1 \le m \le 100000$) и у наредних $m$ редова се уносе временски периоди одређени редним бројем почетног дана $a$ и крајњег дана $b$ ($0 \le a \le b < n$).

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

Решење

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

static int zbir_segmenta(int[] niz, int i, int j) 
{
    int z = 0;
    for (int k = i; i <= j; k++)
        z += niz[k];
    return z;
}
static void zad1()
{
    int n = int.Parse(Console.ReadLine());
    int[] zarade = new int[n];
    string[] linija = Console.ReadLine.Split(" ");
    for (int i = 0; i < n; i++)
    {
        zarade[i] = int.Parse(linija[i]);
    }
    int m = int.Parse(Console.ReadLine());
    while (m > 0) {
        linija = Console.ReadLine().Split();
        int i = int.Parse(linija[0]);
        int j = int.Parse(linija[1]);
        int zbir = zbir_segmenta(zarade, i, j)
        Console.WriteLine(zbir);
        m--;
    }
}

Разлог неефикасности наивног решења je линијa обележена жутом бојом у функцији. Лако се може уочити да збир сваког сегмента рачунамо испочетка. Временска сложеност наивног решења је квадратна.

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

static void zad1_inkrementalno()
{
    int n = int.Parse(Console.ReadLine());
    int[] zarade = new int[n];
    string[] linija = Console.ReadLine.Split(" ");
    zarade[0] = int.Parse(linija[0]);
    for (int i = 1; i < n; i++)
    {
        zarade[i] = zarade[i-1] + int.Parse(linija[i]);
    }
    int m = int.Parse(Console.ReadLine());
    while (m > 0) {
        linija = Console.ReadLine().Split();
        int i = int.Parse(linija[0]);
        int j = int.Parse(linija[1]);
        int zbir = zbir[j];
        if (i > 0) 
            zbir -= zbir[i-1];
        Console.WriteLine(zbir_segmenta(zarade, i, j));
        m--;
    }
}

Временска сложеност инкременталног алгоритма је линеарна. Приметимо да смо прво у линијама 6-10 променили репрезентацију података, тј. инкрементално смо израчунал збирове префикса. Затим у линијама 16-18 у константном времену одређујемо збир сегмента, чиме заправо убрзавамо алгоритам.

Задатак 2

У датом низу позитивних природних бројева наћи све сегменте (њихов почетак и крај) чији је збир једнак датом позитивном броју (бројање позиција почиње од нуле).

Улаз: У првој линији стандардног улаза налази се задати позитиван природни број $z$ који представља дати збир $0 < z < 10^6$ , у другој број елемената низа, $n$ ($2 \le n \le 50000$), а затим, у свакој од наредних $n$ линија стандардног улаза, по један елемент низа (позитиван природни број мањи од 200).

Излаз: У свакој линији стандардног излаза исписују се два броја (цели бројеви) одвојена празнином, који представљају индексе почетка и краја сегмента (бројано од нуле). Ако постоји више тражених сегмената њихове индексе исписати сортирано на основу левог краја.

Решење

Решење које директно следи из текста задатка је лако конструисати. Потребно је да одредимо збирове свих могућих сегмената и да издвојимо почетке и крајеве оних сегмената чији је збир једнак баш $к$. Дакле, потребно је одредимо све могуће почетке ($i$) и крајеве ($j$) сегмената ($0 \le i \le j < n$) и да за тако дефинисан сегмент одредимо његов збир $z = \sum_{k = i}^{j} a_k$. Ако је збир једнак траженом, приказаћемо почетак и крај сегмента. Описано решење је у наставку:

static int zbir_segmenta(int[] niz, int i, int j) 
{
    int z = 0;
    for (int k = i; i <= j; k++)
        z += niz[k];
    return z;
}
static void zad2_naivno(int[] niz, int k)
{
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i; j < niz.Length; j++)
        {
            int z = zbir_segmenta(niz, i, j);
            if (z == k)
            {
                Console.WriteLine("{0} {1}", i, j);
            }
        }
    }
}

Из досадашњег излагања, јасно је да неефикасност лежи у непотребном израчунавању збирова у свакој итерацији унутражње петље. Лако можемо да конструижемо инкрементално решење које је у наставку:

static void zad2_inkrementalno(int[] niz, int k)
{
    for (int i = 0; i < niz.Length; i++)
    {
        int z = 0;
        for (int j = i; j < niz.Length; j++)
        {
            z += niz[j];
            if (z == k)
            {
                Console.WriteLine("{0} {1}", i, j);
            }
        }
    }
}

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

Поред инкременталног решења, задатак можемо да решимо и применом збУвек крећемо од наивне идеје. Наивно, могли бисмо као и до сада да испитујемо све могуће сегменте. Дакле, у двострукој петљи ћемо фиксирати почетак ($i$) и крај сегмента ($j$) и потребно је само још да испитамо да ли тај сегмент испуњава дати услов, тј. да ли се може уредити у узастопни низ целих бројева.

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

Уместо тога, можемо да искористимо поставку задатка. Из поставке задатка знамо да је наш низ сачињен од различитих елемената, тј. нема дупликата. Знајући то, можемо да утврдимо да ли сегмент испуњава услове без сортирања. Потребно је да израчунамо опсег вредности у сегменту, односно да нађемо разлику највећег и најмањег елемента у сегменту. Ако је та разлика једнака дужини сегмента, онда је очигледно да такав сегмент можемо преуредити у растући низ узастопних бројева. Решење које користи ову идеју је у наставку.

static void zad2_zbirovi_prefiksa(int[] niz, int k)
{
    for (int i = 1; i < niz.Length; i++)
        niz[i] += niz[i-1];
    for (int i = 0; i < niz.Length; i++)
    {
        for (int j = i; j < niz.Length; j++)
        {
            int z = niz[j];
            if (i > 0)
                niz[j] -= niz[i-1];
            if (z == k)
            {
                Console.WriteLine("{0} {1}", i, j);
            }
        }
    }
}

Линије 3-4 израчунавају збирове префикса, док линије 9-11 одређују збир сегмента користећи збирове префикса. Временска сложеност решења које користи збирове префикса је такође $O(n^2)$.

Задатак 3

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

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

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

Решење

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

static int zbir_segmenta(int[] niz, int i, int j) 
{
    int z = 0;
    for (int k = i; i <= j; k++)
        z += niz[k];
    return z;
}
static int zad3(int[] niz)
{
    int max = int.MinValue;
    for (int i = 0; i < niz.Length; i++) 
    {
        for (int j = i; j < niz.Length; i++) 
        {
            int z = zbir_segmenta(niz, i, j);
            if (z > max)
            {
                max = z;
            }
        }
    }
    return max;
}

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

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

static int zad3_inkrementalno(int[] niz)
{
    int max = int.MinValue;
    for (int i = 0; i < niz.Length; i++) 
    {
        int z = 0;
        for (int j = i; j < niz.Length; i++) 
        {
            z = niz[j];
            if (z > max)
            {
                max = z;
            }
        }
    }
    return max;
}

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

Размотримо пажљивије шта је наш задатак. Елементе низа можемо да обележимо са $a_i$, а префиксне суме са $P_i = \sum_{0}^{i} a_i$. Тада, збир било ког сегмента можемо да одредимо као $S_{i,j} = P_j - P_{i-1}$. Наш задатак је да одредимо највећи збир неког сегмента датог низа. Прецизније, треба нам следеће:

$$\max_{i,j, i \le j} S_{i,j} = \max_{i,j, i \le j} P_j - P_{i-1}$$

С обзиром да тражимо максимум разлике, то значи за сваку вредност умањеника $P_j$, треба да изабереме најмању могућу вредност умањиоца $P_{i-1}$. Дакле, за сваки сегмент који се завршава на позицији $j$ морамо да знамо најмању могућу вредност од свих префикса који се завршавају на позицијама $i < j$. Као и збирове префикса, тако и најмањи збир префикса можемо да одржавамо инкрементално. Решење је у наставку:

static int zad3_optimalno(int[] niz)
{
    int zbir_prefiksa = 0;
    int min_zbir_prefiksa = 0;
    int max = int.MinValue;
    for (int i = 0; i < niz.Length; i++) 
    {
        zbir_prefiksa += niz[i];
        int zbir_segmenta = zbir_prefiksa - min_zbir_prefiksa;
        if (zbir_segmenta > max)
            max = zbir_segmenta;
        if (zbir_prefiksa < min_zbir_prefiksa)
            min_zbir_prefiksa = zbir_prefiksa;
    }
    return max;
}

Временска сложеност приказаног решења је линеарна, што је оптимална временска сложеност алгоритма који решава овај проблем.

Задатак 4

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

Улаз: У првој линији стандардног улаза налази се број постоља, $n$ ($3 \le N \le 50000$), а затим, у свакој од наредних $n$ линија стандардног улаза, број кутија на сваком постољу (природан број између $0$ и $100$).

Излаз: У једној линији стандарног излаза налази се цео број већи или једнак $0$ који представља највећи број кутија које можемо додати.

Решење

Пажљивом анализом задатка може се закључити следеће:

• Кутије не можемо да додајемо на прво и последње постоље, јер ћемо такву промену видети.
• Кутије можемо да додајемо само на унутрашња постоља.
• Да бисмо додали кутије на постоље $k$, тренутни број кутија мора бити мањи од максимума префикса $max_{pre}_k$, тј. свих бројева кутија на постољима испред позиције $k$. Такође, тај број мора бити мањи и од максимума суфикса низа $max_{suf}_k$, тј. свих бројева кутија на постољима испред позиције $k$.
• Ако је тренутни број кутија на позицији $k$ означен са $a_k$, тада број кутија које треба додати добијамо као $$\min \{ max_{pre}_k - a_k, max_{suf}_k - a_k\}.$$
• Да бисмо решили задатак потребно је само да саберемо све кутије које можемо додати на свакој позицији $k$, $1 \le k < n$.

Јасно је да наивно решење можемо добити тако што ћемо за сваку позицију $k$ у низу испочетка рачунати максимум префикса $max_{pre}_k = \max_{0 \le i < k} a_i$ и максимум суфиксаУвек крећемо од наивне идеје. Наивно, могли бисмо као и до сада да испитујемо све могуће сегменте. Дакле, у двострукој петљи ћемо фиксирати почетак ($i$) и крај сегмента ($j$) и потребно је само још да испитамо да ли тај сегмент испуњава дати услов, тј. да ли се може уредити у узастопни низ целих бројева.

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

Уместо тога, можемо да искористимо поставку задатка. Из поставке задатка знамо да је наш низ сачињен од различитих елемената, тј. нема дупликата. Знајући то, можемо да утврдимо да ли сегмент испуњава услове без сортирања. Потребно је да израчунамо опсег вредности у сегменту, односно да нађемо разлику највећег и најмањег елемента у сегменту. Ако је та разлика једнака дужини сегмента, онда је очигледно да такав сегмент можемо преуредити у растући низ узастопних бројева. Решење које користи ову идеју је у наставку. ену можемо да испитамо максимум и минимум префикса. Да бисмо то урадили, најлакше је да инкрементално израчунамо максимуме префикса и максимуме суфикса унапред. Максимуме префикса рачунамо по устаљеном поступку, сличном као када смо рачунали збирове префикса. Максимуме суфикса рачунамо на исти начин, само што се петљом крећемо од краја ка почетку низа. У наставку следи ефикасно инкрементално решење.

static int zad4(int[] niz)
{
    int[] maksimumiPre = new int[niz.Length]; // prefiksi
    int[] maksimumiPosle = new int[niz.Length]; // sufiksi
    int n = niz.Length;
    maksimumiPre[0] = niz[0];
    maksimumiPosle[n - 1] = niz[n - 1];
    for (int i = 1; i < n - 1; i++)
    {
        maksimumiPre[i] = Math.Max(niz[i], maksimumiPre[i-1]);
        maksimumiPosle[n-1-i] = Math.Max(niz[n-1-i], maksimumiPosle[n-i]);
    }
    int brKontejnera = 0;
    for (int i = 1; i < niz.Length - 1; i++)
    {
        int razlikaLevo = maksimumiPre[i] - niz[i];
        int razlikaDesno = maksimumiPosle[i] - niz[i];
        brKontejnera += Math.Min(razlikaDesno, razlikaLevo);
    }
    return brKontejnera;
}

Временске сложеност приказаног решења је линеарна. Кључно за постизање линеарне временске сложености је инкрементално израчунавање максимума префикса и максимума суфикса (линије 6-12). Поред тога, да би се постигла линеарна временска сложеност, неопходнo је одређивати број кутија које се могу наслагати на свакој позицији у константном времену (линије 14-19). Такође, треба приметити да просторна сложеност нашег решења није константна. У решењу користимо два помоћна низа чије величине линеарно зависе од величине улазног низа. Просторна сложеност приказаног решења је $О(n)$.

Задатак 5

Напиши програм који одређује највећи могући највећи заједнички делилац елемената низа ако је у низу допуштена замена тачно једног елемента произвољном вредношћу.

Улаз: Са стандардног улаза се учитава број $n$ ($3 \le n \le 10^5$), а затим у наредном реду $n$ природних бројева мањих од $10^12$.Увек крећемо од наивне идеје. Наивно, могли бисмо као и до сада да испитујемо све могуће сегменте. Дакле, у двострукој петљи ћемо фиксирати почетак ($i$) и крај сегмента ($j$) и потребно је само још да испитамо да ли тај сегмент испуњава дати услов, тј. да ли се може уредити у узастопни низ целих бројева.

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

Решење

У тексту задатка нам је речено да било који елемент низа можемо да заменимо било којим бројем. Од свих могућих бројева потребно је да текући број заменимо оним којим ће нам дати највећи могући НЗД низа. НЗД низа можемо да одредимо инкрементално, тј. ако знамо НЗД низа од $n-1$ елемената у ознаци $d_{n-1}$, тада НЗД целог низа $d_n$ можемо да одредимо као $d_n = \text{НЗД}(d_{n-1}, a_n)$. Одавде се лако закључује да највећи НЗД целог низа, не може бити већи од НЗД-а префикса, тј. $d_{n-1}$, па број којим можемо да заменимо елемент $a_n$ може бити управо $d_{n-1}$.

Да бисмо одредили највећи такав број, потребно је да редом избацујемо сваки елемент низа $a_i$ и да одредимо НЗД добијеног низа са $n-1$ елемената након избацивања елемента $a_i$. Наивно, НЗД модификованог низа бисмо сваки пут рачунали испочетка. Наивно решење је у наставку:

static int nzd(int x, int y)
{
    while (y != 0)
    {
        int tmp = x % y;
        x = y;
        y = tmp;
    } 
    return x;
}
static int zad5_naivno(int[] niz)
{
    int maxNzd = 0;
    for (int i = 0; i < niz.Length; i++)
    {
        int nzd_i = i == 0 ? niz[1] : niz[0];
        for (int j = 0; j < niz.Length; j++)
        {
            if (j != i)
                nzd_i = nzd(nzd_i, niz[j]);
        }
        maxNzd = Math.Max(maxNzd, nzd_i);
    }
    return maxNzd;
}

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

Из досадашњег искуства, лако можемо да закључимо да је разлог неефикасности изнова и изнова рачунање НЗД-а низа са сваком променом вредности параметра $i$. Да бисмо убрзали програм потребно је да елиминишемо унутрашњу петљу. То можемо лако да учинимо ако се вратимо на дефиницију НЗД-а.

Претпоставимо да је дат низ $\{a_0, a_1, \ldots, a_{n-1}\}$ од $n$ елемената и да желимо да елиминишемо елемент на позицији $i$. Потребно је да одредимо број којим треба заменити елемент $a_i$ тако да бисмо добили највећи могући НЗД полазног низа. Према досадашњој анализи, тај број ће бити једнак НЗД-у полазног низа без елемента $a_i$. С обзиром да НЗД можемо да рачунамо инкрементално, тражени НЗД бисмо могли врло лако да израчунамо када бисмо знали НЗД префикса $P_{i-1} = \text{НЗД}_{0 \le k \le i - 1} a_k$ и НЗД суфикса $S_{i+1} = \text{НЗД}_{i+1 \le k < n} a_k$. Тада ћемо НЗД низа без елемента $a_i$ одредити као $$\text{НЗД}(P_{i-1}, S_{i+1}).$$

Слично као у претходном задатку, инрекементално ћемо одредити НЗД префикса и НЗД суфикса низа уз помоћ којих ћемо елиминисати унутрашњу петљу. Инкрементално решење је у наставку.

static int[] zad4_inkrementalno(int[] niz)
{
    int n = niz.Length;
    int[] nzdPrefiks = new int[n];
    nzdPrefiks[0] = niz[0];
    for (int i = 1; i < n; i++)
        nzdPrefiks[i] = nzd(nzdPrefiks[i - 1], niz[i]);
    int[] nzdSufiks = new int[n];
    nzdSufiks[n - 1] = niz[n - 1];
    for (int i = n - 2; i >= 0; i--)
        nzdSufiks[i] = nzd(nzdSufiks[i], niz[i]);
    int maks_nzd = Math.Max(nzdPrefiks[n-2], nzdSufiks[1]);
    for (int i = 1; i < n - 1; i++)
    {
        maks_nzd = Math.Max(maks_nzd, nzd(nzdPrefiks[i - 1], nzdSufiks[i + 1]));
    }
    return maks_nzd;
}

Приметимо да у овом решењу користимо два помоћна низа чије су величине једнаке величини полазног низа. Због тога је просторна сложеност нашег инкременталног решења $О(n)$. Након што инкрементално израчунамо НЗД-ове префикса и суфикса, можемо ефикасно да одредимо тражени највећи НЗД у линијама 12-16. Приметимо да у линији 12 максимум низа иницијализујемо као већи од два НЗД-а: $P_{n-2}$ и $S_{1}$. Временска сложеност ефикасног алгоритма је $O(n \log n)$.

Задатак 6

У школи малих жутих мрава наставник је прегледао контролни задатак. Прво је прегледао ђаке који су радили групу $А$, а затим оне који су радили групу $Б$, средио је резултате за сваку групу и мраве поређао на основу броја поена који су освојили. Напиши програм који му помаже да од уређеног списка ученика који су радили задатке из групе $А$ и од уређеног списка ученика који су радили задатке из групе $Б$ добије јединствен уређен списак свих ученика.

Улаз: Са стандардног улаза се уноси број ђака $m$ који су радили групу $А$ ($5 \le m \le 25000$), а затим неопадајуће сортиран низ поена тих ђака (елементи су у једној линији, раздвојени са по једним размаком). Након тога се уноси број $n$ ђака који су радили групу $Б$ ($5 \le n \le 25000$), a затим неопадајуће сортиран низ поена тих ђака (елементи су у једној линији, раздвојени са по једним размаком).

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

Решење

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

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

Ако је један од низова празан, резултат обједињавања је други низ и његове елементе је потребно једноставно прекопирати у резултат. Ако низови нису празни, потребно је да искористимо чињеницу да су сортирани. Потребно је да користимо три бројача:

• $i$ - бројач у првом низу.
• $j$ - бројач у другом низу.
• $k$ - бројач у резултујућем низу.

Бројачи $i$ и $j$ показују на текуће елементе које разматрамо у полазним низовима, а бројач $k$ показује на прво слободно место у резултујућем низу. У сваком кораку петље, упоређујемо елементе прва два низа на које редом показују бројачи $i$ и $j$. Мањи од та два броја копирамо на позицију $k$ и увећавамо одговарајуће бројаче. Уколико је мањи био елемент првог низа увећавамо бројаче $i$ и $k$, а уколико је мањи био елемент другог низа увећавамо бројаче $j$ и $k$. Поступак настављамо све док у суфиксима оба низа постоји макар један елемент, тј. док је испуњен услов $i < m \land j < n$. На крају поступка остаје само да прекопирамо реп низа који је преостао.

Ефикасно решење засновано на техници два показивача дато је у наставку.

static int[] zad5(int[] niz1, int[] niz2)
{
    int[] rezultat = new int[niz1.Length + niz2.Length];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < niz1.Length && j < niz2.Length)
    {
        if (niz1[i] < niz2[j])
        {
            rezultat[k] = niz1[i];
            i++; k++;
        }
        else
        {
            rezultat[k] = niz2[j];
            j++; k++;
        }
    }
    while (i < niz1.Length)
    {
        rezultat[k++] = niz1[i++];
    }
    while (j < niz2.Length)
    {
        rezultat[k++] = niz2[j++];
    }
    return rezultat;
}

Временска сложеност обједињавања је $O(m+n)$, као и просторна, јер користимо помоћни низ у који преписујемо елементе полазних низова. Треба приметити да сви бројачи (“показивачи”) које користимо у задатку ($i,j,k$) све време иду у истом смеру, дакле испоштован је основни захтев технике два показивача.

Задатак 7

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

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

Излаз: На стандардни излаз исписати сортирани низ квадрата учитаних бројева (бројеви су раздвојени раз- мацима).

Решење

Задатак можемо директно да решимо тако што ћемо квадрирати све елементе низа и потом сортирати низ. Овакво решење ради у месту, тј. није нам потребна додатна меморија. Решење је у наставку:

static void zad7(int[] niz) {
    for (int i = 0; i < niz.Length; i++) 
    {
        niz[i] = niz[i]*niz[i];
    }
    Array.Sort(niz);
}

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

Задатак можемо да решимо и у линеарном времену. Нека је дат следећи низ:

$$-3 -1 0 1 2 4.$$

Резултат извршавања програма биће следећи низ:

$$0 1 1 4 9 16.$

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

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

static int nadji_prvi_nenegativan(int[] niz)
{
    for (int i = 0; i < niz.Length; i++)
    {
        if (niz[i] >= 0)
            return i;
    }
    return niz.Length;
}
static int[] zad6(int[] niz)
{
    int[] rezultat = new int[niz.Length];
    int prviNenegativan = nadji_prvi_nenegativan(niz);
    int prviNegativan = prviNenegativan - 1;
    int k = 0;
    while (prviNegativan >= 0 && prviNenegativan < niz.Length)
    {
        if (Math.Abs(niz[prviNegativan]) < niz[prviNenegativan])
        {
            niz[k] = niz[prviNegativan] * niz[prviNegativan];
            k++;
            prviNegativan--;
        }
        else
        {
            niz[k] = niz[prviNenegativan] * niz[prviNenegativan];
            k++;
            prviNegativan++;
        }
    }
    while (prviNegativan >= 0)
    {
        niz[k] = niz[prviNegativan] * niz[prviNegativan];
        k++;
        prviNegativan--;
    }
    while (prviNenegativan < niz.Length)
    {
        niz[k] = niz[prviNenegativan] * niz[prviNenegativan];
        k++;
        prviNegativan++;
    }
    return rezultat;
}

Први ненегативан број у полазном низу одређујемо линеарном претрагом у времену $O(n)$. Први ненегативан број у полазном низу се може одредити и применом бинарне претраге преломне тачке, што ће бити тема неког наредног часа. Сама конструкција резултујећег низа је заснована на техници два показивача. Треба приметити да сви бројачи који учествују у решењу се увек крећу у истом смеру, што је једна од главних карактеристика технике два показивача. Временска сложеност приказаног решења је $O(n)$. Просторна сложеност је такође $O(n)$.

Задатак 8

Три локалне продавнице продају различите производе. Сваки производ је окарактерисан јединственим бар- кодом (природним бројем мањим од милијарду). Ако су познати спискови производа који се продају у те три продавнице (сортирани растуће по бар-кодовима), напиши програм који одређује производе који се продају у све три продавнице.

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

Излаз: На стандардном излазу приказати бар-кодове производа који се продају у свакој од те три продавнице, уређене растући, сваки у посебном реду.

Решење

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

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

Једини начин како можемо додатно да убрзамо наше решење, јесте да у потпуности избацимо претрагу из решења. Да бисмо то постигли потребно је да искористимо чињеницу да су улазни низови сортирани. Дакле, за сваки низ нам треба по један бројач који ће чувати позицију елемента до ког смо стигли. Потребно је да истовремено померамо све бројаче у истом смеру све док не стигнемо до заједничког елемента. Заједнички елемент ћемо додати у резултујући низ и наставићемо пролазак кроз низове на исти начин.

С обзиром да не знамо колико заједничких елемената може бити у низу, можемо да користимо динамичке низове, тј. структуру података List<> која ће аутоматски прилагодити потребној величини. Додавање на крај листе је операција у константом времену, па неће утицати на временску сложеност нашег решења. Ефикасно решење је у наставку:

static int[] zad7(int[] niz1, int[] niz2, int[] niz3) 
{
    int i = 0;
    int j = 0;
    int k = 0;
    List<int> zajednicki = new List<int>();
    while (i < niz1.Length && j < niz2.Length && k < niz3.Length)
    {
        int max = Math.Max(niz1[i], Math.Max(niz1[j], niz3[k]));
        while (niz1[i] < max)
        {
            i++;
        }
        while (niz2[j] < max)
        {
            j++;
        }
        while (niz3[k] < max)
        {
            k++;
        }
        if (niz1[i] == niz2[j] && niz2[j] == niz3[k])
        {
            zajednicki.Add(niz1[i]);
            i++; j++; k++;
        }
    }
    return zajednicki.ToArray();
}

Временска сложеност приказаног решења је линеарна, тј. $O(n)$, а просторна сложеност је константна. Треба приметити да сви бројачи који учествују у решењу се увек крећу у истом смеру, што је једна од главних карактеристика технике два показивача.

Задатак 9

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

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

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

Решење

Проблем који треба да решимо се популарно назива двобојка и представља партиционисање полазног низа на две дисјунктне групе елемената који задовољавају неки услов. Важан услов у задатку је то што елементи након партиционисања не морају задржати полазни редослед.

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

static int[] zad9(int[] niz) 
{
    int[] rezultat = new int[niz.Length];
    int k = 0;
    for (int i = 0; i < niz.Length; i++) 
    {
        if (niz[i] % 2 == 0)
            rezultat[k++] = niz[i];
    }
    for (int i = 0; i < niz.Length; i++) 
    {
        if (niz[i] % 2 == 1)
            rezultat[k++] = niz[i];
    }
    return rezultat;
}

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

И просторну и временску сложеност можемо да снизимо. Да бисмо то постигли потребно је да искористимо услов задатка. У задатку експлицитно стоји да не морамо да сачувамо полазни редослед елемената, већ само треба да их прерасподелимо тако да прво иду сви парни, а затим сви непарни елементи низа.

То ћемо најлакше постићи тако што парне елементе можемо да ређамо од почетка низа, а непарне елементе можемо да ређамо од краја низа. Требају нам два бројача $l$ и $d$. Тиме ћемо направити следећу партицију низа:

• Елементи на позицијама $[0, l)$ су парни.
• Елементи на позицијама $[l, d]$ још нису испитани.
• Елементи на позицијама $(d, n-1]$ су непарни.

У сваком кораку петље потребне је да упоредимо елементе низа на позицијама $l$ и $d$ и да проверимо да ли су на одговарајућим местима у резултату. Ако је елемент на позицији $l$ паран, потребно је да увећамо бројач $l$. Ако је елемент на позицији $d$ непаран, тада треба да умањимо вредност бројача $d$. Ако било који од претходна два услова није испуњен, потребно је да размени вредности елемената на позицијама $l$ и $d$ и да ажурирамо бројаче.

Из описа поступка, јасно је да се ради о алгоритму конструисаном техником два показивача. Алгоритам је дат у наставку:

static void swap(int[] niz, int i, int j) 
{
    int tmp = niz[i];
    niz[i] = niz[j];
    niz[j] = tmp;
}
static void zad9(int[] niz) 
{
    int l = 0;
    int d = niz.Length - 1;
    while (l < d) 
    {
        if (niz[l] % 2 == 0)
            l++;
        else if (niz[i] % 2 != 0)
            d--;
        else
            swap(niz, l++, d--);
    }
}

Приметимо да решење засновано на техници два показивача не користи додатну меморију и да проблем решава у једном пролазу кроз низ. Временска сложеност ефикасног решења је $O(n)$, а просторна сложеност је $О(1)$, јер не користимо додатну меморију.

Задатак 10

Написати програм који учитава низ целих бројева а затим га трансформише тако да елементи буду подељени у три дела у зависности од задатих вредности $A$ и $B$. У првом делу су елементи мањи од задате вредности $A$ (вредности из интервала $[- \infty, A)$), у другом елементи већи или једнаки задатој вредности $A$ и мањи или једнаки задатој вредности $B$ (вредности из интервала $[A, B]$), а у трећем елементи већи од задате вредности $B$ (вредности из интервала $(B, + \infty )$). Није битно у ком се редоследу налазе елементи унутар делова.

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

Излаз: Исписати елементе резултујућег низа на стандардни излаз.

Решење

Проблем који треба да решимо се популарно назива холандска тробојка и представља партиционисање полазног низа на три дисјунктне групе елемената који задовољавају неке услов. Важан услов у задатку је то што елементи након партиционисања не морају задржати полазни редослед.

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

static int[] zad10(int[] niz, int a, int b) 
{
    int[] rezultat = new int[niz.Length];
    int k = 0;
    for (int i = 0; i < niz.Length; i++) 
    {
        if (niz[i] < a)
            rezultat[k++] = niz[i];
    }
    for (int i = 0; i < niz.Length; i++) 
    {
        if (a <= niz[i] && niz[i] <= b )
            rezultat[k++] = niz[i];
    }
    for (int i = 0; i < niz.Length; i++) 
    {
        if (niz[i] > b)
            rezultat[k++] = niz[i];
    }
    return rezultat;
}

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

Решење можемо да убрзамо тако што ћемо два пута применити алгоритам из прошлог задатка, тј. двобојку. У првом пролазу бисмо направили партицију низа око вредности $A$ и затим бисмо тако трансформисани низ поново партиционисали око вредности $B$. На тај начин бисмо задатак решили у два пролаза, са консантом меморијском сложеношћу. Међутим, проблем је могуће решити и у само једном пролазу и ради се о модификацији идеје из задатка двобојка.

Алгоритам који решава проблем тробојке у једном пролазу је осмислио Дајкстра. Требају нам три бројача $l$, $i$ и $d$. Тиме ћемо направити следећу партицију низа:

• Елементи на позицијама $[0, l)$ су парни.
• Елементи на позицијама $[l, i)$ су парни.
• Елементи на позицијама $[i, d)$ још нису испитани.
• Елементи на позицијама $(d, n-1]$ су непарни.

У сваком кораку петље потребне је да упоредимо елемент низа на позицији $i$ са вредностима $A$ и $B$. Ако је елемент на позицији $i$ мањи од вредности $A$, тада размењујемо вредности елемената на позицијама $i$ и $l$ и увећавамо оба бројача. Ако је елемент на позицији $i$ мањи или једнак од вредности $B$, тада се налази на исправном месту и само увећавамо вредност бројача $i$. Ако ниједан од ова два услова нису испуњени, тада размењујемо вредности елемената низа на позицијама $i$ и $d$ и умањујемо вредност бројача $d$.

Из описа поступка, јасно је да се ради о алгоритму конструисаном техником два показивача. Алгоритам је дат у наставку:

static void swap(int[] niz, int i, int j) 
{
    int tmp = niz[i];
    niz[i] = niz[j];
    niz[j] = tmp;
}
static void zad10(int[] niz, int a, int b) 
{
    int i = 0;
    int l = 0;
    int d = niz.Length - 1;
    while (l < d) 
    {
        if (niz[l] << A)
            swap(niz, i++, l++);
        else if (niz[i] <= b)
            i--;
        else
            swap(niz, i, --d);
    }
}

Приметимо да решење засновано на техници два показивача не користи додатну меморију и да проблем решава у једном пролазу кроз низ. Временска сложеност ефикасног решења је $O(n)$, а просторна сложеност је $О(1)$, јер не користимо додатну меморију.