[Решења задатака] 2025/2026 Квалификације

Sprdalo · December 16, 2025, 4:22pm

Подела јабука

Аутор: Милош Милутиновић

Текст и тест примери: Милош Милутиновић

Тестирање: Драган Урошевић

Анализа решења: Василије Новаковић

Решење када a,b,c \le 200.

На почетку, Дон Хуан има a јабука, Селектор има b јабука, а Варијације има c јабука.

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

Приметимо да редослед операција није битан, јер ће сваки пријатељ након неких операција имати

k = x + 2 \cdot y - z, где је:

k: број јабука које неки пријатељ има након неких операција,

x: број јабука које је имао пре операција,

y: број сопствених операција,

z: број туђих операција.

k очигледно не зависи од редоследа операција, јер ништа у једначини не зависи од редоследа операција.

Још једна ствар коју можемо приметити јесте да ако сваки пријатељ сазове по једну операцију, то је исто као да је нико није сазвао. Ово значи да ако постоји начин да сва тројица имају једнак број јабука на крају, могуће је то одрадити тако да само двојица раде операције.

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

Претпоставимо да a \le b \le c, ако није можемо их само заменити тако да ова неједнакост важи.

Сад, ако прво радимо операције да повећамо b, па онда да повећамо a, очигледно након операција на b, b и c морају да буду једнаки, јер ће након тога операције на a смањивати оба броја подједнако.

Можемо симулирати операције на b све док не буде важило b \ge c. Ако b > c очигледно је одговор НЕ, јер ће операцијама на a оба подједнако да се смање, па никад неће бити једнаки.

Ако b = c, симулирамо операције на a, све док не буде важило a \ge b, то јест a \ge c.

Сад, из истог разлога, ако је a > b одговор је НЕ, а ако је a = b = c, одговор је очигледно ДА.

Једном операцијом, смањићемо разлику између бројева за 3, па је највећи могући број операција a+b.

Временска сложеност: O(a+b).

Просторна сложеност: O(1).

Главно решење

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

Наиме, изједначавање b и c ће се десити ако и само ако је c - b дељиво са 3, јер једна операција повећава b за 2, а смањује c за 1.

Ако није дељиво са 3, очигледно ће одговор бити НЕ.

Ако јесте, можемо закључити да ћемо урадити (c-b)/3 операција на b. Њих можемо све одједном применити тако што одузмемо (c-b)/3 од a и c, а додамо 2 \cdot (c-b)/3 на b.

Сад важи b = c, и свака операција на a ће смањити b и c подједнако. Исто као за b и c, морамо да проверимо да ли је b-a дељиво са 3. Ако јесте, не морамо ни да радимо операције, јер знамо да ће их оне изједначити, па да је одговор ДА, ако није, одговор је НЕ.

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

Наиме, резултат операције на a је: a постаје a+2, b постаје b-1, c постаје c-1.

Приметимо да се међусобне разлике између свака два елемента остале исте по модулу 3.

Такође приметимо из претходно наведеног процеса, да нам је одговор НЕ, само ако у неком тренутку разлика између нека два елемента није дељива са 3.

Ово нас доводи до закључка да разлика свака два елемента мора бити дељива са 3 на почетку јер се то операцијама не мења.

Ако јесте, показали смо како се решење добија, али довољно је само исписати ДА.

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

Временска и просторна сложеност: O(1).

Sprdalo · December 16, 2025, 4:23pm

Најближи непријатељ

Аутор: Владимир Миловановић

Текст и тест примери: Филип Бојковић

Анализа решења: Софија Чебашек

Тестирање: Драган Урошевић

Решење када се сви достављачи у ниској налазе десно од Соћка

Приметимо да ће достављач најближи Соћку бити први када се крећемо по кругу у једном од два различита смера, почевши од позиције на којој се Соћко налази (s). Најближи достављачи за два смера се могу поклапати, тј. уколико постоји само један достављач он ће бити најближи за оба смера кретања. У овом подзадатку један од та два достављача ће у ниској бити први са десне стране Соћка, који се налази на позицији d_1, а други ће бити последњи достављач у ниској, на позицији d_2. Све позиције можемо наћи једним проласком кроз дату ниску. Растојање између позиција s и d_1 у једном смеру једнако је d_1-s и представља најмање растојање између неког достављача и Соћка, када се у кругу крећемо у том смеру. За други смер је најмање растојање између s и d_2, које се за тај смер рачуна по формули N-d_2+s. Решење задатка је мање од два израчуната растојања.

