Фејк реклама
Аутор: Александар Вишњић
Текст и тест примери: Алекса Милисављевић
Анализа решења: Александар Вишњић
Тестирање: Димитрије Ердељан и Александар Вишњић
Решење за N\leq 20
Код сваке препреке имамо 2 избора, те рекурзивно решење даје сложеност 2^N,
Решење када m_i=1 за свако 1\leq i\leq N и N \leq 30
Користимо meet in the middle технику. За првих \lfloor \frac{N}{2} \rfloor препрека израчунамо све могуће величине војске (рекурзивно као у претходном подзадатку). Затим, за наредних \lceil \frac{N}{2} \rceil почнемо од неке неодређене величине војске x и симулирамо препреке за њу. Податке чувамо у следећем формату:
- Ако је почетно x у интервалу [y,z], онда је x+s могућа тренутна величина војске.
Наравно, ових ставки може имати произвољно много, те их чувамо у некој колекцији. Та колекција може бити празна. На почетку та колекција садржи само једну ставку - ону за почетно x и ограничење [-10^9,10^9]
Када пролазимо кроз препреке, због услова m_i=1, имамо два избора:
- Не радимо ништа, и додајемо ново ограничење за интервал за почетно x на сваку ставку;
- За сваку почетну ставку, направимо копију и симулирамо додавање a_i на x. Памтимо инкремент, а потом додајемо ново ограничење за почетно x у облику интервала.
При сваком кораку величина колекције не порасте за више од дупло. Крајња величина није већа од 2^N.
Када након извшавања прве половине сазнамо свако могуће x, а након извршавања друге половине добијемо све могуће ставке, можемо их спојити и израчунати највећу могућу величину војске након свих прођених препрека.
Меморијска сложеност је O(2^{N/2}), док је временска O(2^{N/2} \cdot N) због сортирања и бинарне претраге.
Решење када N \leq 30
Слично као у претходном подзадатку, користимо технику meet in the middle. Проблем настаје при ажурирању “*m_i”. У првом делу можемо рекурзивно пронаћи свако могуће x. Али, у другом делу више немамо једноставне ставке. Оне сада постају компликованије функције од x. Ипак, испоставља се да су те функције линеарне. На почетку имамо функцију f(x)=x. Она је очито линеарна. Претпоставимо да пре неке препреке имамо колекцију линеарних функција. Посматрајмо једну од њих, нека је то f(x)=p x + q. За модификовање ње имамо две опције:
- f(x)=p m_i x + q m_i
- f(x) = px + q + a_i
Примећујемо да при оба избора, наша функција заиста остаје линеарна. Међутим, додавање нових ограничења за сегмент на оригинално x је нешто компликованије, али изводиво. Можемо целу ставку замислити као функцију са ограниченим доменом (који ће бити неки сегмент).
На крају, из прве половине имамо свако могуће x, а из друге половине имамо сваку могућу линеарну функцију са одговарајућим доменом. Спајање можемо извршити тако што фиксирамо функцију са њеним доменом [l,r]. Приметимо да линеарна функција достиже максимум у крајевима, тј. да тражимо x да буде што ближе “већем крају”. Овим скраћујемо могућност на највише једно могуће x. Сада једноставно прођемо по свакој функцији и евалуирамо је у њеном оптималном x.
Битно је напоменути да се може десити да коефицијенти неке функције изађу из опсега типа long long. Таква је, на пример, функција f(x)=10^{100}x -10^{100}. Она стаје у ограничење [-10^9,10^9] за тачку x=1. Међутим, приметимо да такве функције чији су коефицијенти већи од 10^{18} (по апсолутној вредности) стају у ограничење [l_i,r_i] само у једној тачки. Пошто је домен те функције у ствари једна тачка, довољно је “компресовати” је. Нека је (x_e,y_e=f(x_e)) та тачка (у општем случају “превелике” функције). Њу можемо описати и на следећи начин: f(x) = 0x + y_e. Она очито има коефицијенте у опсегу [-10^9,10^9], те стаје у long long.
Меморијска сложеност је O(2^{N/2}), док је временска O(2^{N/2} \cdot N) због сортирања и бинарне претраге.
Решење када N \leq 40
Користимо идеје из претходног подзадатка. Потребно је смањити временску сложеност на O(2^{N/2}). Приметимо две чињенице:
- Алгоритам бинарне претраге може се заменити са техником два показивача
- Сортирање параметара је могуће вршити у O(2^{N/2}) временској сложености.
Јасно је да ако докажемо и изведемо другу чињеницу, укупна сложеност биће O(2^{N/2}).
Замислимо да имамо тренутни низ x_1,x_2,\ldots ,x_k (у првом делу meet in the middle алгоритма ) и да њега ажурирамо новим операцијама “*m” и “+a”. Познато је да ако је почетни низ сортиран, тада су и низови m\cdot x_1,m\cdot x_2, \ldots, m\cdot x_k; a+x_1, a+x_2, \ldots ,a+x_k. (потенцијално у обрнутом редоследу). Сада можемо применити алгоритам налик merge sort . Временска сложеност овог алгоритма сортирања заиста јесте O(2^{N/2}).
Функције слично сортирамо када их припремамо за технику два показивача. Међутим, потребно их је филтрирати у две групе. Једну групу сортирамо по левом крају домена (оне функције са негативним коефицијентом уз x), а другу групу по десном крају домена (оне функције са ненегативним коефицијентом уз x).