[Решења задатака] 2024/2025 Изборно Дан 2

Algoritam
1

Налбандиан

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

Пре свега, потребно је да адекватно замислимо овај турнир. Приметимо да структура турнира представља укорењено бинарно стабло са 2N-1 чворова. Такмичари су у чворовима индексираним бројевима од 1 до N, а мечеви у чворевима индексираним бројевима од N+1 до 2N-1. Деца чвора N+i су чворови A_i и B_i. Чворови такмичара су листови, па немају децу. Корен овог стабла је 2N-1.

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

Први подзадатак

За сваки упит можемо пробати све такмичаре x који се не налазе у скупу такмичара датом у упиту. За такмичара x је оптимално да победи све своје мечеве. За такмичаре из скупа, оптимално је да победе све своје мечеве, сем ако се такмиче против такмичара x. Уколико у мечу учествују два такмичара који нису x, нити су из скупа, није нам битно ко побеђује.

Уколико се приликом овог процеса сусретну два такмичара из датог скупа, x није валидан кандидат да их све победи, у супротном смо нашли кандидата и увећавамо одговор за 1.

Временска сложеност: O(QN^2 + \sum K_i)
Меморијска сложеност: O(N)

Други подзадатак

У претходном подзадатку симулирамо доста истих ствари без обзира на то који x одаберемо. Покушајмо да то избегнемо како бисмо убрзали упуте.

Нађимо начин да проверимо да ли је x валидан кандидат, без да симулирамо процес турнира. Означимо са s_p број такмичара из упита који се на почетку налазе у подстаблу чвора p.

Кренимо од корена стабла. Нека су његова деца чворови p и q:

  • уколико s_p \geq 2 и s_q \geq 2, онда које год x одаберемо, нека два такмичара из скупа ће се сусрести у подстаблу у којем није x - дакле, одговор је 0
  • уколико s_p \leq 1 и s_q \leq 1, сви кандидати у оба ова подстабла су валидни
  • уколико s_p \leq 1, а s_q \geq 2 (аналогно је и у супротном случају), такмичара из скупа из подстабла чвора p може да сретне најраније у финалу, док све из подстабла чвора q (уколико постоје) мора срести раније у турниру. Зато валидан кандидат, уколико постоји, дефинитивно се налази у подстаблу чвора q. Премештамо се у чвор q и одатле рекурзивно понављамо ову анализу случајева.

Настављамо овај процес било док не дођемо до неког листа и вратимо одговор, или до првог случаја, где кандидат не постоји.

Временска сложеност: O(QN + \sum K_i)
Меморијска сложеност: O(N)

Трећи подзадатак

Једини случај који морамо избећи јесте да се оба такмичара налазе у неком подстаблу, а да се наш кандидат x не налази у том подстаблу. У том случају би се та два такмичара срела, пре него што би срели такмичара x.

Прво подстабло у којем се налазе оба такмичара зове се најнижим заједничким претком (lowest common ancestor) и може се наћи у временској сложености O(\log N) са претпроцесирањем (може и брже, али нема потребе). Сва остала подстабла су претци LCA, тако да је довољно да наш кандидат буде у подстаблу чвора који је LCA два чвора из упита.

Одговор је, дакле, број листова у том подстаблу, не рачунајући два чвора из упита.

Временска сложеност: O(Q\log N + N)
Меморијска сложеност: O(N)

Четврти подзадатак

Случај када K = 2 решавамо исто као у претходном подзадатку. Када K = 3, поново не сме да нам се деси да имамо два такмичара из упита који су у истом подстаблу, а да наш кандидат x није у њему - једино што овај пут имамо укупно три такмичара у упиту.

Нађимо LCA за сва три пара такмичара. Приметимо да ће два од три LCA бити исти чвор и да ће бити предак трећег LCA.

Пример са 5 такмичара:


LCA за (1, 3) и (5, 3) је чвор 9, који је предак чвору 8 - који је LCA за (1, 5).