Решење када постоји само један достављач

Како постоји само један достављач, он ће уједно бити и најближи. Проласком кроз ниску налазимо и чувамо позицију на којој се налази Соћко (s), као и позицију достављача (d). Дужина једног кружног лука између Соћка и достављача једнака је \lvert s-d\rvert, а другог N-\lvert s-d\rvert. Решење задатка је мања од дужина та два лука.

Главно решење

Слично првом подзадатку, потребно је наћи најближег достављача Соћку за сваки од два смера кретања по кругу посебно. Проласком кроз ниску налазимо позицију s. За један смер се крећемо од позиције s улево кроз ниску, до прве позиције на којој се налази достављач (d_1). Уколико при тражењу дођемо до почетка ниске, а нисмо одредили d_1, претрагу настављамо од позиције N-1 улево, пошто се позиције налазе на кругу (карактери у ниској су индексирани од 0). Слично, за позицију најближег достављача при кретању у другом смеру (d_2) претрага се обавља од позиције s удесно. Уколико се налазимо на позицији N-1, а нисмо пронашли позицију d_2, претрагу настављамо од позиције 0 удесно. Растојање између s и d_1 при кретању у одговарајућем смеру у кругу можемо добити бројањем позиција за које смо се померили при тражењу позиције d_1. Слично налазимо и растојање између s и d_2 у одговарајућем смеру. Решење задатка је мање од та два растојања.

Други начин за решавање задатка је да се, након одређивања позиције Соћка у ниској, за сваког достављача израчуна растојање као у претходном подзадатку. Решење задатка је најмање од свих израчунатих растојања.

Временска сложеност: O(N)

Sprdalo · December 16, 2025, 4:23pm

Џек врабац

Аутор: Марко Миленковић

Текст и тест примери: Урош Костадиновић

Анализа решења: Ања Дожић

Тестирање: Софија Чебашек

Опсервација

Посматрајмо јарбол i који се налази на позицији x_i висине h_i и њему најближи јарбол који је виши од њега и налази му се са леве стране тј. најближи јарбол j за који важи h_j>h_i и x_j<x_i (претпоставимо да такав јарбол постоји).

Како су сви јарболи који се потенцијално налазе између њих нижи од оба посматрана јарбола (и i и j), магични конопац који се простире између њих никада неће достићи висину h_i. Дакле најближе место са леве стране где се појављује конопац или јарбол који је бар висине h_i мора бити на магичном конопцу који креће из јарбола j.

Знамо да ће нагиб конопца на почетку бити -1, тј. да ће се конопац спустити на висину h_i на удаљености тачно h_j-h_i од јарбола j. Знамо да се промена нагиба неће догодити пре него што канап дође до тражене висине зато што се нагиб мења на висини која је нижа од суседног јарбола, а ми из претпоставке знамо да је суседни јарбол или посматрани јарбол i или неки јарбол који је нижи од оба i и j.

Коначно, како знамо да је удаљеност између посматрана два јарбола x_i-x_j и знамо да је најближа тачка исте висине као јарбол i на удаљености h_j-h_i од јарбола j, добијамо да је удаљеност јарбола i од њему најближе тачке са леве стране која је исте висине као и он x_i-x_j-(h_j-h_i).

Аналогно добијамо да ће удаљеност јарбола i од њему најближе десне тачке која је бар његове висине бити x_j-x_i-(h_j-h_i).

Подзадатак 1: N\leq 1000

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

Временска сложеност: O(N^2)

Меморијска сложеност: O(N)

Подзадатак 2: N\leq 2\cdot 10^5

У овом подзадатку, јарболе ћемо сортирати по висини.

Када их тако сортирамо ићи ћемо редом од највишег до најнижег и убацивати их у сет. Пре него што убацимо јарбол i у сет, пронаћи ћемо њему најближи јарбол који је већ у сету. Ово можемо урадити помоћу функције lower\_bound која ради у O( \log N). Када пронађемо тај јарбол, на раније објашњен начин ћемо израчунати његову удаљеност од тражене тачке и добити решење.

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

Временска сложеност: O(N \log N)

Меморијска сложеност: O(N)

Подзадатак 3: Цело решење

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

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

Аналогно ћемо проверити и за најближе десне јарболе.

