Базова идея

Базовата идея, както ни насочва първата подзадача, е да "разделим" на леви и десни обувки. После за всяка дясна ще binary search-ваме нейната лява. Начина да се случи това разделяне е прост: ще държим сет от леви обувки и за всяка следваща ще проверяваме дали има чифт в сета от нея + всички леви. Ако да, значи е дясна, ако не -- я наричаме лява. Т.е. левите са просто първите по ред от всеки чифт.

Подход за анализ

Подхода ни за анализ на нашите заявки и колко са ефикасни е да гледаме колко бита информация ни дават. Ако вероятностите да се падне ДА и да се падне НЕ са равни (т.е. 1/2), това е 1 бит, докато, ако отговорът е сигурен, това е 0 бита. По-общо е -log_2 p бита. В най-добрия случай всяка заявка е 1 бит и тогава заадачата ще бъде решена за средно log_2 БРОЙ_ЧИФТОСВАНИЯ заявки (защото толкова бита детерминират уникално отговорът).

Броя чифтосвания можем да преброим като (2N)! / (N! * 2^N). Т.е. броя битове, които определят едно чифтосване е:

log_2((2N)! / (N! * 2^N))
= (приблизително, до O(log log) грешки)
2N log_2 2N - 2N log_2 e - N log_2 N + N log_2 e - N
=
N log_2 N - N log_2 e + N
= (за N = 5000)
59226

Т.е. виждаме, че търсеният брой заявки от 59650 е много близо до теоретичния минимум.

За първата подзадача, обувките вече са разделени на леви и десни, т.е. броя чифтосвания е просто N! и броя битове е:

log_2(N!)
= (приблизително, до O(log log) грешки)
N log_2 N - N log_2 e
= (за N = 5000)
54225

Тук се търсят 54510 заявки, т.е. отново почти оптималното. Но това е лесно, защото просто ползваме двоично търсене, което е г/д оптимално като брой битове (не са точно по 1 бит на заявка, защото бройките не са винаги степени на 2).

Проблеми

Основните големи проблеми са:

1. В края почти винаги има чифт при тези заявки за всички леви + новата, т.е. те са почти 0 бита, но решението ни не може лесно да ги махне.

2. В началото почти никога няма чифт при тези заявки но отново -- решението ни не може лесно да ги махне.

Наименование на решенията

Основните решения са с име shoes_emil_bs_XY.cpp X е "версията" на решението по проблем 1., а Y тази по проблем 2. Като цяло са независими идеите им.

Подобрение за 2.

Можем, вместо да добавяме 1 по 1 всяка нова обувка, да добавим CHUNK наведнъж и да видим има ли чифт в сета от всички леви + тях. Ще избираме CHUNK, така че вероятността да има чифт да е около 1/2. Ако няма чифт, всичките са леви. Ако има чифт, правим двоично търсене, за да открием първата дясна и продължаваме от след нея.

Тази оптимизация само по себе си не помага чак толкова, но става много по ценна, когато минем на стъпка 1+ по 1. проблем (ще бъде обяснено по долу).

Също така, авторовото решение, прави една екстра стъпка, като "застраховка", но тя се оказва ненужна тук. Тъй като описаното е само евристика, за да се застраховаме можем да сметнем очаквания брой заявки до откриване и обработка на първия чифт в досегашните леви + следващите CHUNK обувки (или до откриване, че няма такъв) в следните 2 подхода:

1. Итериране през тях 1 по 1 (т.е. както без това подобрение).
2. Описаната тук стратегия.

И ако се окаже, че 1 е по добро от 2, можем да изберем да не използваме подобрението. На практика обаче, дори с наивната евристика за размера на CHUNK, тази "застраховка" се оказва почти изцяло ненужна.

Подобрения по 1.

Стъпка 1.

Първо, преди да адресираме основния проблем, можем да направим оптимизация и да опростим леко решението си, за да го подготвим за останалите оптимизации.

Вместо първо да разделяме на леви и десни, винаги когато намерим дясна, ще откриваме съвпадащата ѝ лява веднага (с двоично търсене). По този начин плащаме log_2 БРОЙ ЛЕВИ В МОМЕНТА, което често е доста по-малко число. Така ще следим само позиция и текущите леви (или просто немачнати). Анализирано по друг начин, без тази оптимизация "забравяме" кои са възможните леви за дадена дясна и после започваме двоичното търсене от нулата, т.е. изхвърляме част от информацията, която имаме.

