Васа, скупљач ауре
Аутор: Алекса Данић
Текст и тест примери: Алекса Милисављевић
Анализа решења: Алекса Данић
Тестирање: Марко Трајковић
Решење када је 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::multiset.
Рецимо да смо нашли збир x-1 максимума на интервалу [l,r]. Назовимо тај збир S. Нека је large multiset чији су елементи x-1 максимума међу свим suff_i за i \in [l,r] (уколико су x-ти и x-1-ви максимум једнаки, узимамо број елемената те вредности такав да је |large|=x-1). Нека је small multiset чији су елементи сви suff_i за i \in [l,r] који не припадају large.
Да бисмо прешли на интервал [l+1,r+1], потребно је додати елемент suff_{r+1} и избацити елемент suff_l из наших структура, и адекватно ажурирати S, large и small.
Хајде најпре да видимо како правилно додати елемент suff_{r+1}.
За почетак додајемо suff_{r+1} у multiset large и повећавамо S за suff_{r+1}, а потом пребацујемо најмањи елемент multiset-а large у multiset small и смањујемо S за вредност тог елемента.
Након ових операција large чува x-1 максимума интервала [l,r+1], small чува све остале елементе тог интервала, а S суму x-1 максимума.
Потребно је још обрисати елемент suff_l.
Разликујемо два случаја: када се suff_{l} налази у large и када се налази у small (уколико се та вредност налази у оба multiset-а, определимо се за произвољан случај). Ако се налази у small, једноставно га обришемо из тог multiset-а. У супротном га обришемо из large, смањимо S за suff_l, пребацимо највећи елемент multiset-а small у multiset large и повећамо S за његову вредност.
Након свих операција смо успешно прешли са интервала [l,r] на интервал [l+1,r+1].
Као у претходном подзадатку, крећемо од [1,k] и понављањем наведеног поступка тражимо решење за све интервале дужине k.
Временска сложеност: O(n \log n)