[Rešenja zadataka] 2020/2021 SIO - dan 1

Algoritam
1

РНК

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

Подзадатак 1

Користећи 4N упита, можемо одредити цео прототип (за сваку позицију можемо да питамо колико има сваког слова на тој позицији). Након тога можемо пробати сваки интервал за промену, видети да ли даје валидну вакцину. Временска/меморијска сложеност: O(N^2), број позива функцији: 4N.

Подзадатак 2

Слично претходном подзадатку, можемо открити цео прототип, али овај пут смемо користити највише 3 упита по позицији. То није проблем, јер можемо питати за три кодона, ако ниједан не важи, знамо да је у питању четврти кодон. Одредимо кодон који се појављује више од \frac{N}{2} пута, рецимо да се појављује x пута, док се његов комплемент појављује y пута. Желимо да се најчешћи кодон у нашем интервалу појављује макар \frac{x-y}{2} пута више од комплемента. Не сме да се појављује ни превише пута, јер онда његов комплемент постаје елемент који се појављује више од \frac{N}{2} пута, срећом у већини случајева можемо наћи баш интервал у ком се најчешћи кодон појављује тачно \lceil\frac{x-y}{2}\rceil пута више од комплемента. Једини случај у којем то није могуће је уколико је N непаран број и важи x+y=N, у том случају који год интервал да изаберемо, постојаће елемент који се појављује више од \frac{N}{2} пута, па решење не постоји.

Уколико то није случај, постоји одговарајући интервал, и то одговарајући интервал који је и префикс. Назовимо са f(i) разлику броја појављивања најчешћег елемента и његовог комплемента у првих i елемената. Јасно је да важи f(0) = 0 и f(N) = x-y. Како се f(i) и f(i+1) разликују за највише 1, можемо рећи да је у неком смислу ова функција непрекидна, тј. постоје индекси за које износи 0 и x-y, постоје и индекси где износи и било шта између тога, укључујући и \lceil\frac{x-y}{2}\rceil. Самим тим, постоји префикс који нам одговара, и можемо га једноставно наћи.

Временска/меморијска сложеност: O(N), број позива функцији: 3N.

Подзадатак 3

Овај подзадатак веома је сличан претходном, нећемо директно одредити цео прототип, него ћемо искористити 3 позива функцији да за сваки кодон одредимо колико пута се појављује, тј. да одредимо који кодон се појављује највише пута. Када имамо ту информацију, можемо да израчунамо f(i) са два позива функцији. Можемо да израчунамо f(i) и одаберемо оно које нам одговара. Временска/меморијска сложеност: O(N), број позива функцији: (највише) 2N+3.

Подзадатак 4

Нађимо колико се који кодон појављује, односно који се појављује најчешће. Нађимо сва појављивања његовог комплемента у низу користећи до сад укупно N+3 позива функцији. Тих појављивања може бити највише \frac{N}{2}. За сваки префикс који се завршава на једном од ових појављивања, откријмо колико се пута до њега појављује најчешћи кодон. Ова информација нам, због непрекидности наше функције, помаже да одредимо између која два појављивања се налази префикс који тражимо. Када нађемо ту информацију, можемо урадити бинарну претрагу, да нађемо тачан потребан индекс. Временска/меморијска сложеност: O(N), број позива функцији: (највише) 1.5N+\lceil logN\rceil+3.

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

Користићемо бинарну претрагу да нађемо i за које важи f(i) = \lceil\frac{x-y}{2}\rceil. Знамо f(0) = 0 и f(N) = x-y, проверавамо f(mid). Важиће да ће се \lceil\frac{x-y}{2}\rceil налазити или између f(l) и f(mid) или између f(mid) и f(r) (можда и на оба места, али нама је довољно једно). Ово важи по непрекидности наше функције. Онда настављамо бинарну претрагу у делу који садржи вредност коју тражимо. Временска/меморијска сложеност: O(logN), број позива функцији: (највише) 2\lceil logN\rceil+3.

2

Марско

Аутор: Тадија Шебез
Текст и тест примери: Тадија Шебез
Анализа решења: Тадија Шебез
Тестирање: Алекса Плавшић

Решење када су све вредности у низу A једнаке

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

Решење када су све вредности у низу W једнаке

За свако возило важи да Марско може безбедно да се вози по било ком путу или уопште не може безбедно да се вози. У првом случају је решење величина повезане компоненте у којој се град налази, а у другом случају решење је 1. И овај подзадатак решавамо DFS алгоритмом.

Решење за N, M \leq 250

За сваки град i нађимо скуп градова које Марско може да посети кренувши из i-тог града ако користи само возило које је затекао у почетном граду. Направимо усмерени граф тако што ћемо додати грану од i-тог града до сваког града из претходно поменутог скупа. Решење за град i је број чворова које можемо да посетимо кренувши од чвора i у усмереном графу. Овај подзадатак такође можемо да решимо применом DFS алгоритма. Временска сложеност овог решења је O(N^3).

Решење за N, M \leq 2500

Кренимо из града i и памтимо највећу вредност A за градове које смо посетили. Убацимо све путеве од посећених градова у heap структуру података. Узмимо пут са најмањим W и ако је ова вредност мања од највећег A за посећене градове, можемо да пређемо преко тог пута и посетимо нови град ако већ није посећен. Ако смо посетили нови град ажурирамо максимално A и додајемо нове путеве на heap. Када више немамо путева или сви путеви на heap-у имају превелику вредност W, прекидамо и памтимо број посећених чворова као решење за град i. Ово решење покрећемо за сваки град па је временска сложеност O(NMlogM)

Решење за 100 поена