Довољно је да се x налази у подстаблу трећег (најнижег) LCA (у претходном примеру чвор 8) - одговор можемо израчунати на исти начин као у претходном подзадатку.

Временска сложеност: O(Q\log N + N)
Меморијска сложеност: O(N)

Пети подзадатак

Дати турнир формира балансирано бинарно стабло - за сваки чвор који није лист и његову децу p и q, дубине њихових подстабала се разликују за највише један. Дубина оваквог стабла је O(\log N).

Можемо применити исто решење из другог подзадатка, само што више не можемо да израчунамо унапред све вредност s_p, јер је N превелико.

Можемо наћи Ојлеров обилизак стабла (пустити претрагу по дубини, DFS, из корена, и записати чворове у реду посећивања) и поређати такмичаре из упита по том редоследу. Након тога s_p можемо наћи бинарном претрагом по том низу.

Временска сложеност: O(Q\log N\sum \log K_i+ \sum K_i \log K_i + N)
Меморијска сложеност: O(N)

Алтернативно решење: Уколико је K_i > 20, одговор је нула (пошто ће сваки такмичар имати мање од 20 мечева, не може победити више од 20 противника). У супротном применити решење из следећег подзадатка.

Шести подзадатак

Можемо наћи LCA за све парове такмичара из упита. Уколико имамо два LCA тако да ниједан није предак другог, одговор је 0 - оба подстабла тих LCA имају макар два такмичара из упита, а пошто немају пресека, наш кандидат се не може наћи у оба.

У супротном, сви LCA-ови су на истом путу од корена до неког листа. Узмимо најдубљи LCA - валидни кандидат је сваки такмичар из овог подстабла, који није у упиту.

Временска сложеност: O(QK_i^2\log N + N)
Меморијска сложеност: O(N + K^2)

Решење за 100 бодова

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

Можемо наћи Ојлеров обилизак стабла и поређати такмичаре из упита по том поретку. Довољно је посматрати LCA-ове узастопних такмичара у таквом поретку, којих је K-1.

Доказ: Посматрајмо нека два неузастопна такмичара у претходном поретку p и q (рецимо да је p пре q у поретку), као и њихов LCA x. Пошто је x LCA ова два чвора, они се налазе у различитим подстаблима његове деце. Такође, пошто су p и q неузастопни у Ојлеровом поретку, то значи да постоји чвор t који је у истом подстаблу као један од та два чвора. Без умањења општости, рецимо да је у питању чвор p - то значи да је LCA од (t, q) такође x:

  • уколико су t и q суседни у Ојлеровом поретку, доказали смо да се x може и тако наћи
  • уколико нису, понављамо процес за t и q, док не дођемо до суседних такмичара. Процес ће се евентуално завршити јер су t и q дефинитивно ближи у поретку него p и q.

Ако их тражимо тим редом, биће сортирани по Ојлеровом поретку, па можемо једноставно проверити да ли се сви налазе на истом путу од корена користећи време уласка и изласка у чворове (добијене приликом DFS), као и наћи најдубљи како бисмо нашли решење уколико постоји.

Временска сложеност: O(\sum K_i (\log K_i + \log N) + Q + N)
Меморијска сложеност: O(N)

2

Сабирање разапињућих стабала

Аутор: Павле Мартиновић

Текст и тест примери: Милош Милутиновић

Анализа решења: Милош Милутиновић

Тестирање: Немања Мајски

