8. Dežo vzorové riešenie

5 5
0 3 0 
0 2 1
1 3 5
3 5 9
2 5 6

10

V tejto úlohe bolo treba nájsť počet spôsobov, ktorými sa vie Dežo dostať stopom z Trnavy do Nitry.

Hrubá sila

Môžeme vyskúšať všetky možné podmnožiny áut. Zostáva zistiť pre danú podmnožinu či funguje.

Prvá vec čo potrebujeme zistiť je, v akom poradí tieto autá použijeme. Čas, v ktorom \(i\)-te auto prejde nejakým bodom \(x\), vieme vypočítať ako \(t_i + x - a_i\). To znamená, že z \(i\)-teho auta vieme prestúpiť do \(j\)-teho iba ak \(t_i + x - a_i < t_j + x - a_j\), teda \(t_i - a_i < t_j - a_j\). Na začiatku si teda môžeme všetky autá usporiadať podľa \(t_i - a_i\) a potom vieme, že autá môžeme použiť iba v poradí v akom sú v tomto zozname.

Keď už máme určené poradie pre danú podmnožnu, musíme ešte skontrolovať, či náhodou nemáme \(t_i - a_i == t_j - a_j\) pre nejaké dve po sebe idúce autá. To by znamenalo, že autá idú naraz a teda nestíhame prestúpiť.

Ak nám to časovo sedí, treba ešte zistiť či to sedí aj priestorovo. Prejdeme autá a pamätáme si interval \((l_i;r_i\rangle\) v ktorom vieme skončiť po použití prvých \(i\) áut. Prvé auto musí mať \(a_1 = 0\) aby sme vedeli nastúpiť a potom \(l_1=a_1\) a \(r_1=b_1\). Do auta \(i+1\) vieme prestúpiť práve vtedy, ak \(a_{i+1} <= r_i \wedge b_{i+1} > l_i\). Ak \(a_{i+1} <= l_i\), vieme presúpiť a potom aj vystúpiť v nejakom bode za \(l_i\). Ak \(a_{i+1} > l_i\), vieme prestúpiť najskôr v bode \(a_{i+1}\) a teda vystúpiť v nejakom bode neskôr ako \(a_{i+1}\) (lebo sa musíme viezť nenulový čas). Teda \(l_{i+1} = \max(l_i, a_{i+1})\). Najneskôr vieme vystúpiť vždy v \(b_{i+1}\), teda \(r_{i+1}=b_{i+1}\). Ak sa nám podarí prísť až do konca a \(r_n=s\), je daná množina áut použiteľná.

Časová zložitosť tohoto riešenia je \(O(n\cdot 2^n+n\log(n))\). Pamäťová zložitosť je \(O(n)\).

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

using namespace std;

struct Car
{
    int a, b;
    int t;
};

int main()
{
    int n, s;
    cin >> n >> s;
    vector<Car> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].a >> v[i].b >> v[i].t;
    sort(v.begin(), v.end(), [](Car a, Car b)
         { return (a.t - a.a) < (b.t - b.a); });

    int result = 0;
    for (int i = 0; i < (1 << n); i++)
    {
        int l = 0, r = 0;
        bool fail = false;
        int t = -1;
        for (int j = 0; j < n; j++)
        {
            if (!(i & (1 << j)))
                continue;
            Car c = v[j];
            if (c.t - c.a <= t || c.a > r || c.b <= l)
            {
                fail = true;
                break;
            }
            r = c.b;
            l = max(l, c.a);
            t = c.t - c.a;
        }
        if (!fail && r == s)
            result++;
    }
    cout << result << "\n";
}

Dynamika

