Пилећа крилца
Аутор: Марко Савић
Текст и тест примери: Марко Савић
Анализа решења: Марко Савић
Тестер: Алекса Милисављевић
Са R означимо реалну цену једног крилца, коју желимо да израчунамо.
Ако у i-тој ставци менија пише да K_i крилаца кошта C_i Јуана, то значи да K_i крилаца реално не могу коштати мање од C_i-0.5 Јуана. Свака мања реална цена за K_i крилаца заокружена на најближи цео број не би дала C_i као резултат заокруживања. Из тога закључујемо да је K_i R \geq C_i-0.5, односно R \geq (C_i-0.5)/K_i.
Сада је потребно проћи кроз све ставке у менију и за сваку наћи ово доње ограничење за цену. Јасно је да најмања могућа реална цена за једно крилце не сме бити мања од сваког тако добијеног доњег ограничења, што значи да не сме бити мања од њиховог максимума. Пошто нам се у задатку гарантује да су цене у менију формиране исправно, то значи да је најмања могућа реална цена једног крилца једнака управо том максимуму.
R=\max_{i\in\{1,2,\ldots,n\}}(C_i-0.5/K_i)
Леп низ
Аутор: Владимир Миленковић
Текст и тест примери: Владимир Миленковић
Анализа решења: Алекса Милисављевић
Тестер: Иван Стошић
Анализа
Задатак решавамо разматрањем вредности K:
-
Ако је K=0, вредност сваког степена ће бити 1, осим вредности 0^0. У том случају треба да пребројимо колико има 0 у низу и сваку коју можемо повећамо за 1.
-
Уколико је K=1, лепота низа је сума његових елемената. Тада је свеједно који ћемо елемент повећати, па само применимо свих C операција на било који елемент.
-
Уколико је K=2 и уколико будемо примењивали иједну операцију, применићемо свих C операција на највећи. То важи, јер претпоставимо да смо укупно применили D операција и то D_i на елемент A_i и нека највећи има вредност a тада је коначна сума: \sum_{i=1}^n (A_i + D_i)^2 = \sum_{i = 1}^{n} (A_i^2 + 2 \cdot A_i \cdot D_i + D_i^2) = \sum_{i = 1}^{n} (A_i^2 + 2 \cdot A_i \cdot D_i) +\sum_{i = 1}^{n} D_i^2 \leq \sum_{i = 1}^{n} (A_i^2 + 2 \cdot a \cdot D_i) + \sum_{i = 1}^{n} D_i^2 = \sum_{i = 1}^{n} A_i^2 + 2 \cdot a \cdot D + \sum_{i = 1}^{n} D_i^2 \leq \sum_{i = 1}^{n} A_i^2 + 2 \cdot a \cdot D + D^2, што је тачно једнако лепоти низ, када би на највећи додали D. Дакле уколико примењујемо неке операције, свакако их примењујемо на највећи. Међутим, приметимо да се тада лепота променила за 2 \cdot a \cdot D + D^2 што максимум достиже или за D=0 или за D=C, па ако будемо примењивали неку операцију, применићемо свих C на највећи.
Смернице за алгоритам
Приметимо да, уколико је K=2, довољно је да проверимо да ли повећавањем највећег елемента за C, повећавамо његову апсолутну вредност, уколико је повећавамо, применићемо свих C операција на њега, у супротном, нећемо применити ни једну операцију. Приметимо да, уколико апсолутна вредност остаје иста, нећемо применити ни једну операцију, јер тежимо да минимизујемо број операција.
Дељење низа
Аутор: Душан Здравковић
Текст и тест примери: Алекса Милисављевић
Анализа решења: Владимир Миловановић
Тестер: Марко Савић
Анализа
Једна од кључних ставки у задатку јесте гаранција да без избацивања, односно уништења неког узастопног подниза није могуће поделити задати низ тако да су му подзбирови неког префикса и остатка низа једнаки. Такође, поставка задатка условљава да су сви чланови улазног низа строго позитивни, што уз пажљиво решавање поједностављује комплексност коришћеног алгоритма претраге.
Најпре, нека је збир свих чланова задатог низа z, а збир чланова неког његовог префикса (односно суфикса) p. Неопходно је одредити неки непразан подниз улазног низа који не обухвата префикс (односно суфикс), такав да ако збир његових чланова означимо са s, мора бити задовољен услов z = p + s + p = 2p + s. Другим речима, збир чланова подниза који се уништава 0<s<z, мора бити једнак укупној суми свих чланова изворног низа умањеној за двоструку вредност префикса, s=z-2p.
Сада је потребно извршити претрагу по свим префиксима (односно суфиксима) и свим узастопним поднизовима улазног низа и проверити да ли је могуће задовољити малопређашњу једнакост. Уколико би та претрага наивно била извршена кроз три независне петље (прва по префиксима низа, а друга и трећа по левој и десној граници подниза за уништење), добила би се кубна временска сложеност \mathcal{O}(N^3) по дужини низа. Међутим, уз нешто вештију претрагу по левој и десној граници узастопног подниза ту сложеност могуће је и умањити.
Смернице за алгоритам
Наиме, на почетку итерације по префиксима (односно суфиксима) иницијализовати леву и десну границу на први суседни члан префикса (односно суфикса). У свакој итерацији неопходно је испитати да ли је вредност израза z - 2p - s већа, мања или једнака нули, те ако је већа, померати десну границу, а уколико је мања, померати леву. Претрага се завршава или када израз поприми вредност нула након чега следи испис утврђених граница подниза, или када лева и десна граница дођу до краја изворног низа, када се прелази на следећи префикс (односно суфикс). Пошто приликом напредовања граница мора бити задовољен и услов да индекс леве границе није виши од индекса десне, то је укупна сложеност ове унутрашње петље линеарна \mathcal{O}(N) по дужини низа. Како је неопходно претрагу урадити за све префиксе и суфиксе изворног низа (због асиметрије претраге), то је укупна сложеност овог алгоритма квадратна \mathcal{O}(N^2), што се и захтевало за максималан број поена у овом задатку.
Поштар
Аутор: Димитрије Ердељан
Текст и тест примери: Димитрије Ердељан
Анализа решења: Алекса Милисављевић
Тестер: Слободан Митровић
Анализа
Задатак решавамо динамичким програмирањем.
Решимо прво задатак у случају да су све координате Y_i позитивне. Прво сортирамо тачке по углу у односу на позицију поште. Нека је dp[l][r] најмања дужина пута, коју поштар мора да пређе, да би обишао све планере у интервалу [l,r], уколико је то могуће и inf у супротном. Нека смо повезали l са неком m таквом да је l<m<r, то је dp[l][r] = min_{l<m<r}(dp[l][m]+dp[m+1][r]). Друга опција је да повежемо планету l са r. Довољно је да проверимо да ли дуж која их спаја сече дуж између поште и неке друге планете. То можемо да урадимо у O(N). Уколико не сече, имамо још једног кандидата за решење, па је онда dp[l][r]=min(dp[l][r],dist(l,r)+dp[l+1][r-1]), где је dist(l,r) растојање између планете са индексом l и планете са индексом r. Резултат је у dp[1][N], а временска сложеност алгоритма је O(N^3).
Сада можемо решење да уопштимо на случај да координате Y_i нису позитивне. Приметимо да како год повезали планете, увек можемо да нацртамо једну полуправу из (0,0), која не сече ни једну путању. Ово важи зато што се путање међусобно не секу. “Лук” који прави један обилазак две планете може да буде садржан у неком другом и да садржи неки други, али не могу да се секу. Сада сортирамо тачке по углу. Ако претпоставимо да смо повукли ту полуправу негде између i и i+1 планете, можемо да посматрамо низ који је циклично померен улево за i места и да поновимо динамичко као у претходном делу. Ово решење ради у сложености O(N^4).
Међутим можемо да приметимо да велики део тог динамичког ми израчунавамо више пута. Можемо да дуплирамо сортирани низ, тј. циклично га поновимо други пут и поново израчунамо dp[l][r]. Приметимо да је сада у dp[i][i+N] управо решење које се добија када би полуправа била између планета i-1 и i. Па је крајњи резултат min_{1 \leq i \leq N}(dp[i][i+N]). Временска сложеност O(N^3), меморијска сложеност O(N^2).
Додела вредности
Аутор: Иван Стошић
Текст и тест примери: Иван Стошић
Анализа решења: Иван Стошић
Тестер: Владимир Миленковић
Одржавајмо у сваком тренутку граф са следећим особинама:
- Постоје три врсте чворова, “унутрашњи”, “листови” и један специјалан “празан” чвор. Унутрашњи чворови имају тачно две излазне гране, које ћемо звати “левом” и “десном”. Листови немају излазне гране и чувају једну целобројну вредност, коју ћемо звати “лабела”.
- Граф је “непроменљив”, односно, није могуће изменити особине постојећих чворова. Могуће је само додавати нове чворове.
- Сваки чвор чува величину из њега достижног дела графа. За листове, ова величина износи 1. За унутрашње чворове, ова величина једнака је збиру величина чворова до којих се стиже помоћу леве и десне гране. За празан чвор ова величина је 0.
- Аналогно дефинишемо достижни низ лабела за неки чвор. За листове, то је низ од једног елемента - његова лабела. За унутрашње чворове низ се добија конкатенацијом низова левог и десног чвора. За празан чвор је празан низ.
Поред графа, одржавајмо и показивач R на чвор чији ће достижни низ лабела бити једнак тренутној вредности низа a. Упите типа 2 решавамо веома једноставно, крећемо из чвора R и спуштамо се лево или десно у зависности од тога ком елементу низа желимо да приступимо, све док не дођемо до листа.
Упите првог типа решавамо помоћу следећих операција над графом:
-
seci(x, s), враћа два показивача на чворове, где је први чвор такав да је његов достижни низ једнак префиксу достижног низа за чвор x дужине s, а достижни низ другог чвора је једнак остатку достижног низа за чвор x. -
spoji(x, y)враћа чвор чији је достижни низ једнак конкатенацији достижних низова за чворове x и y. Ова операција се може извести на два начина о чему ће бити више речи касније. -
pomnozi(x, k)враћа чвор чији је достижни низ једнак конкатенацији k достижних низова за чвор x.
Наш циљ је да све три операције раде брзо. Тачније, све три операције радиће у сложености линеарној по дубини графа почев од датог чвора или чворова, зато ће нама бити циљ да се ова дубина не повећава превише у току рада.
Следе скице могућих реализација ове три операције:
-
seci(x, s), уколико је s мање од величине левог чвора од x, правимо копију y чвора x чији леви чвор сечемо рекурзивно. Први чвор резултата рекурзивног позива вратимо као први чвор, док други чвор резултата рекурзивног позива закачимо као леви чвор чвора y и као други чвор вратимо управо y. У супротном, аналогно сечемо десни чвор. -
spoji(x, y), насумично изаберемо један од та два чвора (рецимо да је то чвор x), направимо његову копију z, рекурзивно спојимо десни чвор чвора z и чвор y и резултат закачимо као десни чвор z, затим вратимо z. -
pomnozi(x, k), како ће важити k \leq n < 2^{20}, направимо чворове y_0, y_1, \ldots, y_{19}, где је y_0 копија чвора x, а за i > 0 је y_i чвор који се добија “простим” (нерекурзивним) спајањем чвора y_{i-1} са самим собом. Тачније, чвору y_i ће и лева и десна грана показивати на чвор y_{i-1}. Сада је јасно да је низ чвора y_i једнак конкатенацији 2^i низова чвора x. Затим само изаберемо степене двојке у бинарном запису броја k и поново простим спајањем направимо резултујући чвор, водећи рачуна да спајамо од мањих ка већим степенима.
Сада, задатак решавамо на следећи начин. Граф иницијализујемо као бинарно стабло чији листови редом имају лабеле од 1 до N и R постављамо за корен тог стабла. У већини случајева само сечемо делове низа за чвор R и састављамо их у неком другом редоследу. Једини незгодан случај јесте тај када је u > v и l > u-v. Тада се једно парче оригиналног низа циклично понавља одређен број пута, и ту нам је потребна ефикасна операција pomnozi.
Једна могућа оптимизација јесте да, када број чворова пребаци неку унапред задату границу (рецимо пар милиона), израчунамо цео достижан низ из чвора R, обришемо све чворове и “почнемо испочетка” са тим низом.
Временска и меморијска сложеност: N + Q \log N.
Je li mozemo da dobijem tacno resenje u vidu koda(u c jeziku)
ta resenja su u jeziku c++
Onda ne
Ima li rešenja u Assembleru? iz 20. sam veka toster neće da podrži C++
Zasto ovo resenje za D daje maksimum bodova? https://ideone.com/w0O08P
Jel su slabi primer ili je ovo zapravo tacno?
Da li ovo znači da ne treba proveravati da li duž seče radijalne linije (od centra do neke planete)?
Takođe, kako na efikasan način proveriti da li se date duži seku?
Baš te duži i proveravamo, gledamo da li se seče duž koja spaja dve planete l i r i duž od pošte (centra) do neke treće planete između njih. Nema potrebe da proveravamo preseke prve duži i neke između dve (ne-centralne) planete, jer ako taj presek postoji, sigurno postoji i presek sa bar jednom duži do centra.
Da bi proverili da li se duži AB i CD seku, možemo proveriti da li prava p_1 koja prolazi kroz A i B seče CD, i da li prava p_2 kroz C i D seče AB (ovo je potreban i dovoljan uslov). Prava p seče duž AB ako (i samo ako) su A i B sa različite strane prave, tako da nam je dovoljno četiri izračunavanja funkcije “sa koje strane prave (definisane sa dve tačke) se nalazi data tačka”.
Kako znak vektorskog proizvoda dva vektora zavisi od pravca skretanja između njih, da bi proverili sa koje strane prave definisane sa A i B se nalazi P, treba nam znak (b-a) \times(p-a) = (x_b - x_a)(y_p - y_a) - (x_p - x_a)(y_b - y_a). Za ove potrebe, nije nam bitno koju stranu označava pozitivan rezultat a koju negativan, jer nam je ova provera potrebna samo da bi videli da li se znaci razlikuju.
Napomena: u slučaju da tačke mogu biti kolinearne, situacija se malo komplikuje (zavisi da li nas interesuje slučaj gde se prave dodiruju ili ne) i treba paziti na slučaj gde je vektorski proizvod 0 (tj. tačka se nalazi na pravoj).
Gde mogu da najdem teskt zadatka ?