Приметимо да ће -1 бити исписано само у случају када имамо тачно један максимум јер једино тада неће постојати тачка на броду која је бар те висине.

Временска сложеност: O(N log N)

Меморијска сложеност: O(N)

Напомена

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

Sprdalo · December 16, 2025, 4:24pm

Пријатељски тркачи

Аутор: Никола Милосављевић

Текст и тест примери: Василије Новаковић

Анализа решења: Филип Бојковић

Тестирање: Драган Урошевић

Свака два тркача ће се највише једном срести. Хајде да проверимо све међусобне почетне положаје такмичара и да ли ће се поздравити:

иста x координата: како би се сусрели морају бити усмерени један ка другоме и удаљени паран број позиција
није 1. и иста y координата: симетрично случају 1.
није 1. ни 2. и први се креће на горе: једино може да се сретне са неким који се креће у лево или десно и то ако се налазе на истој y=x+n дијагонали за неко n\in\mathbb{Z} или на истој y=-x+n дијагонали зависно од смера кретања
није 1. ни 2. ни 3. и први се креће на доле: симетрично случају 3.

N = 2

Проверимо за свака два тркача услове одозго и избројимо број сусрета.

N \leq 1000

Проверимо за свака два тркача услове одозго и избројимо број сусрета. Временска сложеност је \mathcal{O}\left(N^2\right)

Сви y_i су једнаки

Како је свима y координата иста, поздравиће се они парови који су удаљени за паран број позиција (по x координати). То су само они парови којима је x координата парна и они парови којима је x координата непарна. Решење је дато формулом {\text{broj parnih x}\choose{2}}\cdot{\text{broj neparnih x}\choose{2}} ({a}\choose{b} представља биномни коефицијент, односно за b=2 је само \frac{a\cdot\left(a-1\right)}{2}) и временска сложеност је \mathcal{O}\left(N\righ) јер само треба да избројимо број парних и број непарних x координата.

\left|x_i\right|,\left|y_i\right|\leq 1000

Oвај подзадатак служи за неефикасну имплементацију главног решења (без коришћења мапа на пример)

Главно решење

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

За парове тачака са истом x или y координатом већ знамо шта да радимо. Само је потребно да бројимо појављивања искључиво за оне x или y координате на којима се налазе неке тачке и то можемо урадити коришћењем мапе у C++.

Потребно је такође избројати за све дијагонале на којима се налази нека тачка колико се тачака налази на њој. Можемо приметити да је свака дијагонала облика y=x+n јединствено одређена бројем y-x који је исти за све тачке на њој, док је свака дијагонала облика y=-x+n јединствено одређена бројем y+x који је исти за све тачке на њој. Ове бројеве можемо користити као кључеве за мапу и лако бројати колико има тачака на којој дијагонали. За појединачну дијагоналу решење је 2\cdot {\text{broj tacaka}\choose{2}} јер се за сваки пар тачака поздрављају два пара такмичара (испод и изнад дијагонале).


int n; cin>>n;

map<int,int> xparno,xneparno,yparno,yneparno,dijagonalaplus,dijagonalaminus;

for(int i=0;i<n;i++){

int x,y; cin>>x>>y;

dijagonalaplus[x+y]++;

dijagonalaminus[x-y]++;

if(y&1) xneparno[x]++;

else xparno[x]++;

if(x&1) yneparno[y]++;

else yparno[y]++;

}

long long resenje=0;

for(auto [_,cnt]:dijagonalaplus) resenje+=(long long)cnt*(cnt-1);

for(auto [_,cnt]:dijagonalaminus) resenje+=(long long)cnt*(cnt-1);

for(auto [_,cnt]:xparno) resenje+=(long long)cnt*(cnt-1)/2;

for(auto [_,cnt]:xneparno) resenje+=(long long)cnt*(cnt-1)/2;

for(auto [_,cnt]:yparno) resenje+=(long long)cnt*(cnt-1)/2;

for(auto [_,cnt]:yneparno) resenje+=(long long)cnt*(cnt-1)/2;

cout<<resenje;

Sprdalo · December 16, 2025, 4:24pm

Пејнтбол

Аутор: Марко Миленковић

Текст и тест примери: Марко Миленковић

Анализа решења: Марко Миленковић

Тестирање: Василије Новаковић

Потпуно Решење

