7. Srny, Viki, Viki a iné divé veci vzorové riešenie

3 2
1 2 3
1 2

2

Túto úlohu budeme riešiť pomocou dynamického programovania. Budeme sa pozerať len na posledný krok. Zamyslime sa, čo by mohol byť jeden stav našej dynamiky. Potrebujeme ním nejak popísať stav oboch šúp kalerábu. Stav jednej šupy jednoznačne popisuje jedno číslo - počet zostávajúch kusov na danej šupe. Náš stav teda bude dvojica čísel, počty ostávajúcich kusov. Rôznych stavov teda bude \(O(nm)\). Ako vieme zistiť riešenie pre jednu dvojicu?

Prvé riešenie

V jednom kroku Viki a Viki zvolia koľko kusov sa odstráni z ktorej šupy, a na základe toho pribudnú nejaké srny. Naše riešenie by teda mohlo prejsť cez všetky možnosti, a vybrať z nich najlepšiu - tú pri ktorej sa v koši objaví najmenej sŕn. Keďže máme potencionálne až \(n\) možností ako zvoliť \(x\), a \(m\) možností ako zvoliť \(y\), výpočet jedného stavu by nám zabral \(O(nm)\) času. Celý program by teda bežal v časovej zložitosti \(O(n^2m^2)\).

Optimalizácia

Všimnime si, že výraz \((S - x)\) a \((Z - y)\) má rovnaký efekt ako zníženie všetkých čísel o \(1\) a minimalizovanie výrazu \(S X\). Tento krok nie je nutný na vyriešenie úlohy, ale výrazne zjednoduší zápis nasledujúcich vzorcov.

V optimálnom riešení bude v každom kroku buď \(x\) alebo \(y\) \(1\). Predpokladajme, že by v optimálnom riešení bol krok, pri ktorom zvolené \(x\) aj \(y\) bolo väčšie ako \(1\). Počet sŕn v koši by potom bol \(S Z\). Nech \(s\) a \(z\) sú počty listov na posledných kusoch kalerábov tak, že \(S = S' + s\) a \(Z = Z' + z\). Počet sŕn v koši je teda \((S' + s) (Z' + z)\). Ak by sme ale najprv spravili krok, kde zvolíme hodnoty \(1\) a \(1\), a potom krok pre \(x-1\) a \(y-1\) v koši sa objaví \(s * z + S' Z'\) sŕn. V optimálnom riešení sa však v koši objavilo \(S Z = (s + S') * (z + Z') = s z + S' Z' + s Z' + z S'\) sŕn. Keďže ale \(s Z' + z S' \geq 0\) tak aj v novom riešení sa v koši objavilo nanajvýš toľko sŕn, čo znamená, že môžeme (alebo dokonca musíme) spraviť krok dĺžky \(1\). Opakovaným aplikovaním tohoto postupu ukážeme, že určite existuje optimálne riešenie, v ktorom je vždy \(x\) alebo \(y\) rovné \(1\).

Tento poznatok môžeme využiť vo svojom riešení. Pri skúšaní už budeme skúšať iba tie dvojice \(x\) a \(y\), kde \(x=1\) alebo \(y=1\). Nemáme už \(nm\) možností ale iba \(n+m\) možností. Naše vylepšené riešenie teda má časovú zložitosť \(O(nm(n+m))\), čiže rádovo kubickú.

Vzorové riešenie

Zatiaľ sme vždy pri výpočte počítali, že Viki a Viki spravia celý krok. Pozrime sa teraz na niečo ako medzikroky. Ak teraz rátame s možnosťou, že zvolíme \(x=1\), tak sa vieme vždy rozhodnúť, či zväčšíme \(y\) o \(1\), alebo tento krok “ukončíme”. Vždy keď zvačšíme \(y\) o \(1\) sa v koši objaví \(s z\) sŕn, kde \(s\) je počet listov na poslednej šupy prvého kusu kalerábu, a \(z\) je počet listov na poslednej šupy druhého kusu kalerábu. Uvedomme si, že môžeme počet sŕn rátať takto postupne. Vyplýva to z distributívnosti násobenia a sčítavania (\(s Z = s (z_1 + ... + z_{k-1} + z_k) = (s z_1 + ... + s z_{k-1}) + s z_k\)).

