Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Mali uvod u efikasnost

Такмичарски задаци

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

Хлебови

Сваки човек носи два хлеба, жена један, а дете пола хлеба. Укупно их је \(n\), и носе \(n\) хлебова. Написати програм који учитава природан број \(n\) (\(1 \leq n \leq 2~000~000~000\)) и исписује колико има решења за број људи, жена и деце.

Пример: за \(n = 5\) иписати \(2\)

Објашњење: постоје 2 решења, и то: (1, 2, 2) и (0, 5, 0).

Означимо број људи, жена и деце редом са \(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\) књига и позната је ширина сваке од њих у милиметрима. Она рукама хвата одређени низ књига са прве полице које се налазе једна до друге и све заједно их одједном пребацује на другу полицу, при чему жели да пребаци књиге тако да јој попуне другу полицу од ивице до ивице. У првој линији стандардног улаза налази се природан број \(z\) (такав да је \(1 \leq z \leq 10^6\)), који представља ширину друге полице. У другој се налази број књига на првој полици \(n\) \((2 \leq n \leq 5 \dot 10^5)\), а у трећој ширине књига на првој полици (позитивни природни бројеви мањи од 100), раздвојени размаком.

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

Пример

Улаз:

125

10

35 40 25 50 50 50 25 35 15 35

Излаз:

2

4

5

Објашњење примера: Ако крене књиге број 2, пренеће 25+50+50. Ако крене од књиге број 4, пренеће 50+50+25. Ако крене од књиге број 5, пренеће 50+25+35+15.

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

Када почнемо да анализирамо ефикасност овог решења, одмах уочавамо да број извршених операција не зависи само од броја књига 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. године.

Државна комисија треба да одреди праг за пролазак такмичара са окружног на државно такмичење. Пошто је информатика постала обавезан предмет у основним школама, број такмичара је јако велики. Администраторку Мају која одржава табелу са резултатима стално питају који би број такмичара прошао даље када би праг пролазности био толико и толико поена (даље се пласирају сви ученици чији је број поена већи или једнак прагу). Одлучила је да напише програм који даје одговор на та питања. Са стандардног улаза учитава се број такмичара \(n\) \((1 \leq n \leq 50000)\), а затим и поени такмичара (природни бројеви), задати у сортираном редоследу од највећег до најмањег и раздвојени размацима. Након тога се учитава број \(m\) \((1 ≤ m ≤ 50000)~\) који представља број питања на која Маја треба да одговори, а затим и \(m\) бројева раздвојених размацима за које је потребно дати одговор колико би се такмичара пласирало када би се тај број узео за праг. На стандардни излаз исписати тражене бројеве такмичара који су се пласирали, у посебном реду за сваки праг.

Пример:

Улаз:

5

89 73 73 56 23

4

95 50 70 5

Излаз:

0

4

3

5

Објашњење:

ако је праг 95 поена, нико се није пласирао (исписује се 0)

ако је праг 50 поена, пласирали су се такмичари са освојених 89, 73, 73 и 56 поена (исписује се 4)

ако је праг 70 поена, пласирали су се такмичари са освојених 89, 73 и 73 поена (исписује се 3)

ако је праг 5 поена, сви су се такмичари пласирали (исписује се 5)

Напомена: У бар 15 од 20 тест примера, бројеви \(m\) и \(n\) ће бити мањи од 200.

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

Одредимо сложеност алгоритма. Број операција у овом алгоритму је највећи ако су сви такмичари изнад сваког прага. Овај „најнеповољнији” случај (у смислу броја операција алгоритма, наравно) се једноставно анализира. Наредбе у двострукој петљи се извршавају \(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. године.

Вредност акција једне компаније варирала је из дана у дан током једног дужег временског периода. Напиши програм који одређује колико има низова узастопних дана у којима је укупан збир промена вредности акција једнак датом броју \(z\). Са стандардног улаза се у првој линији уноси тај број \(z\) (цео број између -10000 и 10000), затим, у наредној линији број дана \(n\) у којима се пратила промена вредности акција \((3 \leq n \leq 50000)\) и затим у нареднoj линији промене за сваки од дана у односу на претходни дан (цели бројеви између -100 и 100) раздвојени размацима. На стандардни излаз испиши број периода у којима је укупна промена једнака \(z\) (тј. броја непразних сегмената низа промена чији је збир једнак \(z\)).

Пример

Улаз

11

10

1 2 3 5 1 -1 1 5 3 2

Излаз

7

Објашњење: следећи сегменти имају збир 11: [1 2 3 5], [1 2 3 5 1 -1], [2 3 5 1], [2 3 5 1 -1 1], [5 1 -1 1 5], [1 -1 1 5 3 2, 1 5 3 2]

Наивно решење овог задатка је врло слично оном из задатка књиге: од сваког места у низу промена почињемо са сабирањем и повећавамо бројач низова дана за 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 елемената више него довољно брзо.