Моделоваћемо решење у терминима теорије графова. Чланови Комисије су чворови, а везе између сетера и тестера усмерене гране. Циљ је поделити чворове у два тима, тј. две партиције, тако да барем \lfloor M/2\rfloor грана постоји између партиција.

Расподелимо чворове (чланове Комисије) у две партиције (два тима) произвољно. Уколико постоји чвор који има више суседа у својој партицији, него у другој, пребацимо га у другу. Овај процес понављамо све док постоје такви чворови.

Зашто се процедура завршава?

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

Зашто је алгоритам тачан?

Када се процедура заврши то значи да сваки чвор v има барем deg(v) суседа у другој партицији, где је deg(v) укупан број суседа које тај чвор има. На основу Леме о руковању, знамо да је сума свих степена (број суседа) чворова једнак двоструком броју грана. Одавде следи да смо испунили барем M/2 жеља.

Sprdalo · December 16, 2025, 4:24pm

Баки и Срећко

Аутор: Урош Костадиновић

Текст и тест примери: Урош Костадиновић

Анализа решења: Урош Костадиновић

Тестирање: Владимир Миленковић

Решење када је N \leq 20

Можемо тестирати свих 2^{20} могућности за изборе помераја и изаберемо најбољу (сваки померај или узмемо или не узмемо). Временска сложенст O(2^{n}).

Решење када n, |x_i| \leq 500.

Довољно је да за сваку могућу вредност X, суму свих помераја по x координати, проверимо случајеве када је Y, сума свих помераја по y координати, максимална и минимална. Те вредности можемо израчунати слично као у проблему ранца, где су x_i тежине предмета, а y_i вредности. Проблем настаје када требамо да чувамо вредности за и негативне вредности X. То можемо урадити тако што вредност за X, уместо на индексу X, чувамо на индексу X + |X|_{max}, где |X|_{max} означава максималну апсолутну вредност X. Временска сложеност O(n \sum |x_i|). Меморијска сложеност O(n \sum |x_i|).

Решење када је n \leq 1000

Задатак се може преформулисати на следећи начин: Дато је n вектора. Изабрати подскуп ових вектора тако да њихов збир има највећу могућу дужину. Претпоставимо да смо за сада узели скуп вектора I = \{ v_{i_1},v_{i_2}...v_{i_k} \} и нека је њихов збир v_I. Посматрајмо каква ће бити дужина вектора ако у скуп додамо вектор u. Важи |v_I + u|^2 = |v_i|^2 +|u|^2 + 2(v_i\cdot u) = |v_i|^2 +|u|^2 + 2|v_I||u|\cos\theta, где је угао \theta угао који формирају вектори v_I и u, а v_i\cdot u скаларни производ вектора v_i и u. Ако је \cos\theta > 0 онда нам се додавањем вектора u у скуп I дужина вектора повећава. Посматрајмо каква ће бити дужина вектора ако из скупа избацимо вектор u. Важи |v_I - u|^2 = |v_i|^2 +|u|^2 - 2(v_i\cdot u) = |v_i|^2 +|u|^2 - 2|v_I||u|\cos\theta. Ако је \cos\theta < 0 онда нам се избацивањем вектора u из скупа I дужина вектора повећава. Ово значи да ћемо у оптималном решењу узети све векторе с једне стране праве која је нормална на тај вектор. Довољно је да фиксирамо праву која ће бити нормална на резултујући вектор и онда узмемо све векторе с једне њене стране. Пошто има бесконачно много правих кроз (0,0) не можемо да пробамо сваку од њих. Довољно је да проверимо све праве које су одређене са (0,0) и неким од могућих помераја, тј. пролази кроз (0,0) и (x_i,y_i). Сада је потребно водити рачуна на то да нећемо узети векторе све са једне стране од неке праве, већ све векторе с једне стране неке праве који нису колинеарни са њом и све векторе који су на тој правој и у истом су смеру. За сваку од 2n могућности (2n јер је битно с које стране узимамо векторе) ћемо за сваки од n вектора проверити да ли је на одређеној страни ње. Временска сложеност O(n^2).

Решење за 100 бодова

