Васа, скупљач ауре
Аутор: Алекса Данић
Текст и тест примери: Алекса Милисављевић
Анализа решења: Алекса Данић
Тестирање: Марко Трајковић
Решење када је N \leq 20
У овом подзадатку имамо времена да за сваки подниз фиксирамо скуп индекса на којима се коефицијент повећава, и израчунамо Васину ауру за сваки од тих скупова.
Временска сложеност: O(n^2{k \choose x})
Важна формула за све наредне подзадатке
Посматрајмо конкретан подниз [l,r] дужине k. Нека је ind_c први индекс на ком је Васа узео елемент са коефицијентом c (у случају да је Васа узео елемент p_r са коефицијентом x-1, нека је ind_x=r+1). Нека је sum(a,b)=p_a+p_{a+1}+\dots+p_{b-1}+p_b, (sum(a,b)=0 за a>b). Приметимо да је укупна Васина аура након проласка кроз подниз једнака:
\sum_{i=1}^x sum(ind_i,r)
Ово је збир x суфиксних сума на поднизу [l,r]. Када бисмо за свако p_i израчунали у колико различитих суфиксних сума се тај елемент налази, видели бисмо да је то управо исти број као коефицијент испред тог елемента који је Васа изабрао. Ево примера за лакше разумевање формуле на низу [1,2,3,4,5,6], где су изабрани коефицијенти [1,1,2,2,3,3]:
1 \cdot 1 + 1 \cdot 2 + 2 \cdot 3 + 2 \cdot 4 + 3 \cdot 5 + 3 \cdot 6 = sum(1,6)+sum(3,6)+sum(5,6)
sum(1,6)=1+2+3+4+5+6, sum(3,6)=3+4+5+6, sum(5,6)=5+6
Видимо, на пример, да се број 2 појављује само једном, у суфиксној суми sum(1,6), а да се број 5 појављује у све три суфиксне суме. Такође, коефицијент испред 2 је 1, а коефицијент испред 5 је 3.
Уведимо и ознаку suff_i=sum(i,n). Тада је sum(a,b)=suff_a-suff_{b+1}.
Решење када је p_i \geq 0
Исплати се узети сваки елемент са што већим коефицијентом, па ће Васа повећавати коефицијент сваки пут кад може. Решење за конкретан подниз [l,r], \space r-l+1=k је 1p_l+2p_{l+1}+\dots+xp_{l+x-1}+xp_{l+x}+xp_{l+x+1}+\dots+xp_r=\sum_{i=l}^{l+x-1}sum(i,r)=\sum_{i=l}^{l+x-1}(suff_i-suff_{r+1})=(\sum_{i=l}^{l+x-1}suff_i)-x \cdot suff_{r+1}. Сума коју смо добили у овој формули је сума x узастопних елемената низа suff, коју можемо брзо наћи уколико прекалкулишемо низ префиксних сума над низом suff.
Дакле, нека је P_i=suff_1+suff_2+\dots+suff_{i-1}+suff_i, P_0=0. Решење за интервал [l,r] дужине k је једнако
P_{l+x-1}-P_{l-1}-x \cdot suff_{r+1}
Временска сложеност: O(n)
Решење када је n \leq 300
Спорије имплементације наредног подзадатка дају поене за овај подзадатак.
Решење када је n \leq 3000
Посматрајмо конкретан подниз [l,r] дужине k. Решење за овај подниз је
\sum_{i=1}^x sum(ind_i,r)=\sum_{i=1}^{x}(suff_{ind_i}-suff_{r+1})=(\sum_{i=1}^{x}suff_{ind_i})-x \cdot suff_{r+1}
Потребно је да изаберемо низ ind тако да је вредност наведеног израза што већа. Приметимо да је x \cdot suff_{r+1} константа, па је потребно максимизовати \sum_{i=1}^{x}suff_{ind_i}, или речима, треба нам збир суфиксне суме која почиње на индексу l (јер је ind_1=l), и x-1 највећих суфиксних сума које почињу на индексима између l+1 и r+1. Можемо сортирати све ове суфиксне суме, након чега је лако наћи збир највећих x-1.
Временска сложеност: O(n^2 \log n) - довољно за максималан број поена на овом подзадатку
Уколико бисмо сортирали све суфиксне суме пре фиксирања подниза, и за сваку памтили који индекс јој одговара, након фиксирања подниза бисмо у O(n) могли да издвојимо само суфиксне суме којима одговара индекс из интервала [l+1,r+1], и то у сортираном поретку. Овим приступом избегавамо сортирање за сваки подниз.
Временска сложеност: O(n^2)
Решење када је x = 2
У претходном подзадатку смо видели да је потребно да нађемо збир x-1 највећих suff_i за i \in [l+1,r+1].
Дакле, у овом подзадатку нам треба максимум сваког интервала дужине k низа suff. Користићемо технику sliding window.
Један начин је да користимо структуру података попут std::multiset из стандардне библиотекте програмског језика C++. Ова структура података, између осталог, подржава операције додавања, брисања, и дохватања највећег елемента, све у временској сложености O(\log n), и одржава елементе у уређеном поретку (сортиране по неком критеријуму).
Рецимо да смо нашли максимум на интервалу [l,r], и да су нам у multiset-у сви елементи на том интервалу. Када у multiset додамо suff_{r+1}, а из њега избацимо suff_l, можемо наћи максимум на интервалу [l+1,r+1].
Почињемо од интервала [1,k], и понављајући наведени поступак можемо ефикасно наћи решења за сваки интервал дужине k.
Временска сложеност: O(n \log n)
Постоји и решење у временској сложености O(n) које користи ред са два краја - std::deque, али није неопходно за максималан број поена на овом подзадатку.
Решење за 100 бодова
У решењу за 100 бодова нам треба збир x-1 максимума сваког интервала дужине k низа suff, али у ефикаснијој сложености него у подзадатку n \leq 3000.
Као у подзадатку x \leq 2, користићемо технику sliding window, и структуру података std::set.
Рецимо да смо нашли збир x-1 максимума на интервалу [l,r]. Назовимо тај збир S. Нека је all set чији су елементи сви уређени парови (suff_i, i) за i \in [l,r]. Нека је largest set чији су елементи уређени парови (suff_i, i) за i \in [l,r], али само они за које је suff_i међу x-1 максимума интервала [l,r] (уколико су x-ти и x-1-ви максимум једнаки, међу елементима те вредности узимамо произвољне, тако да је |largest|=x-1).
Да бисмо прешли на интервал [l+1,r+1], потребно је додати елемент suff_{r+1} и избацити елемент suff_l из наших структура, и адекватно ажурирати S, all и largest.
Хајде најпре да видимо како правилно додати елемент suff_{r+1}.
За почетак додајемо уређени пар (suff_{r+1},r+1) у оба set-а и повећавамо S за suff_{r+1}, а потом бришемо најмањи елемент set-а largest и смањујемо S за вредност тог елемента.
Након ових операција all чува све вредности на интервалу [l,r+1], largest чува x-1 максимума тог интервала, а S њихову суму.
Потребно је још обрисати елемент suff_l.
Бришемо уређени пар (suff_{l},l) из all. Такође га бришемо и из largest, али само ако се он налази у том set-у.
Ако се (suff_{l},l) није налазио у largest, завршили смо - all чува све елементе интервала [l+1,r+1], largest чува x-1 максимума међу њима, а S њихову суму.
Други случај је да се (suff_{l},l) налазио у largest. У том случају смо остали без једног од x-1 максимума, па смањујемо S за suff_l и морамо наћи x-1-ви максимум преосталих елемената. Ми знамо x-2-ги максимум, то је најмањи елемент из largest, а x-1-ви максимум се налази непосредно пре њега у all, па се он може наћи помоћу std::set::lower_bound(). Након што нађемо нови x-1-ви максимум, додајемо га у largest и повећавамо S за његову вредност.
Након свих операција смо успешно прешли са интервала [l,r] на интервал [l+1,r+1].
Као у претходном подзадатку, крећемо од [1,k] и понављањем наведеног поступка тражимо решење за све интервале дужине k.
Временска сложеност: O(n \log n)