6. Oči veľké vzorové riešenie

3
5 7 5
2 8 4
4 5 4

6

Bruteforce

Najjednoduchší bruteforce je jednoducho vyskúšať všetky možné priradenia študovaných predmetov ku dňom a skontrolovať, ktoré predmety by sme urobili. Toto je však samozrejme príliš pomalé. Časová zložitosť je \(O(n D^n)\), kde \(D=\max d_i\).

Ako toto vieme zrýchliť?

Lepší bruteforce

Môžeme si všimnúť, že keď už raz začneme študovať nejaký predmet, oplatí sa nám ho celý doštudovať a až potom začínať s ďalším.

Predstavme si totiž, že by v optimálnom riešení existovala dvojica predmetov \(A\) a \(B\), také, že \(A\) sme dokončili skôr ako \(B\), ale ešte pred jeho dokončením sme začali študovať \(B\). Tu vidíme, že keby sme najprv dokončili \(A\), stále by sme mali platné riešenie - \(A\) by sme doštudovali skôr a koniec \(B\) by sa nezmenil. Tu teda vidíme, že existuje optimálne riešenie, v ktorom každý predmet študujeme v jednom kuse.

Toto znamená, že predmety môžeme vnímať ako súvislé bloky. Zaujíma nás teda len to, ktoré predmety sa rozhodneme študovať a v akom poradí.

Z tohoto sa nám formuje rýchlejšie riešenie. Vygenerujeme si všetky podmnožiny predmetov a pre každú z nich všetky jej permutácie. Pre každú z nich si skontrolujeme, že zo všetkých predmetoch v nej urobíme skúšku. Zo všetkých, pre ktoré je odpoveď áno zoberieme tú s najviac kreditmi a tá je riešením. Podľa toho, ako šikovne toto implementujeme sa bude časová zložitosť pohybovať medzi \(O(n!)\) a \(O(n^2 n!)\), čo stále nepostačuje na získanie bodov.

Ďaľšie pozorovanie

Tu ale prichádza na radu druhé kritické pozorovanie. Dokážme si, že v optimálnom riešení budeme predmety študovať v poradí ich skúšok. Keby sme mali predmety \(A\) a \(B\) kde \(A\) má termín skôr ako \(B\) ale \(B\) sa učíme skôr ako \(A\), môžeme ich poradie vymeniť. \(A\) tak dokončíme skôr a \(B\) vtedy, čo pôvodne \(A\). To je ale v poriadku, keďže vieme, že \(A\) má termín skôr ako \(B\). V nasledujúcich riešeniach si teda predmety na začiatku zoradíme a tým pádom nám vypadáva nutnosť riešiť v akom poradí ich budeme študovať.

A tu sa nám pomerne priamočiaro rodí ďalšie riešenie. Prejdeme si všetkými podmnožinami predmetov a pre každú skontrolujeme, či dokážeme všetky jej predmety urobiť. Takéto riešenie má časovú zložitosť okolo \(O(n 2^n)\) a po jeho odovzdaní sme odmenení dvoma bodmi.

Dynamika

A v tomto bode už skúseného KSP-čkara neprekvapí, že optimálnym riešením bude dynamické programovanie.

Zamyslime sa teda, čo by sme chceli mať ako stav tejto dynamiky. Keďže ideme robiť dynamiku, budeme mať nejaké malé podproblémy a budeme ich rozširovať na väčšie. Teda, aby sme vedeli, či vieme do riešenia pridať nejaký predmet budeme potrebovať skontrolovať či by sme ho vôbec stíhali, a teda v stave určite budeme potrebovať mať počet dní zatiaľ strávených štúdiom \(j\). Tiež sa však potrebujeme uistiť, že predmet do jedného riešenia nepridáme dvakrát, tak si pamätajme aj posledný študovaný predmet \(i\). Ak \(i=0\), znamená to, že sme žiadny predmet ešte nevybrali.

Pre \(i=0\) je riešenie jasné - žiadne kredity získať nevieme. Ako teraz spočítame hodnoty stavov s nejakým \(i \geq 1\) ak vieme riešenia pre všetky stavy s menším \(i\)? Najprv si skontrolujeme, či by sme takto vôbec predmet doštudovali pred skúškou, teda či \(j \leq d_i\). Ak nie, hodnota stavu je samozrejme 0. Inak si prejdeme všetkými možnými predošlými predmetmi a zoberieme najlepšiu možnosť - \(\text{dp}[i][j] = \max_{0 \leq x \leq i-1} \text{dp}[x][j-t_i] + k_i\). Toto nám dáva časovú zložitosť \(O(n^2 D)\), čo je dostatočne rýchle na získanie šiestich bodov.

Optimálne riešenie

Optimalizácia, ktorá nám získa posledné dva body je pomerne jednoduchá a podobá sa klasickému 0-1 knapsacku. Prestaňme vynucovať, že \(i\) je posledný predmet – nech len hovorí, že žiadny predmet po ňom sme už nepoužili. Toto ale znamená, že pri prechode nebudeme musieť prechádzať všetky \(x\) menšie ako \(i\), ale len \(x=i-1\), pretože všetky ostatné v ňom budú zahrnuté. Nový prechod tak bude jednoducho \(\text{dp}[i][j] = \max(\text{dp}[i-1][j], \text{dp}[i-1][j-t_i] + k_i)\) ak \(j\leq d_i\), inak proste dp\([i-1][j]\) . Toto nám dáva časovú aj pamäťovú zložitosť \(O(n \log n + n D)\). Môžeme si však všimnúť, že pri počítaní stavov s \(i\) potrebujeme len stav \(i-1\), čo znamená, že ostatné vieme postupne zahadzovať a tak mať pamäťovú zložitosť \(O(n+D)\).

#include <bits/stdc++.h>
using namespace std;

struct Predmet {
    int k, d, t;
    Predmet(int ki, int di, int ti) : k(ki), d(di), t(ti) {}
};

int main() {
    int n;
    cin >> n;

    vector<Predmet> predmety;
    for (int i = 0; i < n; i++) {
        int ki, di, ti;
        cin >> ki >> di >> ti;
        predmety.push_back(Predmet(ki, di, ti));
    }

    // predmety zoradíme podľa di
    sort(predmety.begin(), predmety.end(),
         [](Predmet a, Predmet b) { return a.d < b.d; });

    int D = 0;
    for (auto i : predmety) D = max(D, i.d);

    vector<int> dp(D + 1, 0);

    for (int i = 0; i < n; i++) {
        vector<int> new_dp(D + 1, 0);  // spravíme si novy vektor, aby sme
                                       // nepouzili jeden predmet dvakrat
        for (int t = 0; t <= D; t++) {
            int zaciatok = t - predmety[i].t;
            if (t > predmety[i].d || zaciatok < 0) {
                new_dp[t] = dp[t];
            } else {
                new_dp[t] = max(dp[t], dp[zaciatok] + predmety[i].k);
            }
        }
        dp = new_dp;
    }
    int res = 0;
    // riesenim je maximum celej tabulky
    for (auto i : dp) res = max(res, i);
    cout << res << endl;
}