Pre každú neprázdnu podmnožinu áut, ak ich vieme postupne všetky použiť, vieme definovať interval v ktorom môžeme skončiť po tejto ceste. Bude to polootvorený interval v tvare \((l;r\rangle\).

Pre každú trojicu \(k, l, r\) si spočítame, koľko existuje podmnožín z prvých \(k\) áut (máme ich usporiadané v poradí v akom idú), ktorých cesta končí v intervale \((l;r\rangle\). Túto hodnotu si označime \(D(k,l,r)\). Očividne \(D(k,l,r)=0\) ak \(l>=r\).

Povedzme, že to máme spočítané pre všetky \(k<i\) a ideme to počítať pre \(k=i\). To vypočítame ako \(D(i,l,r)=D(i-1,l,r) + d(i,l,r)\), kde \(d(i,l,r)\) je počet nových ciest, ktoré použijú aj auto \(i\).

Každá cesta končiaca autom \(i\) končí najneskôr v bode \(b_i\), teda pre všetky \(l, r\) kde \(r\neq b_i\) máme \(d(i,l,r)=0\). Tak isto pre \(l<a_i\) nevieme použiť \(i\)-te auto, keďže z neho vieme vystúpiť iba neskôr ako \(a_i\), teda pre ne tiež \(d(i,l,r)=0\).

Nech \(j\) je posledné auto ktoré ide ostro skôr ako \(i\) (teda sa z neho dá prestúpiť). Zvyšné hodnoty teraz vieme vypočítať ako:

• \(d(i,a_i,b_i)=\sum_{l=0}^{a_i} \sum_{r=a_i}^s D(j,l,r)\), \(+1\) ak \(a_i=0\)

• \(d(i, l, b_i)=\sum_{r=l+1}^s D(j, l, r)\); pre \(a_i<l<b_i\)

Keď \(a_i=0\), môžeme auto \(i\) použiť aj ako úplne prvé. Takáto cesta končí v intervale \((a_i;b_i\rangle\), preto pripočítame \(1\) k \(d(i,a_i,b_i)\).

Výpočet začneme tým, že \(D(0,l,r)=0\) a potom postupne počítame \(D(i,l,r)\) pre \(i=1,2,3\dots\).

Keď pridáme nové auto, nové hodnoty vieme vypočítať v čase \(O(s^2)\), teda celková časová zložitosť je \(O(n\cdot s^2)\). Pamäťová zložitosť je tiež \(O(n\cdot s^2)\).

Pamäťová zložitosť sa zlepšiť na \(O(s^2)\). Stačí si pamätať hodnoty \(D(i,l,r)\) pre predchádzajúce \(i\) a k tomu ešte hodnoty \(D(j,l,r)\) pre posledné auto \(j\), ktoré ide ostro skôr. Ďalšie hodnoty budú vždy zavisieť iba od týchto dvoch.

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

using namespace std;

struct Car
{
    int a, b;
    int t;
};

int main()
{
    int n, s;
    cin >> n >> s;
    vector<Car> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].a >> v[i].b >> v[i].t;
    sort(v.begin(), v.end(), [](Car a, Car b)
         { return (a.t - a.a) < (b.t - b.a); });

    vector<vector<long long>> dyn;
    for (int i = 0; i <= s; i++)
        dyn.push_back(vector<long long>(i));

    for (int i = 0; i < n;)
    {
        auto last = dyn;
        int t = v[i].t - v[i].a;
        vector<Car> cars;
        while (i < n && v[i].t - v[i].a == t)
            cars.push_back(v[i++]);
        for (Car c : cars)
        {

            if (c.a == 0)
            {
                dyn[c.b][c.a]++;
                dyn[c.b][c.a] %= MOD;
            }

            for (int b = 0; b <= s; b++)
                for (int a = 0; a < b; a++)
                {
                    if (c.a > b || c.b <= a)
                        continue;

                    dyn[c.b][max(a, c.a)] += last[b][a];
                    dyn[c.b][max(a, c.a)] %= MOD;
                }
        }
    }

    long long result = 0;
    for (int i = 0; i < s; i++)
        result += dyn[s][i];
    result %= MOD;
    cout << result << "\n";
}

Intervaláč

Lepšie riešenie vieme dosiahnuť tým, že si hodnoty budeme pamätať v súčtovom intervalovom strome. Keď vypočítame hodnoty pre \(i\), budeme ich mať zapísané v \(s\) intervaláčoch: jeden intervaláč pre každé \(l\), v ktorom budeme mať hodnoty \(D(i,l,r)\) pre \(0\leq r \leq s\). Tieto intervaláče budeme upravovať pritom ako spracúvame ďalšie autá.

Vždy naraz spracujeme všetky autá ktoré idú naraz (podľa \(t-a\)). Nech sú to autá \(i+1\) až \(j\). Vieme, že \(D(j,l,r)=D(i,l,r) + d(i+1,l,r) + d(i+1,l,r) \dots d(j,l,r)\). Najprv teda vypočítame všetky \(d(x,l,r)\) (\(x \in \{i+1,\dots,j\}\)) a potom v intervaláči pričítame tieto hodnoty.

Nemusíme počítať tie \(d(x,l,r)\), o ktorých vieme, že sa vždy rovnajú \(0\), teda stačí vždy vypočítať iba \(d(x,l,b_x)\) pre \(a_x\leq l<b_x\). Hodnotu \(d(x,a_x,b_x)\) vieme vypočítať pomocou \(s\) otázok na intervaláč v \(O(s\log s)\) a každú z \(d(x,l,b_x)\) pre \(a_x<l<b_x\) vypočítame jednou otázkou v \(O(\log s)\).

Časová zložitosť tohto riešenia bude \(O(ns\log s + s^2)\), pričom \(s^2\) je kvôli skonštruovaniu intervaláča. Tohoto člena sa vieme zbaviť tým, že intervaláč budeme konštruovať dynamicky počas každej query. Pamäťová zložitosť je \(O(s^2)\) alebo \(O(ns\log s)\) pri dynamickom intervaláči.

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

using namespace std;

struct Car
{
    int a, b;
    int t;
};

struct Inter
{
    long long val = 0;
    int l, r;
    Inter *L = nullptr;
    Inter *R = nullptr;
    Inter(int l, int r) : l(l), r(r) {}
    long long get(int ll, int rr)
    {
        if (ll >= r || rr <= l)
            return 0;
        if (ll <= l && rr >= r)
            return val;
        lazy_propagate();
        return (L->get(ll, rr) + R->get(ll, rr)) % MOD;
    }
    void add(int p, long long v)
    {
        if (p >= r || p < l)
            return;
        val += v;
        val %= MOD;
        if (r > l + 1)
        {
            lazy_propagate();
            L->add(p, v);
            R->add(p, v);
        }
    }
    void lazy_propagate()
    {
        if (L == nullptr)
            L = new Inter(l, (l + r) / 2);
        if (R == nullptr)
            R = new Inter((l + r) / 2, r);
    }
};

int main()
{
    int n, s;
    cin >> n >> s;
    vector<Car> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].a >> v[i].b >> v[i].t;
    sort(v.begin(), v.end(), [](Car a, Car b)
         { return (a.t - a.a) < (b.t - b.a); });

    vector<Inter> dyn;
    for (int i = 0; i < s; i++)
        dyn.push_back(Inter(0, s + 1));

    for (int i = 0; i < n;)
    {
        int t = v[i].t - v[i].a;
        vector<Car> cars;
        while (i < n && v[i].t - v[i].a == t)
            cars.push_back(v[i++]);
        vector<vector<long long>> add;
        for (Car c : cars)
        {
            add.push_back(vector<long long>(s));
            if (c.a == 0)
                add.back()[c.a]++;
            for (int a = 0; a < c.b; a++)
                add.back()[max(a, c.a)] += dyn[a].get(c.a, s + 1);
        }
        for (int ci = 0; ci < cars.size(); ci++)
            for (int a = 0; a < s; a++)
            {
                add[ci][a] %= MOD;
                dyn[a].add(cars[ci].b, add[ci][a]);
            }
    }

    long long result = 0;
    for (long long i = 0; i < s; i++)
        result += dyn[i].get(s, s + 1);
    result %= MOD;
    cout << result << "\n";
}

Optimálne riešenie

V optimálnom riešení budeme používať iba dva intervaláče. Prvý \(L(l)\) bude obsahovať počty ciest, ktorých interval začína v bode \(l\), teda \(L(l)=\sum_{r=0}^s D(i,l,r)\) (vždy pre nejaké konkrétne \(i\)) a druhý \(R(r)\) bude obsahovať počty ciest, ktorých interval končí v bode \(r\), teda \(R(r)=\sum_{l=0}^s D(i,l,r)\). Súčty intervalov budeme označovať \(L(a,b)=\sum_{i=a}^b L(i)\) a \(R(a,b)=\sum_{i=a}^b R(i)\)

Keď pridávame nejaké nové auto \(i\), potrebujeme vypočítať počet ciest z ktorých sa naňho dá prestúpiť. To budú také cesty, ktorých interval sa prekrýva s intervalom \(\langle a_i;b_i \rangle\). To vieme vypočítať ako \(R(a_i,s)-L(b_i,s)\). Toľko bude nových ciest, ktoré použijú toto auto. Keďže interval každej z nich končí v bode \(b_i\), intrvaláču \(R\) stačí k \(R(b_i)\) pričítať túto hodnotu.

Aktualizovať intervaláč \(L\) bude o niečo komplikovanejšie, lebo začiatky intervalov ciest sú rôzne. Ak na auto \(i\) prestúpime z cesty, ktorej interval začína skôr ako \(a_i\), interval novej cesty bude začínať v bode \(a_i\). Počet takýchto ciest vieme vypočítať ako \(R(a_i,s)-L(a_i,s)\). Teda k \(L(a_i)\) musíme pričítať túto hodnotu.

Zostávajú intervaly ktoré začínajú v \(a_i\) a neskôr. Takéto intervaly majú prekryv práve vtedy, ak začínajú skôr ako \(b_i\). Ak takýto interval začína v \(l\), nový interval bude tiež začínať v \(l\). To znamená, že pre všetky \(a_i \leq l < b_i\) musíme spraviť \(L(l) += L(l)\), alebo teda \(L(l)\text{ *= }2\). Takúto operáciu “plus svoja hodnota” vieme robiť lazy intervaláčom.

Vždy si najprv niekde zapíšeme aké operácie chceme na intervaláčoch spraviť a potom ich vykonáme, aby sme si počas výpočtu neprepísali staré hodnoty novými. Ak máme niekoľko áut, ktoré idú naraz, zapíšeme si najprv operácie pre všetky autá a až potom ich vykonáme. Treba si pri tom dať pozor ako vyhodnotíme operácie typu “plus svoja hodnota”. Ak viacero áut chce aplikovať túto operáciu na rovnakej pozícii, vo výsledku musíme na tejto pozícii spraviť \(\times 3\). Ak by sme iba postupne dvakrát aplikovali túto operáciu, dostali by sme \(\times 4\). Toto vieme vyriešiť tým, že si v zvlášť dátovej štruktúre udržiavame akým číslom treba ktoré pozície vynásobiť a potom na konci to aplikovať.

Na to môžeme použiť napríklad mapu (\(M\)) a keď nám príde nejaké auto \(i\), spravíme \(M[a_i]\text{ += }1\), \(M[b_i]\text{ -= }1\). Keď chceme zistiť, akým číslom treba vynásobiť pozíciu \(x\), vieme to vypočítať ako \(\sum_{i=0}^x M[i]\). Na konci teda iba preiterujeme túto mapu, pričom si pamätáme doterajší súčet a vždy týmto číslo vynásobíme interval medzi dvoma po sebe idúcimi kľúčmi tejto mapy. Ak máme takto \(k\) áut, týchto intervalov bude najviac \(2k\) a teda len toľko operácií musíme na intervaláči vykonať.

Keď prejdeme všetky autá, odpoveď zistíme jednoducho ako \(R(s)\).

Pre každé auto spravíme iba konštantne veľa operácií s intervaláčom. teda časová zložitosť je \(O(n\log s)\). Pamäťová zložitosť je tiež \(O(n\log s)\). Obe zložitosti sú za predpokladu, že používame dynamické intervaláče.

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

using namespace std;

struct Car
{
    int a, b;
    int t;
};

struct Inter
{
    long long val = 0;
    int l, r;
    long long lazy_mul = 1;
    Inter *L = nullptr;
    Inter *R = nullptr;
    Inter(int l, int r) : l(l), r(r) {}
    long long get(int ll, int rr)
    {
        if (ll >= r || rr <= l)
            return 0;
        if (ll <= l && rr >= r)
            return val;
        lazy_propagate();
        return (L->get(ll, rr) + R->get(ll, rr)) % MOD;
    }
    void add(int p, long long v)
    {
        if (p >= r || p < l)
            return;
        val += v;
        val %= MOD;
        if (r > l + 1)
        {
            lazy_propagate();
            L->add(p, v);
            R->add(p, v);
        }
    }
    void mul(int ll, int rr, long long v)
    {
        if (ll >= r || rr <= l)
            return;
        if (ll <= l && rr >= r)
        {
            lazy_update(v);
            return;
        }
        lazy_propagate();
        L->mul(ll, rr, v);
        R->mul(ll, rr, v);
        val = (L->val + R->val) % MOD;
    }
    void lazy_update(long long v)
    {
        val = (val * v) % MOD;
        lazy_mul = (lazy_mul * v) % MOD;
    }
    void lazy_propagate()
    {
        if (L == nullptr)
            L = new Inter(l, (l + r) / 2);
        if (R == nullptr)
            R = new Inter((l + r) / 2, r);

        if (lazy_mul == 1)
            return;
        L->lazy_update(lazy_mul);
        R->lazy_update(lazy_mul);
        lazy_mul = 1;
    }
};

int main()
{
    int n, s;
    cin >> n >> s;
    vector<Car> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i].a >> v[i].b >> v[i].t;
    sort(v.begin(), v.end(), [](Car a, Car b)
         { return (a.t - a.a) < (b.t - b.a); });

    Inter ends(0, s + 1);
    Inter starts(0, s + 1);

    for (int i = 0; i < n;)
    {
        int t = v[i].t - v[i].a;
        vector<Car> cars;
        while (i < n && v[i].t - v[i].a == t)
            cars.push_back(v[i++]);

        vector<long long> pred;
        vector<long long> prekryv;

        for (Car c : cars)
        {
            long long p = (ends.get(c.a, s + 1) - starts.get(c.a, s + 1) + MOD) % MOD;
            pred.push_back(p);
            prekryv.push_back((p + starts.get(c.a, c.b)) % MOD);
        }

        map<int, int> intervals;
        for (Car c : cars)
        {
            intervals[c.a]++;
            intervals[c.b]--;
        }
        int last_mul = 1;
        int last_start = 0;
        for (auto x : intervals)
        {
            starts.mul(last_start, x.first, last_mul);
            last_start = x.first;
            last_mul += x.second;
        }

        for (int ci = 0; ci < cars.size(); ci++)
        {
            ends.add(cars[ci].b, prekryv[ci]);
            starts.add(cars[ci].a, pred[ci]);
            if (cars[ci].a == 0)
            {
                starts.add(cars[ci].a, 1);
                ends.add(cars[ci].b, 1);
            }
        }
    }

    long long result = ends.get(s, s + 1);
    cout << result << "\n";
}