Забележете, че тъй като тук търсим чифтовете докато разделяме на леви и десни, ако текущата кандидат-дясна обувка е дошла от CHUNK стратегията по проблем 2., ние вече знаем, че участва в чифт, т.е. не е нужна допълнителна проверка за "има ли чифт", а можем да правим директно двоичното търсене. Т.е. това се случва с CHUNK >= 2. При CHUNK = 1, няма смисъл да активираме CHUNK стратегията, защото тя (в момента) е еквивалентна на нормалната, но със следващите стъпки става и по-лоша (тъй като имаме по-умни оптимизации при несигурност дали има чифт).

Стъпка 2.

Ще разгледаме 2 подхода за обработка на нова единична обувка (т.е. не от CHUNK стратегията):

1. Проверяваме дали всички немачнати + тя съдържат чифт. Ако да, двоично търсене, а ако не, тя става немачната.
2. Директно правим байнъри сърч, който има още една опция в рейнджа L до R, която съответства на липса на чифт (т.е. ако търсим първата позиция с чифт, но "стигнем" до края).

Очаквания брой куерита за 1. е 1 + P(чифт) * log2(брой немачнати), за 2. е log2(брой немачнати + 1). Идеята е да сметнем цените на тези два варианта и да правим по евтиния. Така, докато още са несигурни чифтовете, ще избираме вариант 1., но към края, когато са доста вероятни, ще избираме вариант 2.

Стъпка 3/4.

Вместо просто да преценим дали да проверим дали има чифт в началото или просто да правим двоично търсене, можем да правим някакво модифицирано двоично, което, ако още не е открило, че има чифт, в някакъв момент "решава" да провери дали има (т.е. да пита кури с всички кандидат мачове). Когато открием, че има чифт, било то от това "решение" или от нормално куери, става оптимално да правим просто балансирано двоично, а ако открием, че няма (заради това "решение"), просто спираме.

При стъпка 3., която просто е по хаки идея, но почти толкова добра колкото стъпка 4., това става чрез нормално двоично и предварително избиране на фиксирано дълбочина на двоичното, когато вече шансът за чифт е твърде малък и е по-добре да питаме дали наистина има чифт. Тази дълбочина е избрана като разгледаме всяка възможна и за всяка сметнем очаквания брой заявки за откриване на отговора.

При стъпка 4. правим теоретично по-простото и по-чистото: просто смятаме вероятността за липса на мач и я "добавяме" като алтернатива в единия край на на байнъри сърча, после просто правим небалансиран байнъри сърч, т.е. такъв който избира MID не в средата между LEFT и RIGHT, а такъв, че сумарните вероятности отляво и отдясно да са приблизително равни. Авторовото решение прави малко повече неща -- смята очаквания брой заявки в този процес и т.н., но това всъщност не е нужно за самото решение. Нужно е за "застраховката" в оптимизацията по проблем 2., но вече казахме, че тя всъщност почти не е полезна.

Финално подобрение по 2.

Завръщаме се към 2. с опит за финално подобрение. Вместо да избираме с евристика някакъв CHUNK и да правим нормално двоично търсене в него, ще сметнем вероятността за всяка позиция да е първата с чифт и ще правим небалансирано двоично (т.е. ще е балансирано по вероятностите). И тъй като то вече е небалансирано можем да го правим до максимално голямата дясна точка (т.е. тази където ще има гарантиран чифт).

Отново, авторовото решение влага доста усилия да смята доста неща около очаквани цени (като брой заявки) на различните случаи, но това почти няма значение и всяка простичка евристика за дали да ползваме решението с CHUNK (например шанса за чифт със следващата една обувка да е под 1/2) се представя почти толкова добре.

Оказва се обаче, че подобрението от това е почти изцяло пренебрежимо в общия случай. Единственото измеримо предимство на тази оптимизация (във финалното решение) е, че "натурално" се справя и с първата подзадача за пълен брой точки.

Точки по решения

Забележете, че тези решения се оценяват без частния случай за подзадача 1. Т.е. на практика биха имали малко по-добри резултати, особено защото някои от тях правят повече заявки на нея от на втората подзадача.

emil_bs_00 -- 30 точки / 64512 заявки
emil_bs_01 -- 35 точки / 63207 заявки
emil_bs_10 -- 45 точки / 62295 заявки
emil_bs_11 -- 67 точки / 60948 заявки
emil_bs_20 -- 54 точки / 61734 заявки
emil_bs_21 -- 80 точки / 60389 заявки
emil_bs_30 -- 65 точки / 61112 заявки
emil_bs_31 -- 93 точки / 59766 заявки
emil_bs_40 -- 67 точки / 60993 заявки
emil_bs_41 -- 95 точки / 59647 заявки
emil_bs_42 -- 100 точки / 59642 заявки