Náš stav teda bude trojica počty zostávajúcich kusov jedného a druhého kalerábu a indikátor, z ktorého kusu berieme viac ako \(1\). Počet stavov sa teda zdvojnásobí, ale stále bude stavov \(O(nm)\).

Hodnotu v jednom takomto stave vieme vypočítať v konštantnom čase. Možnosti, ktoré treba vyskúšať, sú zobrať ešte jeden alebo ukončiť. Ak ukončíme, tak máme ešte 2 možnosti, či v ďaľšom kroku budeme brať viac z prvého alebo druhého kusu.

Časová zložitosť

Časová zložitosť nášho algoritmu teda bude \(O(nm)\). Hodnotu pre každý z \(O(nm)\) stavov vieme zistiť v konštantnom čase.

Pamäťová zložitosť

Ak si budeme pamätať hodnotu pre každý stav, priestorová zložitosť nášho algoritmu bude \(O(nm)\). Ak by sme ale algoritmus implementovali iteratívne, mohli by sme si všimnúť, že dokážame zlepšiť pamäťovú zložitosť na O(n+m).

Program

Rekurzívne implementované riešenie:

#include <bits/stdc++.h>

#define ll long long
#define INF 123456789123456789
using namespace std;

vector<vector<vector<ll>>> memo;
vector<vector<ll>> v(2);

ll f(vector<ll> &i, ll k)
{
    if(i[0] == -1 && i[1] == -1) return 0;
    if(i[0] < 0 || i[1] < 0) return INF;
    if(memo[i[0]][i[1]][k] == -1)
    {
        auto ni = i;
        ni[k]--;
        memo[i[0]][i[1]][k] = f(ni, k) + v[0][i[0]]*v[1][i[1]];
        ni[!k]--;
        memo[i[0]][i[1]][k] = min(memo[i[0]][i[1]][k], v[0][i[0]]*v[1][i[1]] + min(f(ni, k), f(ni, !k)));
    }
    return memo[i[0]][i[1]][k];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n, m;
    cin >> n >> m;

    v[0].assign(n, 0);
    v[1].assign(m, 0);

    for(ll i = 0; i < n; i++) cin >> v[0][i];
    for(ll i = 0; i < m; i++) cin >> v[1][i];

    for(ll i = 0; i < n; i++) v[0][i]--;
    for(ll i = 0; i < m; i++) v[1][i]--;

    memo.assign(n, vector<vector<ll>>(m, vector<ll>(2, -1)));
    n--;m--;
    vector<ll> x = {n, m};
    cout << min(f(x, 0), f(x, 1)) << '\n';

    return 0;
}

Riešenie s lineárnou pamäťovou zložitosťou:

#include <bits/stdc++.h>


#define ll long long
#define INF 123456789123456789

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n, m;
    cin >> n >> m;

    vector<vector<ll>> v(2);
    v[0].assign(n, 0);
    v[1].assign(m, 0);

    for(int i = 0; i < n; i++) cin >> v[0][i];
    for(int i = 0; i < m; i++) cin >> v[1][i];

    for(int i = 0; i < n; i++) v[0][i]--;
    for(int i = 0; i < m; i++) v[1][i]--;
    
    vector<vector<vector<ll>>> memo(2, vector<vector<ll>>(m, vector<ll>(2, INF)));

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            for(int k = 0; k < 2; k++)
            {
                memo[i&1][j][k] = INF;
                if(i == 0 && j == 0)
                {
                    memo[i&1][j][k] = v[0][0]*v[1][0];
                    continue;
                }

                if(i-1 >= 0 && j-1 >= 0)
                {
                    memo[i&1][j][k] = min(memo[i&1][j][k], v[0][i]*v[1][j] + min(memo[(i-1)&1][j-1][k], memo[(i-1)&1][j-1][!k]));
                }
                if(k == 1)
                {
                    if(j-1 >= 0) memo[i&1][j][k] = min(memo[i&1][j][k], memo[i&1][j-1][k] + v[0][i]*v[1][j]);
                }
                else{
                    if(i-1 >= 0) memo[i&1][j][k] = min(memo[i&1][j][k], memo[(i-1)&1][j][k] + v[0][i]*v[1][j]);
                }
            }
        }
    }
    n--;m--;
    cout << min(memo[n&1][m][0], memo[n&1][m][1]) << '\n';

    return 0;
}