Решење за неки град једнако је решењу града са највећим A_i међу градовима које може да посети. Посматрајмо град i и скуп S свих градова који не могу да посете град са већим A од свог. Нека је j град са најмањим A међу градовима из скупа S који могу да посете град i. Решење за i је исто као решење за j. Доказаћемо претходно тврђење тако што ћемо показати да i може да посети j. Ако i може да посети неки град k са A_k \geq A_j, може и да посети j тако што оде до k, пређе у возило из тог града, врати се у i и оде у j обрнутим путем којим би се од j дошло до i (знамо да су на том путу сви W_e \leq A_j \leq A_k јер j не може да посети град са већим A). Ako je A_k < A_j за све градове које i може да посети, онда постоји град у скупу S који може да посети i и има мање A него град j, што је контрадикција. Сада знамо да је решење за сваки град једнако решењу за најмањи град по вредности A у скупу S који може да посети тај град и можемо да решимо задатак на следећи начин. Процесирајмо градове растуће по њиховим вредностима A. Када процесирамо неки град i додајемо све гране e које имају W_e мање или једнако A_i. За сваку повезану компоненту чувајмо највеће A за чворове у њој. Ако је највеће A за чворове у компоненти чвора i једнако A_i, чвор i је у скупу S и његово решење је величина повезане компоненте. Такође је то и решење за сваки чвор у овој компоненти који се већ није нашао у компоненти неког чвора из скупа S. Moжемо да одржавамо ове градове за сваку компоненту у низу и да их пребацујемо из мање у већу компоненту када се догоди спајање две компоненте. На овај начин добијамо решење које ради у временској сложености O(NlogN + MlogM).

3

Тачке

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

Одговор на упит је Da ако се тачка P налази у унутрашњости или на конвексном омотачу подниза тачака од L до R (са специјалним случајем када су све тачке колинеарне и конвексни омотач је заправо дуж или једна тачка).

Решење када је N, Q \leq 100

За сваки упит можемо у O(N^2) да нађемо конвексни омотач и проверимо да ли се тачка P налази унутар или на омотачу. Временска сложеност је O(QN^2).

Решење када је N, Q \leq 2500

Решење је исто као за прошли подзадатак само што је потребан ефикаснији алгоритам за налажење конвексног омотача. Са алгоритмом у O(NlogN) добијамо временску сложеност O(QNlogN).

Решење када је N, Q \leq 10^5 и све тачке су на X оси.

Конвексни омотач је заправо дуж на X оси па су нам битне тачка са најмањом и тачка са највећом X координатом за сваки упит. Ако за проналажење минимума и максимума користимо сегментно стабло добијамо временску сложеност O(QlogN).

Решење када је N, Q \leq 10^5 и постоје две праве тако да се свака тачка из низа A налази на бар једној од њих

Узмимо 3 различите тачке. Бар један од 3 пара ових тачака се сигурно налази на истој правој. Испробајмо сва три пара и проверимо да ли су све тачке које нису колинеарне са тренутним паром међусобно колинеарне. На овај начин ћемо наћи две праве које садрже све тачке из низа. За сваки упит битне су нам само екстремен тачке на овим правама и њих можемо брзо да нађемо за сваки упит уз помоћ сегментног стабла. На овај начин добијамо конвексни омотач са највише 4 тачке и једноставно можемо да проверимо да ли се тачка P налази у њему. Временска сложеност овог алгоритма је O(QlogN).

Решење када је N, Q \leq 6 \times 10^4 и све координате су цели бројеви из интервала [-500, 500]

За скуп тачака са целобројним координатама у квадрату димензија M \times M највећи број тачака на конвексном омотачу је око M^{2/3}. Решење за овај подзадатак је да чувамо конвексне омотаче у сваком чвору сегментног стабла и радимо њихова спајања. Временска сложеност је O(QlogNM^{2/3}). Ово решење такође пролази и све претходне подзадатке.

Решење за 100 поена

За сако i нађимо најмању границу G_i тако да се тачка P налази у конвексном омотачу подниза од i до G_i. Ако не постоји такав подниз узећемо G_i=N+1. Приметимо да је низ G_i неопадајући, па га можемо наћи применом two pointers технике. Потребна нам је још структура података која подржава операције убацивања и избацивања тачака и одговара на питање да ли је тачка P унутар конвексног омотача. Посматрајмо случај када се тачка P налази у конвексном омотачу неког скупа тачака. За сваку праву која пролази кроз P, постоје две тачке које су са различитих страна те праве, или постоји тачка која је на тој правој. Постматрајмо сада слчај када тачка P није у конвексном омотачу неког скупа тачака. У овом случају постоји права која пролази кроз P таква да су све тачке из скупа са једне њене стране. Посматрајмо тачке из овог скупа сортиране кружно по углу око P. Ако постоји права таква да су све тачке са једне њене стране постоји угао већи од 180 степени између две суседне тачке, а у супротном не постоји. Сада можемо да одговарамо на питања да ли се тачка P налази у конвексном омотачу скупа тачака и да подржимо убаивање и избацивање тачака тако што држимо тачке у \text{std::set}-у сортиране по углу. Тачке можемо да поредимо по углу ако гледамо у којем квадранту се налазе и ако гледамо знак векторског производа за тачке у истом квадранту. Када убацујемо тачку две тачке престају да буду суседне и добијамо нова два пара суседних тачака па треба да ажурирамо информацију о томе да ли постоји угао већи од 180 степени. Слично тако код избацивања тачке избацујемо два пара из разматрања и убацујемо један. Један изузетак на који треба пазити је случај када се нека тачка поклапа са P и можемо да чувамо информацију о броју таквих тачака и да их не убацујемо у \text{std::set}. Када уз помоћ ове структуре урадимо two pointers и нађемо границе G_i, на упите лако можемо одговорити упоређивањем G_{L_i} и R_i. Временска сложеност овог решења је O(NlogN)