[Rešenja zadataka] 2020/2021 Državno

Algoritam
1

Квадрати узвраћају ударац

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

Подзадатак 1

У овом подзадатку сваке две тачке могу формирати квадрат описан у задатку, па треба избројати број свих парова тачака. Одговор је \frac{N(N-1)}{2}.

Подзадатак 2

Није тешко приметити да тачке (x_1, y_1) и (x_2, y_2) могу бити доње лево и горње десно теме квадрата чије су странице паралелне осама ако и само ако дуж која спаја ове две тачке гради угао од 45 степени са x осом у позитивном смеру (тј. паралелна је правој y=x у координатном систему). Ако претворимо изразимо овај услов помоћу координата, видимо да описани квадрат постоји ако и само ако важи x_1-y_1=x_2-y_2.

Дакле, неопходно је израчунати број парова тачака \{(x_i, y_i), (x_j, y_j)\} датог скупа за које важи x_i-y_i=x_j-y_j. Да бисмо ово ефикасно урадили, имамо више приступа. Да бисмо решили овај подзадатак, није неопходно бити превише пажљив, па за сваки пар тачака можемо проверити да ли важи дати услов. Сложеност овог решења је O(N^2).

Подзадатак 3

У овом подзадатку морамо пажљивије избројати парове за које важи горњи услов. Довољно је направити матрицу A димензија 1001\times 1001 такву да A_{i, j}=1 ако и само ако је тачка (i, j) у скупу задатих тачака, где су i, j=0, 1, \dots, 1000. Тада, за сваку могућу вредност x_i-y_i, можемо избројати колико се тачака налази на одговарајућој дијагонали матрице. Нека је за дијагоналу са x_i-y_i=t овај број једнак k_t. Тада је одговор \sum_{t=-1000}^{1000}\frac{k_t(k_t-1)}{2}.

Алтернативно, не морамо формирати матрицу, већ је довољно да за сваку могућу разлику x_i-y_i прођемо кроз све тачке скупа, за сваку од њих проверавајући да ли има одговарају разлику координата, и на тај начин одредимо број k_t. Одговор је исти као и у претходном пасусу. Сложеност овог приступа је O(\max\{|x_i-y_i|\}\times N).

Подзадатак 4

У овом делу задатка морамо ефикасно одредити бројеве k_t дефинисане горе. Ово можемо урадити сортирајући низ тачака по разлици x_i-y_i, а затим проласком кроз низ утврдити колико тачака међусобно има исту разлику x_i-y_i (при чему није од нарочитог значаја конкретна вредност те разлике). Одговор је исти као и у претходном подзадатку.

Смернице за имплементацију

Због величине бројева у задатку (а и потенцијалне величине одговора), потребно је користити 64-битне бројеве, да не би дошло до прекорачења и погрешног одговора.

1 Like
2

Предузеће

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

Подзадатак 1

У овом подазадатку можемо искористити чињеницу да важи k_{i+1}=2*k_{i}-k_{i-1}-a_{i} (осим ѕа ѕапослене 1 и n који имају само једног суседа). Дакле да бисмо нашли компетентност i+1-ог запосленог довољно је да нађемо компетентност првих i запослених. Почев од k_{1}=0 можемо рекоструисати читав низ. Након тога је потребно проверити да ли добијени низ задовољава свих n једначина и исписати -1 уколико оне нису задовољене.

Подзадатак 2

У овом подзадатку треба приметити да нам је довољно само да контруишемо низ разлика компетентости суседних запослених. На осонову тих разлика и услова k_{1}=0 можемо рекоструисати тражени низ. Посматрајмо допринос неког пара запослених x и y као проток интензитета k_{x}-k_{y} који тече од запосленог x ка запосленом y. Ако замислимо да у сваког запосленог x улази неки проток интензитета a_{x} са стране можемо обезбедити да је укупан проток сваког запосленог нула.

Вредности свих протока можемо одредити тако што из сваког запосленог пустимо да тече проток интензитета a_{x} од њега па све до шефа. Проток кроз неки пар суседних запослених је укупан проток који прелази преко те гране на крају. Приметимо такође да је укупан проток кроз запосленог 1 једнак збиру доприноса свих запослених. На основу тога се може показати да решење постоји ако и само ако је збир свих доприноса нула. Пошто је удаљеност сваког запосленог од шефа у овом подзадатку највише log(N) укупна сложеност је O(N*log(N)).

Подзадатак 3

У овом подзадатку можемо применити исти алгоритам као за прошли подзадатак. У овом подзадатку сложеност таквог алгоритма је O(N^2).

Подзадатак 4

За максималан број поена потребно је рекоструисати низ разлика компетентности суседних запослених у линеарној сложености. Ово можемо урадити тако што за сваког запосленог запамтимо оне запослене којима је он надрећен и тражени низ разлика рекоструишемо са десна на лево.
Ако разлику запосленог i означимо са r_{i}=k_{i}-k_{h_i} можемо приметити да важи r_{i}=a_{i}-s где је s сума разлика свих запослених којима је он надређен. Пошто се његови подређени налазе после њега у низу можемо сматрати да су њихове разлике већ израчунате (јер разлике рачунамо са десна на лево) па је могуће одредити r_{i}. Приметимо да је сваки запослени подређен највише једном запосленом па је укупна сложеност овог алгоритма O(N).