Посматрамо све операције mod K. Нађимо блокове овог графа. Наравно, можемо да бирамо разапињуће стабло у сваком блоку независно. Приметимо да постоји начин да изаберемо две гране у истом блоку и једну повећамо за један а другу смањимо за 1. Пошто у једном блоку за сваке две гране e_1 и e_2 постоји циклус који их садржи, можемо да нађемо неко стабло T које садржи тај циклус без e_2 и на њега применимо операцију једном, а на T - e_1 + e_2 K - 1 пута. Ово нам каже да ако нам је фиксирана сума грана у сваком блоку, онда можемо да радимо операције да све сем једне гране можемо произвољно изабрати (а последња грана је тада фиксирана). Приметимо такође да за блок величине A, једна операција мења суму у том блоку за тачно +(A - 1). То значи да ако смо применили укупно t mod K пута операцију, у блоку величину A је сума t \cdot (A-1), што узима укупно K / НЗД(K, \ A - 1) вредности. Али није баш независно, него је избор периодичан са периодом НЗС овог горе по свим блоковима, што је К / НЗД(К, \ величина блока_1 - 1, величина блока_2 - 1, \cdots). Тако да је одговор К ^ {M - број блокова} \cdot К / НЗД(К, \ величина блока_1 \ - \ 1, \ величина блока_2 \ - \ 1, \cdots).

3

Титикака

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

Ради једноставности записа, обрнути пешкири биће болдовани. Такмичари ће бити означени са T_i, лежаљке са L_i.

Решење када је N=1, M=2k+1

Следећа конструкција користи k + 1, тј. (N+M)/2 пешкира, и осваја све поене на оваквим примерима:

  • Поставимо пешкире 1 до k на лежаљке 1 до k.
  • Такмичар, користећи пешкир k + 1, легне на првих k лежаљки (дакле редослед би био T_1-p_{k+1}-p_i-L_i, 1 \leq i \leq k)
  • Такмичар, користећи пешкир k+1, легне на лежаљку k+1.
  • Пешкире 1 до k обрнемо и поставимо на лежаљке k+2 до 2k+1.
  • Такмичар, користећи пешкир k + 1, легне на лежаљке k+2 до 2k+1 (дакле редослед би био T_1-p_{k+1}-\mathbf{p_i}-L_i k+2 \leq i \leq 2k+1).

Овде смо користили пешкир p_{k + 1} како бисмо спречили директан пренос прљавштине између осталих пешкира и такмичара. Тако ће се и у наредним решењима појављивати тзв. џокер пешкир J, који ће првенствено бити постављан између два пешкира како би се спречио пренос прљавштине између њих.

Решење када је N=3, M=2

Ово решење спомињемо јер се на њему заправо заснива главно решење. Користићемо 4 пешкира, означимо их са t_1, t_2, l_1, J. Операције изгледају овако:

  • T_1-t_1-l_1-L_1
  • T_2-t_2-l_1-L_1
  • T_3-\mathbf{t_2}-J-l_1-L_1
  • T_1-t_1-\mathbf{J}-\mathbf{l_1}-L_1
  • T_3-\mathbf{t_2}-\mathbf{l_1}-L_1
  • T_2-\mathbf{t_1}-\mathbf{l_1}-L_2

Решење које користи 1+\lceil 2/3N+M/2 \rceil пешкира

Урадимо прво за N=3a, M=2b. Тада можемо да такмичаре поделимо у a група од 3, а лежаљке у b група од 2. Сад за сваки пар групе такмичара и групе лежаљки можемо да применимо горенаведено решење за N=3, M=2, само треба пазити редослед којим радимо ове операције.

Свакој групи такмичара доделићемо по два пешкира, које ћемо означавати са t_1 и t_2. Исто тако, свакој групи лежаљки доделићемо по један пешкир l_1. Користићемо и један џокер пешкир J, који ћемо постављати тако да што касније могуће испрљамо обичне пешкире.

Може се показати да следећи редослед ваља:

Прво, прођемо кроз све парове и вршимо следеће операције:

  • T_1-t_1-l_1-L_1
  • T_2-t_2-l_1-L_1

Онда, прођемо кроз све парове и вршимо следеће операције:

  • T_3-\mathbf{t_2}-J-l_1-L_1

Затим, прођемо кроз све парове и вршимо следеће операције:

  • T_1-t_1-\mathbf{J}-\mathbf{l_1}-L_1
  • T_3-\mathbf{t_2}-\mathbf{l_1}-L_1

