[Rešenja zadataka] Kvalifikacije 2019 - Treći krug

Algoritam
1

Ворп Спејс

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

Приметимо да координате можемо да посматрамо независно. Најлакши начин да решимо задатак је анализом случајева. За обе координате разматрамо два случаја, да ли смо прешли преко ивице или не. Посматрајмо x координату почетног и крајњег поља. Уколико нисмо прешли ивицу од поља A_{x} до поља B_{x}, растојање је |A_{x}-B_{x}|. Уколико јесмо и дужина ворп-спејса је D_{x}, растојање је D_{x}-|A_{x}-B_{x}|. Дакле, минималан број корака да би смо се нашли на x координати на којој је крајње поље је \min(|A_{x}-B_{x}|,D_{x}-|A_{x}-B_{x}|). Сличан резултат добијамо за y координату, \min(|A_{y}-B_{y}|,D_{y}-|A_{y}-B_{y}|). Укупан број корака је \min(|A_{x}-B_{x}|,D_{x}-|A_{x}-B_{x}|) + \min(|A_{y}-B_{y}|,D_{y}-|A_{y}-B_{y}|).

5 Likes
2

Моћ низа

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

Начин 1

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

Начин 2

Уколико сортирамо (неким O(N \log N) алгоритмом) све цифре нашег броја, приметимо да ће у оптималном решењу бити узастопни подниз тог сортираног низа (дужине N - K). Таквих поднизова има O(N), па можемо проћи кроз све и изабрати онај који даје максималну разлику квадрата.

Смернице за алгоритам

Уколико користимо први начин потребан нам је бројач појављивања сваке цифре у броју како не бисмо сваки пут кад бројимо пролазили кроз цео број - сложеност имплементације може варирати, али постоји 10 цифара, тако да било шта што користи неколико петљи те дужине пролази. Уколико користимо други начин, у укупној сложености доминира сложеност сортирања - O(N \log N) за неки стандардни сорт, O(N) уколико користимо counting sort.

3 Likes
3

Паковање

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

Задатком је дато укупно N кутија и M предмета, при чему свака кутија има неку своју носивост, док сваки предмет има неку своју тежину и одређену вредност. Такође, кључна ставка у поставци задатка јесте ограничење да је у једну кутију могуће сместити тачно један предмет и то само ако је носивост кутије већа од тежине предмета.

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

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

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

Конкретно, једна од таквих апстрактних структура података јесте приоритетни ред (енг. priority queue), који се обично имплементира преко такозване хрпе (енг. heap), а који на рачун логаритамске сложености уметања произвољног елемента дозвољава вађење члана са максималном вредношћу такође у логаритамској временској сложености по броју елемената.

Смернице за алгоритам

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

5 Likes
4

Пожар

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

Уместо да посматрамо проблем “из перспективе круга”, нађимо за сваку праву скуп кругова имају пресек са њом. Како је i-ти круг садржан у наредном, ако права сече i-ти круг, тада сигурно сече и сваки наредни, што значи да овај скуп кругова чини сегмент, притом, суфикс, низа кругова. Нађимо, дакле, за сваку праву најмањи круг који се сече са њом. Из горе изложеног закључујемо да се овај круг може наћи бинарном претрагом по круговима - ако се неки круг не сече са правом, настављамо претрагу по већим круговима, иначе, памтимо решење и тражимо међу мањим круговима. Након што смо нашли индекс j овог најмањег круга, у низу решења z треба бројевима z_j, z_{j+1}, \ldots, z_n да додамо 1, што можемо урадити тако што додамо 1 броју z_j а након што обрадимо све праве израчунамо префиксну суму низа z, коју штампамо.

Смернице за алгоритам

Да бисмо испитали да ли се права одређена двема тачкама A, B сече са кругом радијуса r са центром у тачки C, најједноставнији начин је да нађемо удаљеност праве AB до тачке C и да тај број упоредимо са r. Израчунајмо двоструку површину троугла ABC као апсолутну вредност векторског производа 2P = |CA \times CB| и дужину дужи |AB|. Како је удаљеност праве AB од C заправо висина троугла h_C, ту висину можемо израчунати преко површине: h_C = \frac{2P}{|AB|}. Притом, све ове операције се могу поуздано израчунати помоћу типа double са релативном прецизношћу 10^{-14} што је довољно добро за овај задатак.