3

Прослава рођендана

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

Решење за N \leq 20:

Можемо пробати сваки подскуп гостију. Узмемо максималан одговарајући подскуп. Временска сложеност: O(2^N\cdot N), меморијска сложеност: O(N).

Решење за M=2:

Желимо да одаберемо паран број људи и да они укупно донесу паран број поклона. Поделимо људе у две групе, оне које доносе паран број поклона и оне који доносе непаран број поклона. Сортирајмо људе у обе групе опадајуће по броју поклона. Ако имамо најмање две особе у некој групи, сигурно ћемо моћи без конфликта да позовемо две особе из те групе, а наравно ми ћемо одабрати две особе са највише поклона. Овај процес понављамо док нам у обе групе остане 0 или 1 особа. Тада стајемо, јер те људе не можемо позвати - или број званица неће бити паран, или укупан број њихових поклона. Временска сложеност: О(NlogN), меморијска сложеност: O(N).

Решење за 1≤a_i≤2:

Постоје само две врсте људи: људи који доносе један поклон и људи који доносе два поклона. Означимо са k број позваних људи који доносе један поклон, а са t број позваних људи који доносе два поклона. Мора важити да су t+k и 2\cdot t + k дељиви са M. Фиксирајмо остатак при дељењу t са M и остатак при дељењу k са M. Уколико важе наши услови, узећемо што веће t и k које задовољава дате остатке. Узимамо максимум од свих комбинација остатака. Временска сложеност: O(M^2), меморијска сложеност: O(1).

Решење за 1≤N≤10000:

Користимо динамичко решење, стање је dp[i][j][k] и означава најбоље решење посматрајући првих i људи, тако да је остатак при дељењу броја одабраних људи са M баш j, а остатак при дељењу збира њихових поклона са M баш k. За i-ти елемент важи да можемо или да га узмемо или не, па је рекурентна веза:

dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-1][k-a_i] + a_i).

Битно је напоменути да је одузимање у овој рекурентној вези спроведено по модулу M, на пример 2-5 по модулу 7 је 4. Последњи корак нам је да решење оптимизујемо меморијски, пошто нам тренутно заузима превише меморије. То можемо урадити тако што приметимо да кад рачунамо стања за i, користимо искључиво стања за i-1, па је увек довољно чувати само претходна стања. Временска сложеност: O(NM^2), меморијска сложеност: О(M^2).

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

Одвојимо госте у групе по остатку при дељењу њиховог број поклона са M. Имамо M таквих група, једну за остатак 0, једну за остатак 1, …, једну за остатак M-1. Сортирајмо опадајуће по броју поклона сваку групу.

За сваку групу, највише M-1 људи неће бити позвани (уколико је макар M људи непозвано, можемо да позовемо било којих M непозваних људи, а да не нарушимо остатке при дељењу). То нам говори да ће сви гости у групи који нису у најмањих M-1 сигурно бити позвани, за остале морамо наћи оптимално решење.

У свакој групи имамо највише M-1 елемената које посматрамо, укупно немамо више од M^2 елеманата. На том броју елемената можемо применити решење за претходни подзадатак. Временска сложеност: O(NlogN + M^4), меморијска сложеност: O(M^2).

4

Жице

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

Једном компонентом жица зваћемо скуп свих жица до којих стигне струја ако додирнемо неку од њих.

Решење за N \leq 5000:

Конструишимо граф где су чворови жице, а грана између два чвора постоји ако се жице секу. Након овога довољно је применити било који графовски алгоритам који може бројати број компонентни, на пример ДФС (претрагу у дубину). Временска и меморијска сложеност: O(N^2).

Решење када се жице секу са сваком жицом до које стиже струја:

Другачије речено, у свакој компоненти жица се свака жица сече са сваком. За овај подзадатак нам је била потребна главна идеја у задатку: када сортирамо жице по A_i свака компонента жица ће се састојати од узастопних жица. Ово можемо доказати тако што претпоставимо супротно: постоји компонента која се састоји од макар два (одвојена) узастопна низа жица. Да би оне биле у истој компоненти, морају се сећи нека жица из ‘левог’ интервала и нека из ‘десног’ интервала. Можемо видети ипак (најбоље ако ово нацртамо), да ће било која жица између та два интервала такође морати да сече макар једну од жица из та два интервала, да би стигла до друге стране.

Када знамо ово, можемо да сортирамо жице по A_i, па идемо са лево на десно. Нова компонента почиње на индексу i ако се жице A_i и A_{i-1} не секу. Временска сложеност: O(NlogN), меморијска сложеност: O(N).

Решење када се струја шири на још највише 5 жица:

Другачије речено, свака компонента је величине највише 6. Поново сортирамо жице по A_i. Можемо решити подзадатак да више начина. Идемо опет са лева на десно, и проверавамо за наредних 6 жица да ли припадају истој компоненти, ако не, проверимо уместо тога за 5 жица, итд… Временска сложеност: O(NlogN), меморијска сложеност: О(N).

Може се решити и графовски слично решењу за N \leq 5000.

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

Поново сортирајмо жице по A_i. Нумеришимо их са лева на десно бројевима од 1 до N. Сада сортирајмо жице по B_i, и доделимо им претходне вредности (редни број жице при сортирању по A_i). Тако добијамо пермутацију бројева од 1 до N. Означимо са maxx_i максимум првих i елемената у пермутацији.

Тражимо крај прве компоненте: то је најмање i, тако да су првих i елемената пермутације, пермутација бројева од 1 до i. То је у ствари најмање i за које важи да је maxx_i = i. Сличним резоновањем, долазимо до закључка да се свака компонента завршава индексом такав да важи maxx_{index} = index, па је само потребно да избројимо такве индексе. Временска сложеност: O(NlogN), меморијска сложеност: O(N).

5

Јакузе

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

Решење за N=1,Q\leq200

Овај подзадатак је само најпростија симулација. Приметимо да је Мома у сваком тренутку освојио неки интервал и да су једина нова поља које може освојити она два на крајевима интервала. Сада у сваком тренутку видимо да ли је једно од та два суседна поља баш оно које нам треба и ако јесте освојимо га. Сложеност O(QMN).

Решење за Q\leq200

И овај подзадатак је обична симулација, али се мора генерализовати на дводимензионе табле. Памтићемо за свако i да ли је поље означено са тим бројем суседно некоме од тренутно освојених поља. Онда, када то поље освојимо означићемо његове суседе као могуће за освајање. Тако, итерирајући по вредностима од 2 до MN можемо да утврдимо да ли је могуће да Мома испуни задатак. Сложеност O(QMN).

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

Приметимо следећи потребан и довољан услов да Мома испуни задатак:
Нека кажемо да је поље лоше ако су му сви суседи означени са вредностима већим од његове вредности. Мома може да испуни свој задатак ако и само ако постоји тачно једно лоше поље.
Докажимо ово. Приметимо да је поље означено са бројем 1 свакако лоше. Ако је могуће да Мома испуни задатак онда свако друго поље има неког суседа којег је Мома већ освојио у том тренутку - то јест. неког суседа са мањим индеском од њега, па је један смер доказан. У другом смеру, ако претпоставимо да свако поље са индексом >1 има суседа мањег индекса од њега, онда можемо лаком индукцијом да докажемо да Мома може да испуни свој циљ: по хипотези, Мома може да освоји првих k поља, а поље са индексом k+1 има неког суседа са мањим индексом, то јест неко већ освојено поље, стога Мома може да настави освајање.
Сада кад смо доказали ово, потребно је у сваком тренутку пазити колико постоји лоших поља. На почетку пребројимо колико је лоших поља и приметимо да кад заменимо два поља, то може једино да промени “лошост” највише 10 поља: та два што смо заменили и њихових суседа. Онда напросто ажурирамо да ли су она постала лоша сад и испишемо “DA” уколико имамо само једно лоше поље и “NE” у супротном. Сложеност O(NM+Q).

6

НЗД пермутације

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

Решење за N \leq 9

Можемо да изгенеришемо све пермутације и нађемо тражени збир.

Решење за остале подзадатке

Приметимо да се свака два броја из низа A појављују као суседни у тачно 2 (N-1)! пермутација, па је решење збир највећих заједничких делилаца свих парова пута 2 (N-1)!. Када је N \leq 1000 можемо да прођемо кроз све парове, док је код остала два подзадатка потребно прво пребројати колико се пута која вредност појављује у низу.

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

Нека је cnt_i број појављивања броја i у низу, а d_i број чланова низа који су дељиви са i. Низ d_i се може наћи по формули d_i = \sum_{j=1}^{i*j \leq M} cnt_{i*j} у O(M log M) где је M највећи број у низу. Нека је dp_i број парова чији је НЗД једнак i. Приметимо да је \binom{d_i}{2} број парова чији је НЗД дељив са i, па када од тога одузмемо број парова чији је НЗД једнак 2i, 3i, … добијамо број парова чији је НЗД једнак i. Сада можемо израчунати низ dp од dp_n до dp_1 по формули dp_i = \binom{d_i}{2} - \sum_{j=2}^{i*j \leq M} dp_{i*j}. Временска сложеност решења је O(M log M), а меморијска O(M).

Напомена: Рачунање низова d_i и dp_i је сложености O(M log M) јер се за њихово израчунавање пролази кроз цео низ, па кроз сваки други члан, затим кроз сваки трећи, … У збиру то је \sum_{i=1}^{M} \lfloor \frac{M}{i} \rfloor што је приближно једнако M пута H_M = \sum_{i=1}^{M} \frac{1}{i}. H_n су хармонијски бројеви и они се понашају као природни логаритам.