Користићемо исту идеју као у решењу претходног подзадатка. Можемо приметити да ако сортирамо све векторе око (0,0) по углу који одређују са x осом ћемо увек при фиксирању неке праве узети неки узастопни интервал вектора, или неки префикс и суфикс. Ако у претходном решењу фиксирамо редом праве у сортираном поретку другу границу интервала можемо одржавати користећи технику два покаживача. Временска сложеност O(n \log n + n). Напомена: Векторе можемо да сортирамо по углу тако што прво сортирамо векторе изнад x осе по коефицијенту праве (0,0),(x_i,y_i), а онда исто за векторе испод x осе. Може доћи до грешке у коду ако не избацимо векторе облика (0,0) из оптицаја.

Sprdalo · December 16, 2025, 4:25pm

МСТ

Аутор: Павле Мартиновић
Текст и тест примери: Филип Бојковић
Анализа решења: Филип Бојковић
Тестирање: Ања Дожић
За почетак ћемо мало демистификовати текст задатка. Посматрајмо кружне токове као чворове неусмереног графа, а улице које ми градимо као гране тог графа. Скуп улица који ће становници изабрати за кретање је најмање разапињуће стабло тог графа. Граф који створимо прављењем улица треба да буде прост (да не постоји више грана између иста два чвора и да не постоје гране које повезују неки чвор са њим самим), повезан (да путевима може да се стигне од сваког чвора до сваког другог чвора). Треба исписати највећу могућу тежину (збир тежина грана) најмањег разапињућег стабла неког графа који можемо да направимо. Свако наше прављење путева одговара неком графу и он има најмање разапињуће стабло. Потребно је наћи највећу вредност за било које наше прављење путева.

M = N-1

Једини начин да повежемо граф јесте да изградимо стабло и тада је решење само збир тежина свих датих грана.

int n,m; cin>>n>>m;
vector<int> a(m);
for(int i=0;i<m;i++) cin>>a[i];
cout<<accumulate(a.begin(),a.end(),0ll); // zbir tezina

M = N

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

int n,m; cin>>n>>m;
vector<int> a(m);
for(int i=0;i<m;i++) cin>>a[i];
if(m==n-1){
  cout<<accumulate(a.begin(),a.end(),0ll); // zbir tezina
}else{
  sort(a.begin(),a.end());
  long long zbir=0;
  for(int i=0;i<m;i++){
    if(i==2) continue; //zbir svih grana osim trece
    zbir+=a[i];
  }
  cout<<zbir;
}

(НТОР) Најинтересантији тренутак овог решења

Посматрајмо крускалов алгоритам: становници ће у сваком кораку бирати грану најмање тежине такву да се не прави циклус, а ми желимо тако да направимо граф да они бирају што мање грана мале тежине. Након прве 2 гране можемо да их ”натерамо” да не узму једну грану (прављењем циклус), након прве 3 узете гране можемо да их ”натерамо” да не узму 2 гране, након 4 узете гране можемо 5 итд. Ово радимо тако што правимо комплетан граф са тренутним чворовима докле год можемо, када више не можемо смо приморани да додамо нови чвор и самим тим и грану која мора да буде узета.

Решење за све поене

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

  int n,m; cin>>n>>m;
  vector<int> a(m);
  for(int i=0;i<m;i++) cin>>a[i];
  sort(a.begin(),a.end());
  long long zbir = accumulate(a.begin(),a.end(),0ll);
  int visak = m-n+1; // koliko grana treba preskociti a da graf ostane povezan
  int cvor = 0;
  int tren = 0; // broj grana koji trenutno mozemo da preskocimo
  for(int i=0;i<m;i++){
      if(tren==0){
          tren=cvor;
          cvor++;
          continue;
      }
      if(!visak) break;
      zbir -= a[i];
      tren--;
      visak--;
  }
  cout<<zbir;

M = N+9

Овај подзадатак је ту да се добију неки поени за ручну имплементацију првих пар корака алгоритма за све поене. (M-\left(N-1\right) = 10 = 1+2+3+4)

Sprdalo · December 16, 2025, 4:26pm

Игра са картама

Биће додато ускоро.

Sprdalo · December 16, 2025, 4:26pm

Потера

Аутор: Марко Миленковић

Текст и тест примери: Марко Миленковић

Анализа решења: Марко Миленковић

Тестирање: Урош Костадиновић и Василије Новаковић

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

Собе моделујемо као чворове, а ходнике између њих као усмерене гране.

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

Потпуно Решење

Задатак ћемо решити алгоритмом највећег протока (max-flow). Собе моделујемо као чворове, а ходнике између њих као усмерене гране. Додаћемо и вештачки извор и ушће. За сваки чвор i, уколико му је K_i позитиван, додамо грану од извора до i са капацитетом K_i. Уколико му је K_i негативан, додајемо грану од i до ушћа са капацитетом -K_i.

