Хлебови¶

Означимо број људи, жена и деце редом са \(c\), \(z\), \(d\). Из поставке задатка добијамо систем једначина: \(c + z + d = n~\), \(2c + z + d / 2 = n\). Траже се решења у облику уређених тројки \((c, z, d)\), где су сва три броја цела и ненегативна.

Одузимањем једне једначине од друге добија се \(d = 2c\), а уврштавањем у било коју од полазних једначина добијамо \(3c + z = n\).

Сада се види да је скуп свих решења \(\{(k, n-3k, 2k) : k \in N, 0 \leq k \leq {n \over 3}\}\). Пошто \(k\) може да узме укупно \(1 + \lfloor {n \over 3} \rfloor\) вредности, толико има и решења. Програм написан по овој идеји је једноставан:

Како се програм састоји од фиксног броја операција, сложеност је \(O(1)\) и време рада не зависи од величине улазног податка. Тачан број операција није битан (битно је само да се не мења), а он зависи од тога шта све бројимо као засебну операцију.

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

Књиге¶

Овај задатак се појавио на окружном такмичењу 2018 године за ученике осмог разреда под називом „Кофери”, а затим исте године на државном такмичењу за ученике петог и шестог разреда под називом „Књиге” (промењен је текст задатка, а пример у тексту, тест примери и решење су исти).

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

Једна очигледна идеја (такозвано „наивно” решење) је да се од сваке књиге почне са сабирањем ширина, и да се сабира док се не добије ширина већа или једнака ширини друге полице (или док се не дође до краја низа књига ако се не достиже ширина друге полице).

Када почнемо да анализирамо ефикасност овог решења, одмах уочавамо да број извршених операција не зависи само од броја књига n, него и од ширина тих књига. Да се анализа не би закомпликовала, уобичајено је да се подразумева најгори случај (енгл. worst case analysis). Уосталом, ако желимо да програм ради довољно брзо у сваком случају, онда треба да ради довољно брзо и у најнеповољнијем случају. У нашем задатку то значи да у анализи претпоставимо да књиге нису довољно широке и да ће се при сабирању од сваке позиције ићи до краја низа. Приближно исти број операција се добија и ако се сабирањем стигне до ширине друге полице пред крај низа.

Са овом претпоставком, наредбе у двострукој петљи се извршавају укупно \(n+(n-1)+...+3+2+1 = {n \cdot (n+1) \over 2} = O(n^2)\) пута, па је алгоритам квадратне сложености. С обзиром да то ограничење за број књига \((2 \leq n \leq 5 \cdot 10^5)\), алгоритму квадратне сложености је потребно време од неколико секунди, а можда и минута (види табелу). Како је уобичајено дозвољено време по тесту често испод секунде, видимо да ред величине потребног времена није одговарајући и да ово решење није довољно брзо за све могуће ситуације. Како доћи до бржег решења?

Замислимо да смо сабирајући од позицијe \(i\) стигли до позиције \(j\). Означимо суму \(a_i + a_{i+1} + ... + a_j\) са \(S_{i,j}\), где је \(a\) низ ширина књига. Претпоставимо да је \(j\) такво да је \(S_{i,j} < z~\), а да је \(S_{i,j+1} \geq z~\) (\(z\) је ширина друге полице). Дакле, управо смо завршили са провером свих интервала који почињу на позицији \(i\), а које је вредело проверавати (преостали интервали који почињу на позицији \(i\), а са крајем после позиције \(j\) имају још већи збир и не могу бити одговарајући). Сада нас интересују интервали који почињу на позицији \(i+1\). Како је \(S_{i+1,j} < a_i + S_{i+1,j} = S_{i,j}~\) (елементи низа \(a\) су позитивни) и \(S_{i,j} < z~\) (по претпоставци), закључујемо да ће бити и \(S_{i+1,j} < z~\). То значи да је први интервал који почиње на позицији \(i+1~\), а који вреди проверавати, интевал \([i, j+1]\) (сви пре њега имају премали збир). Тако долазимо до следеће идеје:

• ако је текући збир мањи од \(z~\), \(S_{i,j} < z~\), повећавамо десну границу интервала, као што смо и пре радили
• ако је текући збир већи или једнак \(z~\), \(S_{i,j} \geq z~\), повећавамо леву границу интервала, а десна остаје тамо где је и била

Ево и програма написаног по тој идеји (не саветујемо да тестирате ефикасност у овом окружењу):

Која је сложеност овог алгоритма? Да бисмо одговорили на питање, приметимо следеће:

• При сваком проласку кроз петљу повећава се један од индекса \(i\), \(j\), а ни један од њих се никад не смањује током извршавања алгоритма
• \(i~\) не може постати веће од \(j\), јер ако се икад и изједначе, тада је текући збир интервала једнак 0, па ће се повећавати прво \(j\).
• Из петље се излази кад \(j\) стигне до \(n\).