6 Likes
5

Свеска

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

Укратко, решење задатка ће изгледати овако. Користићемо сегментно стабло да одговоримо на упите. Листови у сегментном стаблу ће бити једнаки низу a. Чвор у стаблу који је отац листова a_i, \ldots, a_j ће садржати најмањи број који може бити записан на табли након коначно много потеза игре са бројевима a_i, \ldots, a_j. Овај приступ намеће два главна питања:

  • Зашто је за сваки чвор довољно чувати само најмањи број који се може добити играјући се његовим синовима?
  • Ако је чвор v отац чворова L и R, како искомбиновати вредности сачуване у L и R да се добије вредност за чвор v?

Да бисмо одговорили на ова питања, посматраћемо овај проблем као задатак са полиномима над \mathbb{Z}_2.

Полиноми над \mathbb{Z}_2 уместо бројева

За број a дефинишемо полином P_a(x) над \mathbb{Z}_2 на следећи начин: P_a(x) садржи x^i акко је i-ти бит броја a једнак 1. Приметимо да ако P_a(x) садржи x^i, онда је коефицијент испред x^i тачно 1. На пример, P_5(x) = x^2 + 1, јер у бинарном запису број 5 је једнак 101.

Тада број а\text{ xor }b одговара полиному P_a(x) + P_b(x). Број 2 \cdot a одговара полиному x \cdot P_a(x), и број \frac a 2 одговара полиному \frac {P_a(x)} x (под условом да је a дељиво са 2).

Задатак без операције дељења

Прво ћемо посматрати задатак у случају да опција дељења није на располагању, тј. можемо да користимо само xor и множење (или, у свету полинома, ако користимо сабирање и множење са x).

Приметимо да за било који полином Q(x) над \mathbb{Z}_2, ако почнемо од полинома P_a(x) можемо добити полином P_a(x) * Q(x) применом само ове две операције. На пример, да бисмо добили P_a(x) * Q(x) почевши од P_a(x), прво за свако x^i које има позитиван коефицијент у Q(x) направимо полином x^i * P_a(x). Потом саберемо све те полиноме.

Нека је A скуп полинома. Из Безуовог става сада следи да се применом ове две операције на скуп полинома из A може добити NZD(A) (највећи заједнички делилац полинома из A). Пошто се сабирањем два (различита) полинома који су дељиви са NZD(A) добија полином дељив са NZD(A) (који је једнак или већи од NZD(A)), и такође пошто се множењем полинома са x добија полином дељив са NZD(A), то значи да је NZD(A) најмањи полином који можемо добити применом ове две операције.

Такође, ако имамо два скупа полинома A и B, тада важи NZD(NZD(A), NZD(B)) = NZD(A \cup B). Ово оправдава приступ описан на почетку у којем, да бисмо израчунали најмањи записан број у неком интервалу (за који смо у случају да користимо само две операције закључили да одговара NZD вредности одговарајућих полинома), смо користили сегментно стабло.

Задатак са операцијом дељења

Досадашњи опис решења овог задатка је подразумевао да не користимо операцију дељења са x. Пошто ова операција практично каже да крајњи полином не треба да буде дељив са x (иначе није најмањи), дељење можемо применити тек на крају или чак у сваком кораку током примене NZD операција. NZD полиноми које добијамо у међу-корацима би се у зависности од примене дељења разликовали само у дељивости са x, што је небитно за крајњи резултат. Дакле, дељење са x је довољно применити само на крајњи резултат и игнорисати до тада.

Смернице за алгоритам

Имплементација било која од два упита у сегментом стаблу захтева O(\log{n}) NZD операција.

Да бисмо нашли NZD два полинома P_a(x) и P_b(x) можемо да искористимо неки од стандардних алгоритама, на пример, Еуклидов алгоритам. Тај цео процес у нашем случају, где такође имамо операцију дељења, може да се уради на једноставан начин. Наиме, почнемо од a и b, и све док су оба различита од 0 радимо следеће. Нека је a \leq b, и нека је c број добијен од a множењем (“shift”-овањем) са 2 све док се c и b разликују по дужини у бинарном запису. Потом b заменимо са b\text{ xor }c, и наставимо процес. Кад један од бројева a или b постане 0, вратимо не-нула међу њима на који је примењено дељење са 2 док је то могуће.

5 Likes