За свака два чвора која су повезана у графу, додајемо ту грану која их повезује и стављамо јој капацитет бесконачно (у пракси ставимо неки јако велики број, нпр. INT32_MAX). Затим, Форд-Фулкерсоновим алгоритмом налазимо највећи проток f.

Од суме свих позитивних вредности K_i одузимамо f. Вредност коју добијемо обележимо са X. Уколико је X позитивно, исписујемо то као решење, а иначе штампамо -1.

Доказ тачности

Испуњавамо услов затворености скупа S са постојањем бесконачних грана. На основу дуалности између највећег протока и минималног пресека (min-cut-max-flow duality), можемо да закључимо да у минималном пресеку сигурно се неће наћи грана бесконачног капацитета.

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

Sprdalo · December 16, 2025, 4:26pm

Перица и новогоришње стабло

Аутор: Марко Миленковић

Текст и тест примери: Урош Костадиновић

Анализа решења: Урош Костадиновић

Тестирање: Алекса Данић и Марко Миленковић

Решење када је \epsilon = 10^{-3}

У овом случају довољно је наћи MST за ове тачке. За сваку тачку ћемо додати само одређене гране које је садрже и применити Крускалов алгоритам за MST. Посматрајмо неку тачку A и поделимо раван у 8 квадранта тако да је A у центру. Никада у MST-у неће бити оптимално да узмемо две гране које садрже A, нпр. гране које спајају тачке A и B и тачке A и C, из истог октанта јер ће важити dist(B,C) \leq max(dist(A,B),dist(A,C)), где dist(X,Y) означава Менхетн дистанцу између тачака X и Y. Ово значи да можемо за сваку тачку посматрати само по најкраћу грану у сваком октанту. Потребно је још пронаћи за сваку такчу која јој је најближа у сваком њеном октанту. Претпоставимо да тражимо само најближу тачку у једном октанту, остали случајеви су исти до на ротацију. Дистанца од тачке A до неке тачке из њеног октанта, нпр. B, ће бити B_x-A_x+B_y-A_y = (B_x+B_y)-(A_x+A_y). За свако k чуваћемо у Фенвиковом стаблу минималну вредност збира координата тачака које смо прошли до сад које имају разлику x и y координате мању од k. Сортираћемо тачке прво по y координати опадајуће и ићи редом кроз њих. Када желимо да нађемо најближу тачку у октанту за тачку A само ћемо наћи бредност у Фенвиковом стаблу за k = A_x-A_y и након тога ажурирати вредност на позицији A_x-A_y са A_x+A_y. Након што додамо све гране ћемо применити Крускалов алгоритам за налажење MST-а. Временска сложеност: O(nlogn).

Решење за 100 бодова

Поделимо [0,1]^2 на квадратиће странице дужине \frac{\epsilon}{3}. Контраковаћемо граф тако што ће нам у новом графу чворови бити квадратићи, а грана између два квадрата бити најмања дистанца неке тачке из првог и неке тачке из другог. Нeka je F минимално разапињуће стабло овог контракованог графа. Стабло F ћемо наћи тако што ћемо прво за сваки квадратић све тачке у њему спојити по цени 0 и онда применити Крускалов алгоритам посматрајући све исте гране као у претходном подзадатку. Због овога свака грана у F мора да буде и у MST и свака грана из MST дужине веће од \frac{2\epsilon}{3} мора да буде и у F. Тачке из грана из оригиналног графа које смо додали у F ће нам чинити скуп Q, а гране из оригиналног графа које смо додали у F ће нам заједно са произвољним гранама унутар квадратића чинити стабло T. Свака грана из T или припада MST-у или цела припада неком квадратићу који садржи тачку из MST, па свака тачка на T има себи \epsilon-близу тачку из MST. Једине гране из MST које нису у T имају дужину максимално \frac{2\epsilon}{3}. Посматрајмо једну такву грану која спаја тачке A и B. Нека је тачка C на тој грани и нека јој је без умањења општности тачка A ближа од тачке B, тј. dis(A,C) \leq \frac{\epsilon}{3}. За тачку A постоји тачка X из њеног квадратића која је на дистанци максимално \frac{2\epsilon}{3}, па ће због неједнакости троугла важити dis(C,X) \leq dis(C,A)+dis(A,X) \leq \frac{\epsilon}{3} + \frac{2\epsilon}{3} = \epsilon, што значи да стабло T задовољава услов задатка. Временска сложеност: O(nlogn).

