Tekstove zadataka možete ovde, gde možete i testirati svoje kodove.
Прва цифра
Аутор: Никола Милосављевић
Текст и тест примери: Алекса Плавшић
Анализа решења: Душан Здравковић
Анализа
Задатак је осмишљен тако да буде најлакши у овом кругу квалификација. Потребно је урадити управо оно што пише у тексту - упоредити прву цифру бројева, а уколико су исте, онда упоредити целе бројеве.
Смернице за алгоритам
Елегантно решење је учитати бројеве као стрингове, и упоредити први карактер стринга, а уколико је први карактер исти, онда пребацити стринг у број (нпр. користећи atoi функцију у C++, или StrToInt функцију у Pascalu) и упоредити бројеве једноставним поређењем.
Уколико бројеве учитамо у Integer формату, прву цифру броја можемо добити једноставном функцијом (пример дат у C++):
int prvaCifra(int a) {
while (a >= 10) {
a /= 10;
}
return a;
}
2 Likes
Трансформација матрице
Аутор: Никола Милосављевић
Текст и тест примери: Алекса Плавшић
Анализа решења: Душан Здравковић
Тестер: Слободан Митровић
Анализа
Прво што је потребно приметити у задатку је да редослед операција које извршавамо над првом матрицом није битан. Тј. исто ће бити уколико прво променимо вредност једног елемента, па онда ротирамо матрицу, или уколико прво ротирамо, па онда заменимо вредност. То значи да прво можемо радити операције ротације, па тек онда после тога операције промене вредности.
Такође, можемо приметити да никада нећемо ротирати матрицу више од 3 пута, јер ако је ротирамо 4 пута, онда долазимо у исту позицију као на почетку. Тиме смо задатак свели на 4 случаја, у зависности од тога колико пута смо ротирали матрицу (0 до 3 пута). Сваки пут када је ротирамо, проверићемо колико се елемената разликује, а број различитих елемената плус број тренутних ротација до сада нам даје колико је укупно потребно операција за тај случај. На крају, запамтићемо најмањи број потребних операција који нам је требао у неком од та 4 случаја.
Смернице за алгоритам
За ротацију квадратне матрице A величине NxN за 90 степени у десно је потребно да приметимо да ће на место поља (x,y) доћи поље (y, N+1-x), уколико су поља индексирана почев од 1. Тј. уколико желимо да добијемо матрицу А' која је ротирана верзија матрице А, можемо је израчунати преко формуле: А'[x][y] = A[y][N+1-x].
2 Likes
Продавнице
Аутор, текст и тест примери, анализа решења: Никола Милосављевић
Тестери: Алекса Плавшић и Иван Стошић
Анализа
Јасно је да је за сваки упит (A, B) потребно израчунати вредност израза \sum_{i=1}^n \min(|x_i - A|, |x_i - B|) тј. суму растојања до најближе продавнице. Директно рачунање ове суме за сваки упит даје решење сложености O(nm) што је довољно само за 20 поена.
Посматрајмо случај када увек важи A_i = B_i тј. када је потребно израчунати \sum_{i=1}^n |x_i - A|. За почетак, природан корак је сортирање низа x – надаље претпостављамо да је x_1 \leq x_2 \leq \ldots \leq x_n. За дату вредност A можемо бинарном претрагом у сложености O(\log n) одредити највећу вредност ind за коју важи x_{ind} < A (или установити да таква вредност не постоји ако је A \leq x_1). Сада важи
\sum_{i=1}^n |x_i - A| = \sum_{i = 1}^{ind} (A - x_i) + \sum_{i=ind+1}^n (x_i - A) = ind \cdot A - s_{ind} + (s_n - s_{ind}) - (n - ind)\cdot A
где је s низ префиксних сума низа x, тј. s_i = x_1 + x_2 + \ldots + x_i. Према томе, уколико на почетку (пре свих упита) сортирамо низ x и израчунамо низ префиксних сума, можемо за сваки упит одрадити бинарну претрагу и вратити резултат из претходне једначине (без сумирања). Сложеност овог приступа је O(n \log n + m \log n).
Претходни алгоритам се једноставно модификује и у случају када је A_i \neq B_i. У том случају, за упит (A, B) (нпр. нека је A < B) бинарном претрагом пронађемо највећу вредност mid за коју важи x_{mid} < \frac{A+B}{2}; то значи да ће сви становници са координатама x_1, x_2, \ldots, x_{mid} ићи у продавницу A а становници са координатама x_{mid+1}, x_{mid+2}, \ldots, x_n у продавницу B. Затим два пута применимо претходни алгоритам, једном за подниз x[1, mid] и вредност A, а други пут за подниз x[mid+1, n] и вредност B.
За додатне подзадатке је такође предвиђен овај алгоритам али је за њих довољна потенцијално лакша имеплементација и мања анализа специјалних случајева о којима треба водити рачуна приликом имплементације решења за 100 поена – нпр. када су вредности A или B или \frac{A+B}{2} лево или десно од низа x (нпр. када сви иду у само једну продавницу). Ово се у потпуности може заобићи паметно дизајнираном функцијом за поменуту бинарну претрагу.
2 Likes
Окрњен троугао
Аутор и текст: Никола Спасић
Тест примери и анализа решења: Иван Стошић
Тестер: Андреј Ивашковоћ
Анализа
Посматрајмо неки троугао T који задовољава услове задатка.
Како троугао T садржи дати многоугао M, а T је конвексан скуп, важиће и K \subseteq T, где је
K конвексни омотач многоугла M, јер је K по дефиницији најмањи конвексан скуп који
садржи M. Дакле, у задатку се тражи да за дати многоугао нађемо троугао најмање површине
који садржи његов конвексни омотач, са додатним ограничењем да нека страница троугла буде
једнака некој страници датог многоугла, нека је то страница BC.
Темена B, C морају бити суседна темена у конвексном омотачу, јер се у супротом страница троугла налази у строгој унутрашњости конвексног омотача па га троугао не може садржати.
Из претходно реченог произилази да конвексни омотач и троугао имају заједничку страницу.
Посматрајмо сада неку страницу BC конвексног омотача. Претпоставићемо да наш троугао баш
ту страницу дели са К. Како нам треба троугао минималне површине његове преостале странице морају имати исти правац као и странице које су суседне страници BC, нека су то странице AB, CD.
Стога за сваку страницу конвексног омотача треба проверити да ли се продужеци суседних страна AB, CD секу са одговарајуће стране и да ли је страница BC конвексног омотача уједно и страница многоугла, што нам је довољно да закључимо да постоји троугао са одговарајућим својствима. Затим, налазимо пресек правих E = AB \cap CD и то је трећа тачка нашег троугла. Сада знамо сва темена троугла, одредимо површину а затим и разлику површина између њега и почетног многоугла.
Смернице за алгоритам
Због начина на који су дата темена многоугла можемо у линеарном времену наћи конвексни омотач. (видети чланак на Википедији).
Површина троугла коме знамо координате може се добити као половина интензитета векторског производа две његове странице (односно одговарајућих вектора).
Означена површина неконвексног многоугла може се наћи као збир означених површина произвољног разбијања тог многоугла на троуглове - видети линк.
Даље, потребно је наћи површину троугла BCE где је E пресек правих AB и CD. У теорији, ово се може урадити налажењем једначина те две праве и решавањем система од две једначине са две непознате, а затим применом горе поменуте формуле за површину троугла. Међутим, проблем настаје због употребе типа double за представљање коефицијената и решења ове једначине. Срећом, постоји далеко једноставнији начин за налажење површине троугла BCE. Важи следећа једнакост: P(BCE) = \frac{P(ABC) P(BCD)}{P(BCF)}, где је F тачка добијена померањем тачке D за вектор CB, што се може релативно лако доказати алатима елементарне геометрије.
3 Likes
Награде
Аутор: Борис Грубић
Текст, тест примери: Димитрије Ердељан
Анализа решења и тестирање: Иван Стошић
Анализа
Прво, за сваки број са улаза нађимо све различите просте бројеве који
га деле. Ово се може урадити ефикасно помоћу модификације Ератостеновог
сита, којом се сваки број x < M може факторизовати у логаритамској сложености, где је M горња граница за Ератостеново сито.
Ових различитих простих бројева има не више од 6, јер је производ
најмањих 7 простих бројева већи од 2 \times 10^5. Сада, за сваки број нађимо
количник њега и сваког различитог простог броја који га дели. Нека
је за i-ти број P_i листа његових различитих простих делилаца а C_i листа
која се добија када се A_i подели са сваким елементом листе P_i. Циљ задатка је да нађемо
низ различитих бројева B тако да је за свако i, B_i = A_i / P_{i, j} = C_{i, j} за неко j. Овај проблем је познат
и под називом систем различитих представника фамилије скупова C. Ово
се може решити у полиномијалном времену
тако што се представи као бипартитни граф, где су чворови са
леве стране индекси из оригиналног низа, а са десне стране количници. За свако
i додајемо грану од чвора i са леве стране до чворова C_{i, j} са
десне, за свако j. Сваки систем различитих представника сада одговара једном
перфектном спаривању (мечингу) у овом графу, односно мечингу где је сваки чвор
са леве стране спарен. Дакле желимо да испитамо
да ли овако добијен граф има мечинг са N грана и који је то мечинг.
Најједноставнији и најпознатији алгоритам јесте Форд-Фулкерсонов
алгоритам који ради у сложености O(VE), где је V број чворова,
а E број грана у графу, што у нашем случају, због горе
поменутог ограничења на број грана износи O(N^2). Приметимо да не морамо
да додајемо све чворове са десне стране већ само оне који се бар
једном појављују као количници.
2 Likes