На крају, прођемо кроз све парове и вршимо следеће операције:

  • T_2-\mathbf{t_1}-\mathbf{l_1}-L_2

Када је N=3a, M=2b, ово очигледно користи 1+2/3N+M/2 пешкира. Случајеви кад N није дељиво са 3 или M није дељиво са 2 могу се урадити на исти начин, сем што ћемо имати још једну непуну групу на крају. Са њом се могу радити исте ове операције, само избацимо оне које користе непостојеће такмичаре/лежаљке. Тада решење користи 1+\lceil 2/3N+M/2 \rceil пешкира.

Комбиновано са решењем за случај N=1, M=2k+1, ово решење осваја 80 поена.

Решење које користи \lceil 2/3N+M/2 \rceil пешкира

Идеја је у суштини иста - врши се подела у групе од по 3 такмичара и 2 пешкира, само што овај пут морамо некако да искористимо пешкир мање. Најбољи кандидат за избацивање јесте џокер пешкир, који ћемо заправо добити из неког другог пешкира.

Конкретно, претпоставимо да важи N, M \geq 6 и N = 3a+6, M= 2b+2. Издвојићемо једну специјалну групу од 6 такмичара и једну од 2 пешкира, а остатак делимо као раније. Отприлике желимо да одрадимо операције између те две групе, и одатле узети један пешкир који ћемо користити као џокер.

Означимо 6 специјалних такмичара са T'_i, 1 \leq i \leq 6, лежаљка са L'_i, 1 \leq i \leq 2. Они ће користити 5 пешкира p'_i, 1 \leq i \leq 5.
Остале пешкире које користе такмичари означавамо са pt_i, 1 \leq i \leq 2a, а оне које користе лежаљке са pl_i, 1 \leq i \leq b.

Можете се (пожељно папиром и оловком) уверити да је следећи редослед операција валидан:

  1. Све комбинације T'_1-p'_2, T'_3-p'_3, T'_4-p'_4, T'_5-p'_5, T_{3i-1}-pt_{2i}, T_{3i-2}-pt_{2i-1} са p'_1-L'_2, pl_{j}-L_{2j-1}.
  2. Даље ћемо p'_4 користити као џокер, означавамо га са J.
  3. Обрћемо p'_5, као и све pt_{2i}.
  4. Све комбинације T'_6-\mathbf{p'_5}-J, T_{3i}-\mathbf{pt_{2i}}-J са p'_1-L'_2, pl_j-L_{2j-1}.
  5. Све комбинације T'_2 - p'_1 са L'_2, pl_{j} - L_{2j-1}.
  6. Обрћемо све pl_{j}.
  7. Све комбинације T'_1-p'_2 са L'_1, \mathbf{J}-\mathbf{pl_{j}}-L_{2j}
  8. Све комбинације T'_2-p'_1, T'_6-\mathbf{p'_5}, T_{3i}-\mathbf{pt_{2i}} са p'_2-L'_1, \mathbf{pl_{j}}-L_{2j}
  9. Све комбинације T'_3-p'_3, T_{3i-2}-pt_{2i-1} са \mathbf{J}-p'_2-L'_1, \mathbf{J}-\mathbf{pl_j}-L_{2j}
  10. Обрћемо пешкир p'_3 и све пешкире pt_{2i-1}.
  11. Све комбинације Т'_4-\mathbf{p'_3}, T'_5-\mathbf{J}, T_{3i-1}-\mathbf{pt_{2i-1}} са \mathbf{pl_{j}}-L_{2j}, p'_2-L'_1

Укупан број искоришћених пешкира је 5 + 2a + b = 6 + 2(N-6)/3 + (M-2)/2 = 2N/3 + M/2. Случајеви кад N није дељиво са 3 или M није дељиво са 2 могу се урадити на исти начин као раније - треба повећати границу до које итерирамо i, j, али не вршити оне операције над непостојећим такмичарима или пешкирима. Може се видети да се тада користи \lceil 2N/3 + M/2 \rceil пешкира.