Sprdalo · December 16, 2025, 4:27pm

Срећко и пончои

Аутор: Урош Костадиновић

Текст и тест примери: Урош Костадиновић

Анализа решења: Урош Костадиновић

Тестирање: Немања Мајски

Решење када је N \leq 40, \epsilon = 0.01

У овом подзадатку је могуће наћи оптимално решење за Срећка. Класично решење за проблем ранца би било сложености O(nW) , а испробавање свих могућности за узимање пончоа би било сложености O(2^n), што је за ограничења преспоро. Друго решење би било довољно добро да је n \leq 20. Mожемо да поделимо пончое у две групе тако да је величина сваке мања или једнака од \frac{n+1}{2} и на њима искористимо друго решење. Сада смо генерисали све могућности ако сви узети пончои припадају истој групи и остало је да проверимо за решења где пончои припадају у обе групе. Фиксирајмо које смо пончое узели из прве групе и нека је њихова тежина W_1. Онда ћемо из друге групе узети пончое тежине максимално W-W_1 са највећом вредношћу. Ту вредност можемо наћи користећи технику два показивача. Сортирајмо могућности из прве групе и могућности из друге групе (одвојено) по тежини. Фиксираћемо групу пончоа које пончое узимамо из прве групе опадајући по тежини и редом ћемо додавати могућности из.

Временска сложеност O(2^{\frac{n}{2}}n)

Решење када \epsilon = 0.5.

У верзији задатkа у којој можемо да узмемо било који реалан део неког пончоа оптимално је да сортирамо пончое по односу цене и тежине и онда узимамо сваки следећи на реду уколико можемо. На овај начин само један од пончоа које смо узели неће бити цео. Нека је opt_{greedy} вредност коју добијемо на овај начин не рачунајући део не-целог пончоа. Нека је V_k пончо чији бисмо део узели у другој верзији задарка. Знамо да је opt_greedy + V_k \geq opt. Нека је V_{max} највећа вредност неког пончоа, онда је opt_{greedy}+V_{max} \geq opt па је max(opt_{greedy},V_{max}) \geq \frac{opt}{2}. Узећемо бољу од ове две опције и она ће гарантовано бити барем (1-\epsilon)opt. Временска сложеност O(n log n)

Решење када је n \leq 60,\epsilon = 0.2

У оптималном решењу ћемо користити мање од \frac{1}{\epsilon} пончоа величине веће или једнаке од \epsilon \cdot opt. Можемо да прођемо кроз све могућности за те пончое којих има O(n^{\frac{1}{\epsilon}}). Остале елементе ћемо имати већ сортиране и на исти грамзив начин ћемо их узимати као и у претходном подзадатку. Сада је разлика у томе што ће пончо чији бисмо узели реалан део био вредности максимално \epsilon \cdot opt, па је ans + \epsilon \cdot opt \geq opt тј. ans \geq (1-\epsilon) opt што значи да решење које смо нашли одговара. Временска сложеност: O(n^{\frac{1}{\epsilon}})

Решење за 100 бодова

Уместо да применимо класичан проблем ранца на праве вредности можемо да их скалирамо по цени губљења прецизности. Нека је нова вредности понча i једнака v'_i = \lfloor \frac{v_i}{\frac{\epsilon}{n}v_{max}} \rfloor. Применићемо класичан проблем ранца тако што ћемо израчунати за сваки могући збир вредност која је минимална тежина скупа пончоа који имају ту вредност. За сваки пончо занемарујемо део његове вредности који је највише \frac{\epsilon}{n}v_{max}, а пошто узимамо максимално n пончоа максимално смо занемарили n \frac{\epsilon}{n}v_{max} = \epsilon v_{max}, па је ans+ \epsilon v_{max} \geq opt, где је ans решење које смо нашли рачунато са новим вредностима пончоа. Пошто је v_{max} \leq opt онда је и ans+ \epsilon opt \geq opt па је ans \geq (1-\epsilon)opt, што значи да решење које смо нашли одговара. Нове вредности пончоа ће бити између 0 и \frac{n}{\epsilon} па ће временска и меморијска сложеност бити O(\frac{n^3}{\epsilon}).