6. Dlhodobý Krtkov plán vzorové riešenie

2 4

2

Prvá vec, ktorú si môžeme uvedomiť, je koľko najmenej času potrebujeme na \(n\) úloh. Najmenej času, ktorý vieme venovať najmenej dôležitej úlohe je \(0\). Potom najmenej času ktorý vieme venovať druhej najmenej dôležitej úlohe je 1. Vo všeobecnosti vieme povedať, že ak máme \(i\)-tu najmenej dôležitú úlohu, musíme jej venovať aspoň \(i-1\) času. Každej z i-1 menej dôležitých úloh musíme totiž venovať iný čas. \(n\) úlohám teda musíme venovať aspoň \(0 + 1 + 2 + ... + (n-1) = \frac{(n-1)\cdot n}{2}\)

Keď už vieme koľko času najmenej musíme venovať ktorej úlohe, môžeme problém zo zadania mierne upraviť. Zvyšný čas, teda \(m - \frac{(n-1)\cdot n}{2}\) chceme rozdeliť medzi \(n\) úloh tak, aby dôležitejšia dostala viac alebo rovnako ako menej dôležitá. To môže pôsobiť ako zbytočné, no povedie to ku kúsok jednoduchšej implementácií.

Riešenie

Túto úlohu budeme riešiť pomocou dynamického programovania. Cheme zistiť, ako sa dá rozdeliť čas medzi nejaké úlohy. Prvým riešením by mohlo byť, že vyskúšame všetky možnosti koľko času môžeme venovať najmenej dôležitej úlohe, a zvyšok je podobná otázka - o jednu úlohu menej a o nejaký čas menej. Možeme si všimnúť, že ak sa rozhodneme venovať najmenej dôležitej úlohe \(k\) času, musíme aj každej ďaľšej úlohe venovať aspoň \(k\) času. Počet možností teda môžeme spočítať ako \(f(u, c) = \sum f(u-1,\ c-u\cdot k)\), kde \(f(u, c)\) je počet možností ako vieme rozdeliť medzi \(u\) úloh \(c\) času. Samozrejme využijeme memoizáciu, aby sme jednu hodnotu nepočítali viackrát.

Takéto riešenie prejde všetky možnosti ako vieme rozdeliť čas medzi úlohy. Pozrime sa na zložitosti. Máme \(n \cdot m\) stavov, každý vieme spočítať v \(O(m)\). Výsledná zložitosť teda bude \(O(nm^2)\).

Vzorové riešenie

V predošlom riešení sme sa vždy rozhodli koľko presne času budeme venovať jednej úlohe, čo viedlo k tomu, že jeden stav sme museli počítať až v zložitosti \(O(m)\). V tomto riešení to vylepšíme. Vždy sa rozhodneme, či najmenej dôležitej úlohe ešte budeme pridávať čas, alebo už nie. Presnejšie sa rozhodneme či pridáme ešte \(1\) čas. Opakovaným pridávaním \(1\) času vieme pridať ľubovoľne veľa. Ak čas pridáme, musíme ho pridať aj všetkým ostatným úlohám, podobne ako v minulom riešení. Bude teda platiť, že \(f(u, c) = f(u,\ c-u) + f(u-1, c)\). Počet rôznych stavov, ktoré potrebujeme spočítať sa nezmenil, ale každý už vieme vypočítať v \(O(1)\). Preto celková časová zložitosť našeho algoritmu bude \(O(nm)\) a pamäťová \(O(nm)\).

Táto pamäťová zložitosť sa dá ešte zlepšiť. Predstavme si, že máme iteratívne naprogramovaný náš algoritmus. Teda máme dvojrozmerné pole, a postupne ho vypĺňame hodnotami \(f(u, c)\). Všimnime si, že keď dopĺňame riadok pre nejaké \(u\), nepotrebujeme si pamätať celú tabuľku, ale stačí nám posledný a aktuálny riadok - teda tie, pre \(u\) a \(u-1\). Takto vieme zmenšiť pamäťovú zložitosť na \(O(m)\).

n, m = map((int), input().split())
mod = 1000000007

m -= n*(n-1)//2

if m < 0:
    print("0")
else:
    dp = []
    for i in range(n+1):
        a = []
        for j in range(m+n+1):
            a.append(0)
        dp.append(a)

    
    dp[0][0] = 1

    for u in range(n):
        for c in range(m+1):
            dp[u][c+n-u] += dp[u][c]
            dp[u][c+n-u] %= mod
            dp[u+1][c] += dp[u][c]
            dp[u+1][c] %= mod

    print(dp[n][m])

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

int main()
{
    
    long long n, m;
    cin >> n >> m;

    m -= n*(n-1)/2;

    if(m < 0 )
    {
        cout << "0\n";
        return 0;
    }

    vector<vector<long long>> DP(n+1, vector<long long>(m+n+1));
    DP[0][0] = 1;

    for(int u = 0; u < n; u++)
    {
        for(int c = 0; c <= m; c++)
        {
            DP[u][c+n-u] += DP[u][c];
            DP[u][c+n-u] %= MOD;
            DP[u+1][c] += DP[u][c];
            DP[u+1][c] %= MOD;
        }
    }        

    cout << DP[n][m] << '\n';
    
    return 0;
}