[Rešenja zadataka] Kvalifikacije 2020 - Drugi krug

Пикадо

Аутор: Никола Пешић
Текст и тест примери: Лазар Миленковић
Анализа решења: Филип Ћосовић
Тестер: Никола Пешић

Анализа

Потребно је наћи све елементе низа A који се појављују бар K пута у низу. Елементи низа A су у интервалу [-N,N] тако да постоји 2 \cdot N+1 различитих вредности које се могу појавити у низу. Можемо искористити помоћни низ B дужине 2 \cdot N+1 који представља број појављивања сваког елемента у почетном низу.

На почетку низ B има вредност 0 на свакој позицији. Једним проласком кроз низ A, када наиђеимо на елемент A_i повећавамо број појављивања тог елемента за 1. Пошто не можемо приступити негативним индексима број појављивања елемента који има вредност X памтимо у низу B на позицији X+N. Тако је интервал [-N,N] пресликан у интервал [0, 2 \cdot N] што нам омогућава да користимо низ.

Проласком кроз низ B пребројавамо и исписујемо све бројеве који су се појавили бар K пута у низу. Ако за неко j важи да је B[j] \geq K то значи да се број j-N појавио бар K пута.

Имплементација коришћењем низа је сложености O(N). Може се користити и структура заснована на претраживачком стаблу (std::map сложености O(N \log N)) или хеш табела (std::unordered_map очекиване сложености O(N)) што нам омогућава решење и када су елементи низа A много велики и немамо довољно меморије да направимо низ који обухвата све потенцијалне вредности.

5 Likes

Полица

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

Анализа

Да би распоред добијен заменом две цифре имао највећу могућу лепоту, желимо да прва цифра буде највећа могућа, па ако иза A_1 постоји нека већа вредност, заменићемо је са оном која је:

  • највећа, и ако постоји неколико истих
  • последњом таквом (да би ставили мању цифру A_1 на место са што мањом “тежином”).

Уколико оваква цифра не постоји, односно A_1 је већа или једнака од свих вредности десно од ње, исти процес пробамо за следећу цифру A_2 (где као кандидате за замену гледамо само оне десно од A_2), и тако даље док не нађемо пар који се може заменити.

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

“Наивно” решење задатка које за свако A_i пролази кроз све цифре десно од ње има временску сложеност O(N^2), тако да се неће извршити у датом ограничењу за последњи подзадатак. Да би избегли овај корак, на почетку програма можемо пронаћи последње појављивање сваке цифре и сачувати то у помоћном низу, што се може искористити да за свако A_i нађемо оптималну замену у константном времену, и самим тим даје укупну временску сложеност O(N).

4 Likes

Златници

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

Анализа

Посматрајмо низове r_i и c_i, који означавају у којој се колони и врсти налазе златници. Видимо да у једном потезу узимамо један златник и мењамо му редни број врсте или редни број колоне за \pm1. Ово значи да ми у једном потезу мењамо вредност једног члана низа r_i за \pm 1, или један члан низа c_i за \pm 1. Нама је циљ да на крају оба низа r_i и c_i постану пермутација скупа \{1,2,3,\cdots,n\}. Означимо са R минимални број потеза да се ово учини са низом r_i а са C минималан број потеза да се ово уради са низом c_i. Тада је тражено решење очито барем R+C.

Решимо ово за низ r_i. Ако на крају добијемо низ x_i онда нам је требало S=|r_1-x_1|+|r_2-x_2|+\cdots+|r_n-x_n| потеза. Приметимо да ако r_i<r_j и x_i>x_j, тада заменом вредности x_i и x_j не повећавамо (а потенцијално смањујемо) резултат. Ово се доказује анализом случаја за све поретке ових 4 вредности. Овиме видимо да је једно од случајева када се најбоље решење достиже је када су бројеви x_i у истом поретку као и бројеви r_i. Ово значи да када је низ r_i сортиран, онда је R=|r_1-1|+|r_2-2|+\cdots+|r_n-n|. По истом принципу важи ако је низ c_i сортиран тада C=|c_1-1|+|c_2-2|+\cdots+|c_n-n|.

Прво ћемо анализирати шта се дешава у случају да могу постојати два (или више) новчића на истом пољу у истом тренутку. Тада су координате златнике очигледно независне, па је одговор управо R+C.

Међутим, испоставља се да је ово одговор и у правом задатку. Ово је тако јер је могуће извршити низ потеза тако да се достигне једнакост и за R и за C а да при томе никад не буду два златника на истом пољу. Прво ћемо распоредити златнике у различитим редовима у оптималном броју потеза, а после тога је очито јасно да нема проблема распоредити их по различитим колонама јер то што су у различитим редовима гарантује да су на различитим пољима. За тај први део је очито довољно да за сваку колону доведемо златнике на права места без преклопа, јер златници који крећу у различитим колонама ће остати на различитим пољима док само мењамо у којим се редовима мењају. У свакој колони ће постојати неки златници који иду “на горе” и они који иду “на доле”. У сваком тренутку ћемо узети онај највиши који треба да иде на горе а није у правом реду и померити га на горе или најнижи који трева да иде на доле а није у правом реду и померити га на доле. Јасно је да овако неће бити никад два на истом пољу јер ако неки златник што иде на горе се поклопи са неким што иде на горе, то је у контрадикцији са тиме да смо изабрали највиши такав златник, а ако се поклопи са неким што иде на доле, то је у контрадикцији са тиме да су почетне вредности r_i у истом поретку као и коначне вредности r_i.

