Налбандиан
Аутор: Павле Мартиновић
Текст и тест примери: Немања Мајски
Анализа решења: Младен Пузић
Тестирање: Павле Мартиновић
Пре свега, потребно је да адекватно замислимо овај турнир. Приметимо да структура турнира представља укорењено бинарно стабло са 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)