Одавде се може закључити да се кроз петљу пролази највише \(2n\) пута, па је сложеност алгоритма \(O(n)\).

Праг¶

Задатак је са окружног такмичења 2018. године.

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

Одредимо сложеност алгоритма. Број операција у овом алгоритму је највећи ако су сви такмичари изнад сваког прага. Овај „најнеповољнији” случај (у смислу броја операција алгоритма, наравно) се једноставно анализира. Наредбе у двострукој петљи се извршавају \(m \cdot n\) пута, па је сложеност алгоритма \(O(m \cdot n)\). Како је у поставци задатка речено да вредности \(m\) и \(n\) могу бити до 50000, за овај алгоритам нам је потребно реда \(50~000^2 = 2~500~000~000\) операција. Чак и уз милијарду операција у секунди, то је две и по секунде, што је превише у односу на уобичајено дозвољено време (види напомену на крају овог дела). Може ли брже?

Брже решење доноси бинарна претрага (то је техника која се посебно учи, не очекује се од решавача задатака да ово што следи смисле када виде задатак). Пошто готове Пајтон функције које раде бинарну претрагу очекују листу сортирану растуће, најпре ћемо да обрнемо листу поена (први елемент иде на последње место, други на претпоследње итд.) методом reverse(). Након тога, за сваки праг позовемо функцију bisect.bisect_left(), која бинарном претрагом проналази индекс \(k\) првог (крајњег левог) елемента већег или једнаког прагу. Тада је број елемената листе који су мањи од прага једнак \(k\) (пошто се индекси броје од нуле), а број елемената који су већи или једнаки прагу који нама треба је \(n-k\). Ево и програма:

Одредимо сада сложеност и за ово решење:

• За учитавање и формирање листе поена треба \(O(n)\) времена.
• За обртање листе у четвртом реду потребно је \(O(n)\) времена.
• За учитавање прагова треба \(O(m)\) времена.
• Функција bisect.bisect_left() се позива \(m\) пута, а при сваком извршавању јој је потребно \(O(Lg(n))\) времена, што је укупно \(O(m \cdot Lg(n))\) времена.

Када саберемо све делове, добијамо да је сложеност целог програма \(O(m) + O(n) + O(m \cdot Lg(n))\). Ради лакшег изражавања можемо увести ознаку \(N = max(m, n)\). Сада сложеност можемо да изразимо као \(O(N) + O(N \cdot Lg(N))\), односно \(O(N \cdot Lg(N))\), јер се линеарно време утапа у ен-лог-ен, које доминира по броју операција и зато одређује укупну сложеност.

Акције¶

Задатак је са државног такмичења 2018. године.

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

Сложеност је очигледно одређена бројем извршавања наредби у дрвострукој петљи. Те наредбе се (као и у задатку „Књиге”) извршавају \(n+(n-1)+...+3+2+1 = {n \cdot (n+1) \over 2} = O(n^2)\) пута. Како низ може имати до 50000 елемената, поново имамо ситуацију да алгоритам квадратне сложености није прихватљив.

Покушајмо да дођемо до решења у једном пролазу кроз низ. Пошто у једном пролазу не можемо да сабирамо почев од сваког елемента, искористићемо честу идеју да се збир елемената интервала \([i, j]\), означен са \(S_{i,j} = x_i + x_{i+1} + ... + x_j\), може изразити као \(S_{i,j} = S_{0,j} - S_{0, i-1}~\) (овде је \(x\) дати низ промена вредности акција). Ово значи да ће нам бити потребно да за сваку претходну вредност збира \(S_{0,k}\) памтимо да ли се и колико пута појавила, да бисмо могли да утврдимо да ли има сегмената низа који се завршавају на текућој позицији и имају тражени збир. У ту сврху најбоље је користити речник, помоћу њега можемо једноставно да бројимо претходна појављивања збирова од почетка низа. Преостаје да у проласку кроз низ при свакој новој вредности збира \(S\) који рачунамо, проверимо колико пута се претходно појавио збир \(S-Z\), јер толико има нових сегмената са траженим збиром \(Z\).

Појаснимо још један детаљ у програму који следи, а тиче се више синтаксе Пајтона: ако неког кључа K нема у речнику R, писање R[K] би довело до грешке у извршавању програма. Зато постоји метода get, која омогућава да осим кључа наведемо и подразумевану вредност P, која ће бити враћена ако кључа нема у речнику: R.get(K, P). У конкретном случају, ако се неки збир није појављивао, он није ни уписан у речник као кључ, али ако питамо за број појављивања тог збира, желимо да добијемо 0 као одговор. Зато је други аргумент у позивима методе get једнак 0.

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