Извлачење сламки
Аутор: Младен Пузић
Текст и тест примери: Младен Пузић
Анализа решења: Младен Пузић
Тестирање: Павле Мартиновић
Подзадатак 1
За овај подзадатак, потребно је наћи позицију са које се највише пута извлачи сламка, а да је могуће ставити најкраћу сламку на ту позицију. Потребно је, дакле, само наћи интервал на којем може завршити најкраћа сламка. На почетку је тај интервал једнак само њеној почетној позицији, док сваким новим мешањем тај интервал се може проширити, уколико се макар и мало преклапа са интервалом мешања. Временска и меморијска сложеност: O(N+M).
Подзадатак 2
За свако мешање, можемо фиксирати да ли се мења место двема сламкама на интервалу мешања. Сваку комбинацију симулирамо и узмемо најбоље решење. Меморијска сложеност: O(N+M), временска сложеност: O(2^M\cdot M + N).
Подзадатак 3
Овај подзадатак има решење веома слично подзадатку 4, али га је лакше замислити, па је служио као помоћ такмичарима да дођу до бољег решења. Погледати решење четвртог подзадатка.
Подзадатак 4
Означимо са dp_{i, j} максимално решење ако се после j догађаја најкраћа сламка налази на позицији i. На почетку важи dp_{i, 0} = -\infty (довољно мали негативан број), за свако i на којем се не налази најкраћа сламка, док важи dp_{i, 0} = 0, за i које је почетна позиција најкраће сламке. Сада је потребно да нађемо рекурзивну везу. Постојаће два случаја, за два различита типа догађаја:
1 l r: dp_{i, j} = max\{dp_{l, j-1}, dp_{l+1, j-1}, \ldots, dp_{r, j-1}\}, уколико i \in [l, r]. У супротном dp_{i, j} = dp_{i, j-1}. Дакле, било која позиција на интервалу може доћи са било које друге позиције на интервалу, а оптимално је да узмемо са максималне.
2 x: dp_{x, j} = dp_{x, j-1} + 1, а dp_{i, j} = dp_{i, j-1} уколико i \neq x. Једино се повећава случај кад се баш ту налази најкраћа сламка, остале се не мењају.
Меморијска сложеност: O(NM) (може и O(N)), временска сложеност: O(NM).
Подзадатак 5
Чувајмо dp_i за сваки догађај i који је другог типа. Ту чувамо најбоље решење ако је Павле у том тренутку извукао најкраћу сламку. Како бисмо израчунали ову вредност потребно је да видимо одакле смо све могли да дођемо. Крећемо се уназад кроз догађаје и одржавамо интервал одакле смо могли да дођемо на позицију сламке коју је Павле извукао у догађају i, слично решењу првог подзадатка. Сваки пут када наиђемо на догађај j облика 2, ако је у интервалу од којег смо могли да дођемо, урадимо операцију dp_i = max(dp_i, dp_j+1). Крајње решење нам је максимум целог низа dp. Меморијска сложеност: O(M), временска сложеност: O(M^2+N).
Главно решење
Веома слично решењу подзадатка 4, идемо кроз дешавања једно по једно и одржавамо низ dp_i, за до сада пређене догађаје, које је најбоље решење, ако се тренутно најкраћа сламка налази на позицији i. Овај низ можемо одржавати по рекурентним везама из 4 подзадатка, користећи сегментно стабло са лењом пропагацијом, које има операције: нађи максимум на интервалу и постави цео интервал на неку вредност. Догађај један се покрива операцијом постави интервал на максимум на интервалу, док се догађај два покрива операцијом постави интервал [x, x] на вредност од dp_x+1. Меморијска сложеност: O(N), временска сложеност: O(MlogN+N).