Далтонизација
Аутор: Марко Миленковић
Текст и тест примери: Алекса Милисављевић
Анализа решења: Алекса Милисављевић
Тестирање: Милош Милутиновић
Решење када је a_i = 1 за свако 1 \leq i \leq N и N \leq 300
У овом подзадатку важи да сви нфт-ови имају исту вредност, те је сваком брату потпуно свеједно да ли узима нфт са почетка или нфт са краја. i-ти брат ће укупно имати онолико нфт-а у вредности колико пута ће бити на потезу.
Решење када је N \leq 20
У овом подзадатку за сваког брата можемо да рекурзивно симулирамо све могуће његове одлуке и одлуке осталих. Ово решење ради у временској сложености O(N \cdot 2^N).
Решење када је M = 2 и N \leq 300
У овом подзадатку постоје само два брата, те важи да је обојици циљ да прикупе што више (тј. не морамо да анализирамо њихове профите независно). За овај и наредне подзадатке решење проналазимо коришћењем техника динамичког програмирања. Означимо са s(l,r) суму a_l + a_{l+1} + ... + a_{r-1} + a_r. Нека је dp[i][l][r] зарада i-тог брата ако су остали нфт-ови на позицијама између l и r и брат i је на потезу. Приметимо да у том случају је зарада брата који није i-ти управо s(l,r)-dp[i][l][r], тј. узеће све оно што није узео i-ти брат. Тада је dp[1][l][r] = \max(a_l + (sum(l+1,r) - dp[2][l+1][r]),a_r + (sum(l,r-1) - dp[2][l][r-1])) и слично томе dp[2][l][r] = \max(a_l + (sum(l+1,r) - dp[1][l+1][r]),a_r + (sum(l,r-1) - dp[1][l][r-1])). Приметимо да је динамичко програмирање неопходно конструисати растуће у односу на дужину интервала [l,r].
Коначно први брат ће имати укупно dp[1][1][N], док ће други имати sum(1,N) - dp[1][1][N]. Ово решење ради у временској сложености O(N^2) и меморијској сложености O(N^2).
Решење када је N \leq 300
У овом подзадатку морамо да генерализујемо решење из претходног подзадатка. Приметимо прво да број нфт-ова који су преостали у низу једнозначно одређује брата који је на потезу. Нека је b(l,r) брат који је на потезу ако су остали само нфт-ови између позиција l и r. Овим елиминишемо једну димензију динамичког програмирања из претходног подзадатка. Дакле, dp[l][r] представља профит брата b(l,r) уколико се преостала браћа уроте против њега. Нека је b(l,r)=i. Он ће у том потезу изабрати или a_l или a_r. Претпоставимо да је изабрао a_l. Приметимо да се након потеза преостале браће број нфт-ова у низу смањио за тачно M-1. Према томе, наредни пут када брат i буде на потезу, преостаће му да бира са почетка или са краја једног од интервала [l+1,r-M+1], [l+2,r-M+2], …, [l+M-1,r-1], [l+M,r]. Како су се преосталих M-1 браће уротили против њега, знамо да су они одлуке доносили тако да његова укупна зарада буде што мања могућа. Дакле, брату i ће преостати интервал са најмањом зарадом, тј. зарадиће \min(dp[l+1][r-M+1],...,dp[l+M][r]). Слична анализа ради и у случају да он одабере нфт a_r. Коначно, ово динамичко програмирање можемо да рачунамо формулом: dp[l][r] = \max(a_l + \min(dp[l+1][r-M+1],...,dp[l+M][r]), a_r + \min(dp[l][r-M],...,dp[l+M-1][r-1])).
Да би добили решење за i-тог брата, морамо да анализирамо интервале када ће он бити први пут на потезу и да одаберемо онај који има најмању вредност, тј. \min(dp[1][N-i+1],dp[2][N-i+2],...,dp[i][N]). Ово решење ради у временској сложености O(N^3) и меморијској сложености O(N^2).
Решење када је N \leq 4.000
У овом подзадатку можемо да приметимо да је могуће искористити структуру података на решењу из претходног подзадатка. Приметимо да интервали од којих тражимо онај са минималном вредношћу у формули за рачунање динамичког програмирања сви имају исту дужину и да су ти интервали узастопни са том дужином (тј. почеци свака два суседна се разликују за тачно 1). Према томе, можемо да конструишемо сегментно стабло за сваку дужину. У сваком чвору сегментног стабла чувамо минимум за неки узастопни скуп интервала.
Ово решење ради у временској сложености O(N^2 \log N) и меморијској сложености O(N^2).
Главно решење
У овом подзадатку морамо да оптимизујемо временску и меморијску сложеност из претходног подзадатка. Прво, приметимо да је рачунање решења за сваког брата потпуно независно и да се не ослања на вредности динамичког програмирања за осталу браћу. Приметимо и да решење за i-тог брата искључиво зависи од његовог првог следећег потеза. Према томе, можемо сваког брата да процесирамо независно и растуће по дужини интервала који разматрамо. Претпоставимо да смо израчунали решење за све интервале дужине d. У наредном кораку рачунамо решење за све интервале дужине d+M. Чим то решење израчунамо, подаци о дужини d нам више не требају. Један начин да израчунамо решење за интервале дужине d+M је да применимо структуру из претходног подзадатка. Овим добијамо решење временске сложености O(N^2 \log N) и меморијске сложености O(N).
Да би оптимизовали и временску сложеност, морамо да приметимо и да је број интервала у сваком од минимума динамичког програмирања тачно M. Према томе можемо да применимо sliding window технику. Процесирамо групу од првих M узастопних интервала дужине d. Потом се померимо на десно за једну позицију (тј. избацимо први интервал из групе и убацимо први наредни). Процесираћемо на овај начин једну по једну групу од M интервала дужине d и сваки пут проналазити минимум.
Одржаваћемо deque (тј. ред са два краја). Када се померимо на десно за један, прво проверимо да ли је интервал на почетку реда још увек део групе. Уколико није, избацимо га. Потом посматрамо елемент са краја реда. Све док елемент са краја реда има већу или једнаку вредност од новог интервала у групи, можемо да га обришемо са краја. Ово је тачно, јер нас интересује само минимум, а како се померамо на десно, тај интервал са већом вредношћу ће бити избачен пре интервала који је управо додат у групу коју разматрамо, те, према томе, он никада неће бити бољи избор. Када избришемо све интервале са краја који су имали већу или једнаку вредност, додамо нови интервал на крај. Приметимо да ова конструкција гарантује да елемент који је испред новододатог има строго мању вредност од њега. Према томе, најмања вредност у целом реду је заправо елемент на почетку реда.
Ово решење ради у временској сложености O(N^2) и меморијској сложености O(N).