[Решења задатака] 2024/2025 Квалификације - први круг

Algoritam
1

Пећина

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

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

Како би се решио задатак довољно је, почевши од првог, итерирати кроз низ оформљен од вредности висина сталактита (мисли се на висину од пода пећине на којој се налази врх сталактита) и упоређивати висину i-тог сталактита H_i са висином L. Уколико је H_i \leq L неопходно је исписати i водећи рачуна да индекси који заправо представљају редне бројеве сталактита почињу од 1, а не од 0. За случај да се прође кроз читав низ, то јест свих N вредности висина сталактита, и да су притом висине свих њих строго веће од L, тада је потребно исписати -1.

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

Изворни код у програмском језику Пајтон могао би изгледати рецимо:

N, L = map(int,input().split())
H = list(map(int,input().split()))

idx = -1
for i in range(len(H)):
    if H[i] <= L:
        idx = i + 1
        break

print(idx)
2

Плазма

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

Анализа решења

Најпре је згодно размотрити решење за једно питање, односно за случај када је Q=1. Неопходно је обрађивати доставе у временском редоследу како су и дате, водећи рачуна када је била последња достава, број паковања Плазма кекса који је тренутно на располагању, као и укупан број паковања који је купљен (до тог тренутка). Када се обрађује нова достава Плазме, ажурира се укупан број паковања, али и број паковања који је на располагању како би се урачунало и то колико је кутија поједено од последње куповине, као и нове кутије у последњој куповини. Одговор је заправо само разлика између броја паковања Плазме које су достављене и броја паковања која су преостала на крају. Како су доставе већ сортиране по времену, обрада једне доставе узима \mathcal{O}(1), односно \mathcal{O}(N) укупно за свих N достава.

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

Користећи се техником два показивача, задатак је могуће решити и у сложености \mathcal{O}(N+Q), иако се то није захтевало за максималан број поена. Кључно за ово решење јесте унутар једне петље итерирати истовремено и кроз доставе и кроз питања и вршити одговарајуће обраде. Поред боље временске сложености, меморијска сложеност овог алгоритма је такође нижа од претходно описане бинарне бретраге.

1 Like
3

Пожар

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

Решење када је N = 1

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

Решење када је N, M \leq 10

У овом подзадатку довољно је проверити за свако поље brute-force методом да ли му је ближи Стева или било која ватра.

Peшење када тачно једно поље садржи ватру

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

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

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

4

Конвексни скоро омотач

Аутор: Немања Мајски
Текст и тест примери: Немања Мајски
Анализа решења: Немања Мајски
Тестирање: Александар Вишњић

Рачунање површине:

Површину неког конвексног моноугла можемо израчунати тако што га поделимо на троуглове, израчунамо површине тих троуглова и саберемо их. Важно је да површину рачунамо користећи само целе бројеве. Препорука је да се то ради преко векторког производа. Ако се користи нпр. Херонова формула, дешавају се грешке у прецизности, због чега програм неће дати тачан резултат.

Решење када је N=4:

Приметимо да је проблем исто што и склањање једне тачке и затим тражење минималног конвексног омотача осталих тачака. Из тога следи да ће конвексни скоро омотач бити троугао који има 3 од дате 4 тачке. Тако да можемо проверити све троуглове и исписати најмању од њихових површина.

Решење када је N \le 500:

Приметимо да како бисмо нашли конвексни скоро-омотач можемо да итерирамо кроз тачку коју избацујемо и да нађемо конвексни омотач осталих тачака. Такав омотач са најмањом површином је конвексни скоро-омотач.

За налажење конвексног омотача можемо користити алгоритам у сложености O(N^2). На пример Jarvis march алгоритам.

Временска сложеност је O(N^3), а меморијска O(N).

Решење када је N \le 2000:

Користимо решење из претходног подзадатка, само што користимо ефикаснији алгоритам за налажење конвексног омотача. Можемо на пример користити Graham scan који ради у времеској сложености O(N log N).

Временска сложеност је O(N^2 log N), а меморијска O(N).

Решење када је број страница конвексног омотача највише 10:

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

Временска сложеност је O(\alpha \cdot N log N), а меморијска O(N), где \alpha представља број темена конвексног омотача.

Решење када су тачке темена конвексног $N-$тоугла:

Итерирамо по тачки коју избацујемо. Нека је то тачка A и нека су њени суседи B и C. Приметимо да ће конвексни омотач бити исти, сем што после тачке B неће долазити тачка A него тачка C. Тако да ће његова површина бити једнака површини почетног моноугла умањеној за површину троугла ABC.

Ако израчунамо површину оригиналног моноугла и одузмемо површину највећег троугла који чине 3 суседне тачке, нашли смо површину конвексног скоро-омотача.

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

Решење када је број страница конвексног омотача најмање N - 100:

Нађимо конвексни омотач свих тачака. Над њиме примењујемо алгоритам из претходног подзадатка. Проблем је ако се у троуглу ABC налазе неке тачке.

Тада конвексни омотач неће ићи од тачке B до тачке C, већ ће садржати и неке тачке које се налазе у троуглу ABC. Да бисмо нашли за колико се смањи површина склањањем тачке A, морамо од површине троугла ABC одузети површину конвексног омотача скупа тачака који чине тачке B, C и тачке унутар троугла ABC (без тачке A).

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

Временска сложеност је O(\alpha \cdot N + N log N), а меморијска O(N), где \alpha представља број тачака које се не налазе на конвексном омотачу.

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

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

Нека су координате тачака троугла ABC редом (x_1,y_1),(x_2,y_2),(x_3,y_3). Онда да би нека тачка (x, y) припадала троуглу ABC, мора да важи:

min(x_1, x_2, x_3) \le x \le max(x_1, x_2, x_3)

Ако тачке оригинално сортирамо по x координати, онда је налажење свих таквих тачака лако користећи бинарну претрагу. Онда за све такве тачке проверимо да ли су у троуглу.

Како је конвексни омотач конвексан моноугао, то значи да га свака права сече у највише 2 тачке. Из тога следи да ће уз оптимизајицу горе свака тачка бити проверена највише 4 пута да ли је у неком троуглу, па ће бити највише 4 \cdot N провера.

Временска сложеност је O(N log N), а меморијска O(N).

5

Два низа

Аутор: Милош Милутиновић
Текст и тест примери: Милош Милутиновић
Анализа решења: Милош Милутиновић
Тестирање: Филип Бојковић

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

Фиксирамо L, и затим померамо R = L, L+1, \dots, N, и приликом померања рачунамо xor и and вредност интервала. Временска сложеност је O(N^2).

Peшење када је A_i = 1

Приметимо да ће оптимални интервал садржати само један елемент, тј. L = R, јер избором већег интервала не можемо добити већу вредност ни за xor ни за and. Одатле се види да је решење максимални елемент у низу B.

Решење када је A_i \leq 500

Уведимо низ pref_i = A_1 xor A_2 \dots xor A_i који ћемо надаље користити.

Могуће је за свако R фиксирати xor вредност интервала, нека је та вредност X. Тада знамо да важи pref_R xor pref_{L - 1} = X, тј. pref_R xor X = pref_{L - 1}. Приметимо да је нама оптимално изабрати највеће L које испуњава тај услов. У помоћном низу aux_i ћемо чувати највеће L такво да је pref_{L - 1} = i. Тиме за свако R и X можемо наћи оптимално L и израчунати вредност тог подниза. Временска сложеност је O(N \cdot mаxA), где mаxA представља максималну вредност за A_i.

Решење када је B_i = 1

У овом подзадатку је потребно наћи интервал са највећом xor вредности. Ово је стандардан проблем који се решава коришћењем структуре података “trie”. Крећући се редом R = 1, 2, \dots, N тражићемо највећу вредност pref_R xor pref_{L - 1}. To радимо тако што све префиксне xor-ове убацујемо у структуру “trie”. Када за дати број x тражимо највећи xor, можемо да кренемо претрагу у структури почев од највишег бита, тј. корена структуре, и у сваком тренутку уколико постоји син тренутног чвора са битом супротним у односу на одговарајући бит броја x, у њему настављамо претрагу повећавајући максимални xor за одговарајућу вредност, док уколико не постоји тај син, претрагу настављамо у једином сину.

Решење када је B_i \leq 3

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

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

Приметимо да за дато R постоји највише \log_2 A различитих and вредности за интервал са датом десном границом. То је тривијално доказати, јер приликом додавања броја у неки скуп, and вредност тог скупа може само “изгубити” неке битове, којих је на почетку могуће максимално имати \log_2 maxA. Сада можемо чувати по једну “trie” структуру, у којим ћемо чувати префиксне xor-еве, за сваки интервал левих граница са истом “and” вредношћу. Приликом преласка на следећу десну границу, могуће је да ће се неки интервали левих граница спојити, па је потребно спојити и њихове “trie” структуре. То је могуће урадити на више начина, нпр. чувати те структуре у имплицитном облику па је могуће све елементе једне структуре директно пребацити у другу, под условом да прву избришемо. Временска сложеност тог дела је укупно О(N \cdot {\log^2 maxA}), јер сваки елемент ће бити пребачен највише логаритамски број пута у другу “trie” структуру и пребацивање једног елемента се врши у логаритамској сложености. За крај како бисмо нашли решење, за свако R, почевши од 1 и редом све до N, пролазимо кроз сегменте са истом and вредношћу и у сваком интервалу тражимо највећу вредност за pref_R xor pref_{L - 1}. Временска сложеност је О(N \cdot {\log^2 maxA}), меморијска сложеност је O(N \cdot {\log maxA}).