Анализ на задача Eagers

Подзадача 1:
Тъй като всеки елемент участва в един от к-те подмасива, то първия подмасив започва в елемент 1, а всеки следващ започва в елемента, който е веднага след края на предишния. От това се вижда, че може да обозначим всяко разпределение, като масив от н елемента с 0 или 1ци, в който 1ци означават, че елемента е последния във подмасива си. За да е валидно обозначение, трябва да има точно к 1ци и последната да е на позиция н. Можем да обходим всяко разпределение и да проверим дали е валидно и какъв резултат получава, след което да се вземе максимума.
Сложността на решението е O(2^n*n)

Подзадача 2:
В подзадачата всяка стойност е или 0 или 1. Това значи, че отговора също е или 0 или 1. Затова ще проверим дали отговора може да е 1. За да бъде отговора 1, искаме ORа във всеки подмасив да е 1, т.е. да има поне 1 1ца във всеки подмасив. Лесно се вижда, че ако има поне K елемента, които са 1ци, това е възможно. Това е така, защото могат да се изберат К 1ци, които да бъдат край на подмасивите си и елементите след последната 1ца да се сложат при нея. Това разпределение ще даде резултат 1 със сигурност.

Подзадача 3:
Тук всяка стойност е 0, 1 или 2. Това значи, че отговорът е 0, 1, 2 или 3. Можем да проверим дали всяка стойност е възможна. 1 и 2 имат същата идея като миналата подзадача: просто броим дали има поне К от тях.
За да проверим дали стойността 3 е възможна, трябва да започнем да мислим гриди идеята. 
Може да забележим, че ако е възможно разпределение с X подмасива, то е възможно такова с X-1, като два подмасива просто се обединят. Затова ще се опитаме да намерим най-голямата бройка от подмасиви, която дава резултат. Нека започнем да строим от началото, т.е. елемент 1. Тъй като се опитваме да направим максимален брой подмасиви, трябва да направим подмасивите възможно най-малки. Веднага щом увеличим първоначалния подмасив да дава стойност 3, може да приключим с него. Това ще се случи на позицията, на която е първата 1ца или първата 2ка (което е по-голямо). Може да продължим алгоритъма си по този начин, всеки път създавайки подмасив до най-близката 1ца или 2ка (което е по-голямо) и така, докато не изчерпаме числата в масива. Така ще получим максималния брой подмасиви, които дават отговор 3. Ако това число е поне К, то отговорът 3 е възможен.
За да се напише по-бързо от O(n^2), трябва да преизчислим най-близките 1ци и 2ки от всяка позиция, след което решението става O(n)

Подзадача 4:
В тази подзадача малко ще се разсеяме от наблюдения и ще приложим най-базовото дп възможно. Нека dp[x][y][z] e 0 или 1, спрямо възможно ли е стойност z да се получи от първите х числа чрез точно у подмасива. Базовите стойности за у=1 са ясни: просто префиксните орове. Нека сме изчислили вече всички стойностти за определено х. Може от тези които са 1ци да циклим напред от х+1 до н и да попълваме новите стойности, които вече са възможни (може да видите по-подробно следващата подзадача какво представлява цикъла). Щом може dp[x][y][z], то за дадено i от х+1 до н, ще може dp[i][y+1][z AND (ора от х+1 до i)].
След всичко това просто виждаме най-голямата стойност за която dp[n][k][] е 1.
Сложността на решението става O(n^3*A)
Трябва да се има предвид че с числа до 2000, може да се получи отговор до 2^11, т.е. 2048, а не само 2000. Т.е. А=2048