Овај алгоритам се сада лако имплементира у O(n \log (n)) са обичним сортом или O(n) са counting сортом.

4 Likes

ЈАГ

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

Анализа

Скуп територија можемо репрезентовати као неоријентисан граф, у коме су чворови баш тих N територија, а гране постоје између парова територија које деле заједничку границу. Тај граф је повезан (јер је од било које територије могуће доћи до било које друге, потенцијално прелазећи преко других територија). Како има тачно N-1 грана (јер толико има парова територија које деле границу), то тај граф представља стабло (повезан граф у коме нема петљи/циклуса).

Дијаметар стабла је дужина пута између два најудаљенија чвора (удаљеност се рачуна као дужина најкраћег пута, тј. број грана на најкраћем путу). Означимо са D дијаметар графа.
Приметимо да ако постоје бар 4 територије такве да је растојање између сваке две једнако дијаметру D, онда други играч може играти тако да први играч мора обојити бар две од те четири територије и због тога је тада раштрканост територија првог играча једнака D. Али раштрканост ће бити једнака D и ако се могу издвојити две (дисјунктне) групе територија (нека су то A и B) које имају по бар два елемента тако да је растојање између сваке територије из прве групе и сваке територије из друге групе једнако дијаметру D. Наиме, и у том случају, други играч може играти тако да први играч мора обојити по једну територију из сваке од двеју група (мисли се на групе A и B) и тада је раштрканости једнака D.

Шта ако стабло (граф) не задовољава горње услове? Нека су u и v чворови који су на растојању D. Претпоставимо да постоји бар још један чвор који је на растојању D од бар једног од чворова (нека је чвор w на растојању D од чвора u). Тада се могу издвојити две (дисјунктне) групе A и B (од којих једна има само један елемент, иначе би у супротном могли применити разматрање из претходног одељка) такве да је растојање између свака два чвора из те две групе једнако дијаметру D. У овом случају резултат зависи од парности броја територија. Ако је број територија непаран, први играч "изводи’’ последњи потез и због тога други играч може играти тако да први играч мора обојити по једну територију иа сваке од двеју група, па је раштрканост једнака D. Ако је број територија паран, онда први играч може играти тако да не узме територију која се налази у групи са само једном територијом. Због тога је раштрканост једнака D-1.

Ако није важио ни претходни услов, онда постоје тачно две територије које су на растојању D (нека су то u и v). У том случају се одређује колико има територија које су на растојању D-1 од једне (или обе) од ове две територије и изводи се слично разматрање као у претходна два одељка са једином разликом што ће сада раштрканост бити D-1 или D-2 зависно од броја територија које су на растојању D-1 од територија u и v (као и од парности броја N, ако постоји по тачно једна територија која је на растојању D-1 од сваке територија u и v).

За крај како одредити дијаметар графа? Један од начина је применом два обиласка у дубину уз одређивање растојања сваког од чворова стабла од полазног чвора). Први обилазак креће од произвољног чвора w, а други од чвора u који је на највећем растојању од чвора w. Нека је чвор v на највећем растојању од чвора u. Може се показати да је растојање између чворова u и v једнако дијаметру стабла.

Сложеност описаног алгоритма је O(N).

4 Likes

Гриц

Аутор: Иван Стошић
Текст и тест примери: Иван Стошић
Анализа решења: Иван Стошић
Тестер: Никола Пешић

Анализа

На основу ограничења y_i \geq H можемо закључити да ће, уколико посматрамо произвољну вертикалну праву која пролази кроз кекс, у сваком тренутку, пресек преосталог кекса са том правом бити или празан, или ће бити једна дуж. Кад ово ограничење не би постојало, било би могуће да Павле поједе парче из “средине” кекса, у том случају би тај пресек могао да се састоји из више дужи. Основна идеја која је заједничка свим решењима јесте да се одржава низ b, где је b_i преостало парче кекса на позицији x = i. У почетку, пре свих упита имамо b_i = 0 за свако i \in [0, W]. Треба обратити пажњу при имплементацији да се не штампа негативан број, односно, ако неки круг прелази икс-осу, не треба смањивати b_i испод 0.

У првом подзадатку, радијус круга је 1, па су измене на низу b тривијалне - уколико круг има y=H, стављамо b_{x} = H-1.

