# \[Rešenja zadataka\] Kvalifikacije 2018 - Treći krug

**URL:** <https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165>\
**Category:** Algoritam\
**Created:** [February 25, 2018, 2:59am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165 "2018-02-25T02:59:31Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![ivan100sic](https://algora.petlja.org/user_avatar/algora.petlja.org/ivan100sic/32/192_2.png) [@ivan100sic](https://algora.petlja.org/u/ivan100sic)\
**Post date:** [February 25, 2018, 2:59am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/1 "2018-02-25T02:59:31Z")

</div>

Takmičarsko okruženje i tekstovi zadataka nalaze se [ovde](https://arena.petlja.org/Competitions/Competition/188).

---

<div class="post-metadata">

**Author:** ![ivan100sic](https://algora.petlja.org/user_avatar/algora.petlja.org/ivan100sic/32/192_2.png) [@ivan100sic](https://algora.petlja.org/u/ivan100sic)\
**Post date:** [February 25, 2018, 3:01am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/2 "2018-02-25T03:01:45Z")

</div>

## Задатак 1 - Зечеви

Аутор, текст и тест примери: Иван Стошић  
Анализа решења: Иван Стошић  
Тестер: Душан Здравковић

Учитамо висине три зеца и уредимо их у неопадајући редослед. Добијамо три броја b\_1 \leq b\_2 \leq b\_3. Посматрајмо разлике d\_1 = b\_2 - b\_1 и d\_2 = b\_3 - b\_2. Уколико су ове разлике једнаке, могуће је наћи решење, то је број b\_3 + d\_2 и он заједно са остала три чини аритметичку прогресију. И број b\_1 - d\_1 такође чини аритметичку прогресију са остала три броја али овај број може бити мањи или једнак нули, док претходно наведени b\_3 + d\_2 не може, јер је већи или једнак од b\_3 који је природан број. Даље, уколико је d\_1 = 2 d\_2, односно, уколико је разлика другог и првог броја дупло већа од разлике трећег и другог броја, можемо додати нови број између прва два, а то је број b\_1 + d\_2, и он са осталима чини аритметичку прогресију. Ако је пак d\_2 = 2 d\_1 можемо додати број b\_2 + d\_1 и он ће са преостала три чинити аритметичку прогресију. Ако ниједан од ових услова није испуњен, такав број не постоји.

---

<div class="post-metadata">

**Author:** ![ivan100sic](https://algora.petlja.org/user_avatar/algora.petlja.org/ivan100sic/32/192_2.png) [@ivan100sic](https://algora.petlja.org/u/ivan100sic)\
**Post date:** [February 25, 2018, 3:04am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/3 "2018-02-25T03:04:01Z")

</div>

## Задатак 2 - Најближи неопадајући

Аутор, текст и тест примери: Владимир Миловановић  
Анализа решења: Владимир Миловановић  
Тестер: Иван Стошић

## Анализа

Потребно је приметити да провера да ли је одређени број неопадајући не зависи линеарно од вредности тог броја, већ од броја његових цифара који је за природне бројеве у декадном запису пропорционалан \log\_{10}N.

Идејно најједноставније решење највероватније је да се крене од задатог броја N и редом проверава да ли је неопадајући или не, тако што ће се најпре испитати сам задати број N, затим N\pm1, па N\pm2 и тако даље.

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

Да би се одредио најближи неопадајући број већи од задатог броја, најпре у низу цифара унетог броја почевши од цифре највећег значаја треба пронаћи прво место где низ постаје опадајући, односно две суседне цифре за које важи c\_{i} \> c\_{i-1}, а затим све цифре у опсегу од c\_{0} до c\_{i-1} променити у c\_{i}. Тако ће на пример број N=12321 бити преправљен у 12333, а самим тим и одређен најближи неопадајући број већи од задатог броја.

Слично томе, како би се одредио најближи неопадајући број мањи од задатог броја, прво се на исти начин пронађе монотоно неопадајући префикс броја N, потом c\_{i} умањи за један, а цифре у опсегу од c\_{0} до c\_{i-1} промене у 9. За горњи пример N=12321 то значи да ће најближи неопадајући број мањи од задатог броја бити 12299. Треба обратити пажњу да декрементирање последње цифре префикса може проузроковати промену његове монотоности, као на пример код N=12345554321, па најближи неопадајући број неће бити 12345549999, ни 12345499999, већ 12344999999. Узимајући и тај случај у обзир долази се до најближег неопадајућег броја који је мањи од задатог.

Уз напомену да је временска сложеност проналаска најближег неопадајућег броја линеарна по дужини низа цифара, односно логаритамска по вредности задатог броја N, преостаје само да се провери који је од два неопадајућа броја ближи, и да се исти испише, чиме је задатак урађен у \mathcal{O}(\log{N}) временској сложености.

---

<div class="post-metadata">

**Author:** ![ivan100sic](https://algora.petlja.org/user_avatar/algora.petlja.org/ivan100sic/32/192_2.png) [@ivan100sic](https://algora.petlja.org/u/ivan100sic)\
**Post date:** [February 25, 2018, 3:06am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/4 "2018-02-25T03:06:53Z")

</div>

## Задатак 3 - Струја

Аутор: Никола Јовановић  
Текст и тест примери: Димитрије Ердељан  
Анализа решења: Димитрије Ердељан  
Тестер: Никола Јовановић

Ако оптимално тргујемо струјом, сигурно ћемо сваког дана или “чекати”  
(без куповине и продаје), или потрошити сав новац на струју, или  
продати сву струју коју имамо. Ово тврђење неће бити формално доказано  
овде, али идеја иза њега је да ако “раздвојимо” новац (или струју) и  
потрошимо само део, потрошен и сачуван део се могу посматрати  
независно. Ако потрошен део новца доноси бољу зараду од непотрошеног,  
боље је да потрошимо све (и обрнуто).

Сада је потребно само одабрати дане када ћемо куповати и продавати  
струју. Оптималан избор је да купујемо у локалним минимумима цене,  
односно данима када је струја јефтинија него што је била јуче и него  
што ће бити сутра, и да продајемо у локалним максимумима (кад је  
скупља од суседних дана). Да бисмо доказали да је ово оптимално,  
посматрајмо било који други избор дана. Тада сигурно можемо “померити"  
ону куповину (или продају) која није локални минимум (максимум) на  
"суседни” дан када је цена повољнија и зарадити више.

Локалне минимуме и максимуме можемо наћи у \mathcal{O}(N) (за сваки  
дан гледамо само два суседа), тако да се цео задатак може решити у  
\mathcal{O}(N). Обратите пажњу на први и последњи дан – пошто имају  
само једног суседа, можемо их или посматрати као специјалне случајеве,  
или додати “вештачке” елементе за дане 0 и N+1, са ценама \infty и  
-\infty.

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

---

<div class="post-metadata">

**Author:** ![ivan100sic](https://algora.petlja.org/user_avatar/algora.petlja.org/ivan100sic/32/192_2.png) [@ivan100sic](https://algora.petlja.org/u/ivan100sic)\
**Post date:** [February 25, 2018, 3:08am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/5 "2018-02-25T03:08:44Z")

</div>

## Задатак 4 - Плус минус

Аутор, текст и тест примери: Драган Урошевић  
Анализа решења: Драган Урошевић  
Тестер: Никола Јовановић

## Анализа

Означимо са s\_k збир првих k елемената низа, тј. s\_k = \sum\_{i=1}^k x\_k, \ \ \ \ k=0, 1, 2, ..., n.  
Зваћемо ове збирове парцијалне суме.  
Лако се закључује да је збир елемената ед елемента на позицији i до елемента на позицији j једнак

x\_i + x\_{i+1} + ... +x\_{j-1} + x\_j = s\_j - s\_{i-1}.

Ако је збир елеманата од елемента на позицији i до елемента на позицији j позитиван, онда је s\_j-s\_{i-1} \> 0, односно s\_{i-1} \< s\_j. Ако је збир елеманата од елемента на позицији i до елемента на позицији j негативан, онда је s\_j-s\_{i-1} \< 0, односно s\_{j} \< s\_{i-1}.

Формираћемо оријентисан граф G=(V,E) у коме чворови одговарају парцијалним сумама (можемо чворове нумерисати и бројевима између 0 и n). За сваку неједнакост облика s\_a \< s\_b уводимо ивицу од чвора који одговара парцијалној суми s\_a до чвора који одговара парцијалној суми s\_b. Ако у том графу постоји петља, онда не постоји низ који задовољава задате услове. Наиме, петља је низ чворова у коме се први и последњи чвор поклапају такав да између свака два узастопна постоји ивица. Нека тај низ чине чворови

s\_{k\_1}, s\_{k\_2}, s\_{k\_3}, ..., s\_{k\_c}, s\_{k\_1}.

Тада за парцијалне суме важи

s\_{k\_1} \< s\_{k\_2} \< s\_{k\_3} \< ..., \<s\_{k\_c} \< s\_{k\_1} 

и због транзитивности је s\_{k\_1} \< s\_{k\_1} , што је контрадикција.

Ако у графу G не постоји циклус, чворови графа се могу поређати у низ тако да ако постоји ивица од чвора s\_a до чвора s\_b онда је чвор s\_a стоји у низу пре чвора s\_b. Свако такво ређање у низ се назива тополошко сортирање и може се обавити варијацијом на обилазак графа у дубину. На основу тог набрајања чворова, парцијалним сумама (чворовима графа) можемо доделити целе бројеве, тако да се чвору s\_0 додели вредност 0, чворовима који се налазе после њега у том набрајању редом бројеви 1, 2, 3, ... (у складу са поретком у набрајању), а чворовима који се налазе пре њега редом бројеви -1, -2, -3, ... (овај пут сдесна улево, у складу са набрајањем). Лако се уверавамо да ће за свака два чвора s\_a и s\_b важити да ако је s\_a пре (лево) од s\_b у набрајању, онда је s\_a \< s\_b. Другим речима, парцијалним сумама смо доделили различите целе бројеве и они задовољавају све неједнакости које су задате у улазним подацима.  
На основу парцијалних сума се могу одредити елементи низа:

x\_i = s\_i - s\_{i-1},\ \ \ \ i = 1, 2, ..., n.

## Смернице за алгоритам

Дајемо само псеудокод за топошко сортирање (набрајање). Претпостављамо да је граф репрезентован помоћу вектора/листи суседа својих чворова. Резултат који враћа функција је 0, ако граф јесте ацикличан (поред тога је у низу `tops` његово тополошко сортирање), a 1, ако је граф има бар једну петљу и самим тим не постоји тополошко сортирање.

```auto
topsort() {
	p = n;
	for (i = 0; i <= n; i++)
		mark[i] = BEO
	for (i = 0; i <= n; i++) 
		if (mark[i] == BEO)
			if (topsortr(i) != 0) return 1;
	return 0;
}
topsortr(i) {
	mark[i] = SIV;
	for (k = 0; k < susedi[i].size(); k++) {
		  j = susedi[i][k];
		  if (mark[j] == SIV) return 1;
		  if (mark[j] == BEO)
			  if (topsortr(j) != 0) return 1;
	}
	tops[p] = i;
	p = p - 1;
	mark[i] = CRN;
	return 0;
}

```

---

<div class="post-metadata">

**Author:** ![ivan100sic](https://algora.petlja.org/user_avatar/algora.petlja.org/ivan100sic/32/192_2.png) [@ivan100sic](https://algora.petlja.org/u/ivan100sic)\
**Post date:** [February 25, 2018, 3:10am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/6 "2018-02-25T03:10:29Z")

</div>

## Задатак 5 - Преписивање

Аутор, текст и тест примери: Душан Здравковић  
Анализа решења: -  
Тестер: Иван Стошић

---

<div class="post-metadata">

**Author:** ![mushisgosuuu](https://algora.petlja.org/user_avatar/algora.petlja.org/mushisgosuuu/32/663_2.png) [@mushisgosuuu](https://algora.petlja.org/u/mushisgosuuu)\
**Post date:** [February 27, 2018, 11:45am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/7 "2018-02-27T11:45:43Z")

</div>

Kada ce resenje za 5. zadatak biti okaceno?

---

<div class="post-metadata">

**Author:** ![DuX](https://algora.petlja.org/user_avatar/algora.petlja.org/dux/32/57_2.png) [@DuX](https://algora.petlja.org/u/DuX)\
**Post date:** [February 27, 2018, 12:08pm UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/8 "2018-02-27T12:08:43Z")

</div>

U toku ove nedelje sigurno, a nadam se vrlo uskoro 🙂

---

<div class="post-metadata">

**Author:** ![allllekssssa](https://algora.petlja.org/letter_avatar_proxy/v4/letter/a/5e9695/32.png) [@allllekssssa](https://algora.petlja.org/u/allllekssssa)\
**Post date:** [May 21, 2018, 8:55pm UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/9 "2018-05-21T20:55:05Z")

</div>

Rešenje je napisano još “one nedelje”, samo što su slova obojena u belo i post je vešto sakriven na Algori.

---

<div class="post-metadata">

**Author:** ![TadijaSebez](https://algora.petlja.org/user_avatar/algora.petlja.org/tadijasebez/32/421_2.png) [@TadijaSebez](https://algora.petlja.org/u/TadijaSebez)\
**Post date:** [May 22, 2018, 12:48pm UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/10 "2018-05-22T12:48:11Z")

</div>

Ako komisija ne moze da oboji slova u neku drugu boju, ja cu napisati svoje resenje u toku ove nedelje sigurno, a nadam se vrlo uskoro 🙂

---

<div class="post-metadata">

**Author:** ![allllekssssa](https://algora.petlja.org/letter_avatar_proxy/v4/letter/a/5e9695/32.png) [@allllekssssa](https://algora.petlja.org/u/allllekssssa)\
**Post date:** [May 22, 2018, 1:20pm UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/11 "2018-05-22T13:20:30Z")

</div>

Bilo bi lepo da napišeš svoju ideju, verujem da bi mnogima bila korisna !

Naravno nadam se da će @DuX isto uraditi, kao i da če skorije biti objavljena rešenja svih zadataka sa SIO.

---

<div class="post-metadata">

**Author:** ![TadijaSebez](https://algora.petlja.org/user_avatar/algora.petlja.org/tadijasebez/32/421_2.png) [@TadijaSebez](https://algora.petlja.org/u/TadijaSebez)\
**Post date:** [May 27, 2018, 10:29am UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/12 "2018-05-27T10:29:40Z")

</div>

**Преписивање**

**Подзадатак 1**

Сложеност O(K\sum\_{i=1}^{N} S\_{i}).  
За сваку рунду треба имати листу такмичара који су на њој преписивали. Сваки упит решавамо тако што кренемо од почетне рунде и бројимо оне такмичаре које смо први пут ухватили.

**_Offline_ решење**

Потребно нам је сегментно стабло. Да би решили све упите којима је почетна рунда S за сваког такмичара који је преписивао на некој од рунди иѕ сегмента [S,R] треба да на вредност прве рунде на којој ће бити ухваћен додамо 1. Да би ефикасно изградили структуру треба да решавамо прво све упите са S=R па S=R-1 итд. Када је S=R вредност R у стаблу биће једнака броју људи који су преписивали на тој рунди. За остале S није довољно само поставити вредност на број људи који су преписивали на тој рунди већ морамо и да смањимо вредност неких од следећих рунди. Ако је такмичар X преписивао на тренутној рунди и на некој од следећих треба да смањимо вредност следеће рунде на којој је преписивао. Овако у сваком кораку имамо описано сегментно стабло. Упите решавамо бинарном претрагом по решењу уз помоћ сегментног стабла. Сложеност овог алгоритма је O(Klog^2R).

**Подзадатак 2**

Овај подзадатак се решава тако што уместо обичног сегментног стабла користимо _persistent segment tree_. Тако можемо приступити претходним верзијама сегментног стабла и после целе изградње. Временска сложеност остаје O(Klog^2R) а меморијска се повећава на O((\sum\_{i=1}^{N} S\_{i})logR).

**Подзадатак 3**

Овај подзадатак захтева више размишљања. Потребно је смањити сложеност _Offline_ решења са O(Klog^2R) на O(KlogR). Приметимо да сегментно стабло већ има израчунате вредности за неке сегменте. То можемо користити уместо бинарне претраге. Започнимо рекурзивну алгоритам у корену стабла. Ако је вредност левог сегмента већа или једнака броју такмичара које члан комисије треба да ухвати померамо се на лево подстабло, ако не померамо се на десно подстабло и памтимо да смо ухватили онолико такмичара колика је била вредност левог сегмента. На крају овог алгоритма налазимо се у листу који представља решење упита.

**Подзадатак 4**

Овај подзадатак се решава применом подзадатака 2 и 3, односно користимо _persistent segment tree_ и описани алгоритам на њему да би смањили временску сложеност на O(KlogR) док меморијска сложеност остаје O((\sum\_{i=1}^{N} S\_{i})logR).

На линку испод је детаљно објашњена _persistent segment tree_ структура података.

> **[Persistent Segment Tree | Set 1 (Introduction) - GeeksforGeeks](https://www.geeksforgeeks.org/persistent-segment-tree-set-1-introduction/)**
>
> A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

**Задаци за вежбу**

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

[http://codeforces.com/contest/899/problem/F](http://codeforces.com/contest/899/problem/F)  
Овај задатак може да се решава и као подзадатак 2.

[http://codeforces.com/problemset/problem/786/C](http://codeforces.com/problemset/problem/786/C)  
Овај задатак захтева _persistent segment tree_ и трик за смањење сложености.

---

<div class="post-metadata">

**Author:** ![DuX](https://algora.petlja.org/user_avatar/algora.petlja.org/dux/32/57_2.png) [@DuX](https://algora.petlja.org/u/DuX)\
**Post date:** [May 27, 2018, 4:05pm UTC](https://algora.petlja.org/t/resenja-zadataka-kvalifikacije-2018-treci-krug/1165/13 "2018-05-27T16:05:56Z")

</div>

Hvala @TadijaSebez 🙂