Подзадача 5:
Вижда се, че дп идеи като dp[x][y] определящо максималната стойност, която може да се получи от у подмасива и първите х елемента, са грешни защото функцията AND не гарантира, че макса за к подмасива ще се получи чрез макса за к-1 подмасива. Но всъщност има друга дп идея, която е легитимна. Ще използваме наблюдението от подзадача 3, че ако една стойност y може да се получи чрез к подмасива, тя може и чрез к-1, като се съединят два от подмасивите. Ще изведем дп-то dp[x][y] - колко е максималния брой подмасиви с които може да се получи стойност у от първите х елемента. Отговорът ни ще е най-голямата стойност за у, за която dp[n][y]>=k . Нека стойност -1 означава, че стойноста не може да се получи.
нека cost(i,j)=aiORai+1OR...ORaj
да започнем с базови стойности: dp[x][cost(1,x)] може да се получи и е поне 1. Ще изчисляваме стойности отляво надясно за х. Щом изчислим всички стойности за dp[x][..] ще ъпдейтнем стойностите на по-големите х.
Взимаме dp[x][y] и започваме да обхождаме от х+1 до н. Нека броячът се казва i.
Знаем че стойност y AND cost(x+1,i) може да се получи от първите i елемента с dp[x][y]+1 подмасива. Затова може да проверим дали dp[x][y]+1 e повече от засега записана стойност в dp[i][y AND cost(x+1,i)] (и дали стойноста не е била -1) и ако е да я ъпдейтнем. Вижда се, че докато стигнем до стойността за х да е i , ще сме минали през всички възможности и ще сме получили максимума.
Сложността на решението става O(n^2*A)
Както в миналата подзадача А трябва да се увеличи до степента на двойката, т.е. 2048
Тук е важно и да се спомене една "грешка" в обяснението. Обединяване на 2 подмасива от едно разпределение всъщност не винаги дава същия отговор. Обаче отговора, който може да се получи винаги е по-голям и има всички битове 1ца на оригиналния. Заради това дп-то ни ще полчи някой фалшиви бройки (пр. мислейки си че 3ка може с 4 подм, а всъщност може 7ца). Но тези фалшиви бройки винаги ще бъдат дублирани от по-големи стойности и затова отговорът няма да се повлияе.

Подзадача 6:
Пак ще опитаме да изчислим за всяка стойност, максималния брой подмасиви, от които може да се получи. Но вместо с дп, ще го правим с грийди. В подзадача 3 говорихме, че за да получим стойност 3 в подмасив, ни трябва стойност 0 или 1. По същата логика, за да получим число х, трябва в подмасива да се среща число, което има бит 1ца, за всеки бит, който е 1 в х. Така можем да преизчислим log масива от най-близкото число с бит 1ца за всеки бит. С този масив лесно можем да намерим с колко подмасива се получава някоя стойност, като приложим грийдито от подзадача 3, всеки път проверявайки максималната стойност от битовете 1ца.
След всичко това, отговорът пак е максималното число, което може да се получи от поне К подмасива.
Сложността на решението е O(n*A*log)
Както в миналата подзадача А трябва да се увеличи до степента на двойката, т.е. 2048

Подзадача 7:
Подзадачата е предвидена за по-бавни решения на главната идея. Примерно такива с сложност O(n*log^2)

Подзадача 8:
В подзадача 5 обсъдихме как за дадена стойност , може да се провери от колко подмасива се получава с около n oперации. Обаче всъщност не е нужно да се проверява всяка стойност. Може да направим двоично търсене по битовете.
В подзадача 4 обсъдихме защо ако число х може да се получи с у подмасива, то няма как число с всички битове 1ца на х (т.е. и по-голямо) да се получава с повече от у подмасива, заради фалшивите стойности.
Следователно може да проверим дали числото 2^29 (първата стойност по-малка от 10^9) се получава с поне к подмасива. Ако се, то всички стойности по-големи (т.е. имащи този 29 бит 1ца), е възможно да се получат. Вече няма да има смисъл да проверяваме стойности по-малки от 2^29, защото търсим максимум.
След това ще проверим за 2^28 ако 2^29 не е можело или 2^28+2^29 , ако е. Аналогично продължаваме и добавяме всеки бит, ако се получава възможна комбинация с него.
След проверката за 1, ще сме останали с най-голямата стойност, която е възможна.
Решението може да бъде написано или за O(n*log^2) или O(n*log) и ще вземе съответно 6та или 7ма подзадача