У другом подзадатку, постављамо b_x = \min(b_x, y-2) и b_{x-1} = \min(b_{x-1}, y - \sqrt{3}), слично за b_{x+1}, наравно, уколико су ове x-координате у сегменту [0, W]. Временска сложеност решења прва два подзадатка је O(Q + W).

Трећи подзадатак је уопштење претходне идеје. Тачна вредност на коју треба поставити број b_i је \min(b_i, y - \sqrt{(R+i-x)(R-i+x)}) за све i \in [0, W] \cap [x-R, x+R]. Ова формула се може извести геометријски, помоћу Питагорине теореме. Временска сложеност је O(W + QR).

За решавање четвртог и петог подзадатка неопходне су нам следеће опсервације. Прва је та да је довољно посматрати облик који формирају доњи полукружни лукови додатих кругова. Друга, кључна је да се ниједна два таква лука не могу сећи више од једном, осим ако се не поклапају. Ово се може доказати на следећи начин: Посматрајмо нека два круга. Уколико се они не поклапају, они се могу сећи на највише два места. На основу тога што имају исти радијус, тачке пресека су централно симетрично распоређене у односу на тачку која се налази на средини дужи која спаја центре та два круга. Како овај центар има y-координату већу него “нижи” од та два круга, и једна од пресечних тачака сигурно исто има већу y-координату од центра нижег друга, па не учествује у пресеку доњих полукружница.

Четврти подзадатак се може решити тако што се експлицитно израчуна облик кекса. Сортирамо све кругове по x-координати и обрађујемо их у овом редоследу. Помоћу стека одржавамо скуп полукружница које учествују у коначном облику кекса, као и позиције пресека суседних полукружница. Одговор на неки упит можемо наћи бинарном претрагом по добијеном низу полукружница, или једноставније, обрадом целог низа полукружница тј. експлицитним налажењем свих вредности b_i, у једном пролазу кроз низ. Ово решење је применљиво управо зато што се сваке две полукружнице секу највише једном. Ову идеју није могуће применити уколико то не би важило, на пример, ако би се радијуси датих кружница разликовали. Временска сложеност је O(W + Q \log Q).

Одавде је јасно да решење четвртог подзадатка подсећа на оно што се зове “трик са конвексним омотачем”, где се налази облик који формира пресек полуравни. Други начин да се израчуна овај пресек полуравни јесте помоћу такозваног LiChao сегментног стабла, па је природно покушати прилагодити ту структуру података за овај проблем.

Наиме, формирајмо сегментно стабло, где се у сваком чвору налази опис једне полукружнице, која цела покрива придружени сегмент у стаблу, односно, таква да ако је чвор одговоран за сегмент [x_l, x_r], тада за кружницу важи x-R \leq x_l \leq x_r \leq x+R (услов 1), где је (x,y) њен центар. Додатно, намећемо ограничење да за лист, тј. чвор који одговара сегменту [x, x], пут у стаблу од тог листа до корена садржи круг који у x достиже најмању y-координату, у сваком тренутку. Ако ово важи, јасно је да на упит можемо одговорити у O(\log W), само посматрањем тих O(\log W) чворова на путу од листа до корена.

Како додати нови круг? Посматрајмо рекурзивну функцију која полази од корена стабла, који одговара чвору који чува сегмент [0, W]. Уколико за тренутни чвор не важи услов 1, и сегменти који одговарају кругу и чвору се не секу, можемо одмах изаћи, иначе рекурзивно додајемо круг у оба чвора детета тренутног чвора. На даље претпоставимо да услов 1 важи. Ако у тренутном чвору нема никаквог круга, слободно можемо ставити у тај чвор нови круг и изаћи из функције. Још један случај где можемо одмах ставити круг и изаћи јесте ако је нови полукруг цео испод старог на целом сегменту тренутног чвора [x_l, x_r], што се може једноставно проверити ако израчунамо y-координате пресека полукругова са [x_l, x_r], као по формули датој у решењу подзадатка 3. Уколико је нови полукруг цео изнад старог на том сегменту, не морамо да га додајемо, већ одмах излазимо из функције. Иначе, ова два полукруга се секу на тачно једном месту, унутар сегмента. У тај чвор можемо уписати онај од та два круга који је “доминантан” на бар једној половини сегмента, док други можемо рекурзивно убацити у друго дете тренутног чвора. Временска сложеност овог поступка се разликује од оног за обично сегментно стабло. У току рекурзије долазимо до O(\log W) чворова за које важи услов 1, а за сваки од њих имамо по један рекурзивни пут који се може састојати из највише O(\log W) чворова, па је временска сложеност додавања једног круга O(\log^2W), а целог решења O(W + Q \log^2 W).

7 Likes

Može li efikasnije tj bez sorta? Ako se napravi niz parcijalnih suma zlatnika, po vrsti i koloni. Onda se u O(n) saberu sve razlike tj. odstupanja od idealnih parcijalnih suma (1,2,3…n).

1 Like