8. Abnormálne Veľký Hotel (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

Úloha

Prideľovač¹ pracuje v hoteli s \(n\) izbami číslovanými od \(0\) po \(n - 1\) vrátane.

Prideľovač dostáva dva druhy požiadaviek:

check-in požiadavky, ktoré obsahujú číslo \(x\) – počet miestností potrebný pre skupinu hostí. Prideľovač týchto hostí ubytuje do \(x\) po sebe idúcich voľných izieb. Prideľovač vždy vyberie taký usek izieb, ktorý minimalizuje minimálne číslo izby zo všetkých čísel izieb v úseku.
check-out požiadavky, ktoré obsahujú číslo \(i\) – index skoršej check-in požiadavky. Check-in požiadavky indexujeme od \(0\) a do indexovania nerátame check-out požiadavky. Skupina hostí ubytovaná v \(i\)-tej check-in požiadavke uvoľní svoje miestnosti a opustí hotel.

Je zaručené, že Prideľovač bude schopný naplniť všetky požiadavky.

Vašou úlohou je vypísať pre každú check-in požiadavku číslo najmenšej izby z úseku miestností pridelených skupine hostí.

Formát vstupu

Na prvom riadku vstupu sú dve medzerou oddelené prirodzené čísla \(n\), \(q\) – počet izieb v hoteli a počet požiadaviek.

Nasleduje \(q\) riadkov. Každý riadok obsahuje jednu požiadavku. Check-in požiadavky majú tvar I x, \(x\) – počet miestností potrebný pre skupinu hostí. Check-out požiadavky majú tvar O i, \(i\) – index skoršej check-in požiadavky.

Formát výstupu

Pre každú check-in požiadavku vypíšte na jeden riadok jediné číslo – číslo najmenšej izby z úseku miestností pridelených skupine hostí.

Hodnotenie

Sú 4 sady vstupov po 2 bodoch. Platia v nich nasledovné obmedzenia:

Sada	1	2	3	4
\(1 \leq n\ \leq\)	\(10^3\)	\(10^9\)	\(10^9\)	\(10^{18}\)
\(1 \leq q\ \leq\)	\(10\)	\(5\,000\)	\(300\,000\)	\(600\,000\)

Príklad

Input:

9 7
I 3
I 3
O 0
I 2
I 2
I 1
I 1

Output:

Reprezentujme hotel stringov znakov, kde i-ty znak reprezentuje stav i-tej izby. Spočiatku je hotel prázdny ---------. Príde skupina troch hostí 000------. Príde ďaľšia skupina troch hostí 000111---. Odubytuje sa skupina hostí 0 ---111---. Príde skupina 2 hostí 22-111--- a na to ďaľšia 22-11133-. Nakoniec príde jeden človek 22411133- a za ním ďalší 224111335.

Ujo, ktorého úlohou je ubytovávať a odubytovávať hostí↩︎

Brute-force riešenie

Táto úloha má pomerne jednoduché bruteforce riešenie, ktoré stačí na polovicu bodov. Stačí simulovať proces prichádzania a odchádzania ľudí a udržiavať si pri tom dve informácie:

Pole intervalov voľných izieb. Na začiatku behu obsahuje interval \([0, n)\).
Pole intervalov priradených izieb, v ktorom si pre každú skupinu pamätáme priradené izby, nech ich vieme odubytovať, keď na to príde čas. Na začiatku je prázdne. Počas behu pole_i obsahuje interval, ktorý bol priradený \(i\)-tej skupine.

Keď príde check-in požiadavka, lineárne prejdeme pole obsahujúce úseky voľných izieb a nájdeme taký úsek, ktorý je dosť dlhý na ubytovanie celej skupiny a zároven je najviac vľavo. Do nájdeného úseku ubytujeme hostí a vymažeme ho zo zoznamu voľných úsekov. Je však možné, že nájdený úsek bol dlhší než bolo nutné. V takom prípade pridáme naspäť do zoznamu nepoužitú časť úseku. Na záver vložíme na koniec poľa priradených intervalov izieb interval, ktorý sme priradili novej skupinke.

Keď príde check-out požiadavka, nazrieme do pola priradených izieb na korešpondujúci index. Tieto izby chceme uvoľniť, čo znamená, že ich chceme vložiť naspäť do poľa voľných úsekov izieb. Avšak, nemôžme tento úsek len tak vložiť naspäť do zoznamu voľných, lebo je možne, že existujú ďalšie izby v zozname voľných tesne pred/za naším úsekom. Napríklad, može sa stať, že pole voľných úsekov aktuálne obsahuje úseky \([0, 3)\) a \([4, 7)\) a úsek, ktorý sa snažíme vložiť je \([3, 4)\). Za takých okolností najprv vymažeme úseky \([0, 3)\) a \([4, 7)\) zo zoznamu voľných úsekov, a potom vložíme dnu \([0, 7)\). Inými slovami, vymažeme voľné susediace úseky a potom vložíme naspäť úsek, ktorý je zlúčením úseku patriaceho skupinke z check-out požiadavky a okolitých voľných úsekov.

Pre každú požiadavku robíme viacero lineárnych prehľadávaní a mazaní na poli obsahujúcom intervaly voľných izieb. Týchto intervalov je \(O(q)\), lebo po každej check-out požiadavke nám mohol pribudnúť interval do zoznamu. Po check-in požiadavke ostala dĺžka zoznamu v najhoršom prípade rovnaká. Celková časová zložitosť je teda \(O(q^2)\), lebo je \(O(q)\) požiadaviek a na každú odpovieme v \(O(q)\) čase. Pamäťová zložitosť je \(O(q)\), lebo ako sme spomínali, dĺžka pola voľných izieb je \(O(q)\) a dĺžka pola priradených izieb je tiež \(O(q)\), lebo aspoň polovica požiadaviek sú check-in požiadavky.

Vzorové riešenie

Vzorové riešenie sa od spomenutého brute-force riešenia líši len tým, ako si ukladáme voľné úseky. Brute-force riešenie je pomalé, lebo mu trvá lineárne dlho robiť operácie, ako napríklad hladať najľavejší dostatočne dlhý úsek izieb, mazať úseky izieb a hľadať susediace úseky izieb. Tieto operácie vieme všetky naimplementovať v logaritmickej zložitosti a to tak, že použijeme binárny vyhľadávací strom, napríklad treap.

Majme teda treap voľných úsekov. Keď chceme mazať úseky izieb, je to jednoduché, lebo mazať z treapu sa dá v logaritmickom čase. Rovnako nájsť susediace úseky, v prípade, že kontrolujeme či je treba zjednocovať počas check-outu, je logaritmické, lebo treapy podporujú rýchle hľadanie najmenšieho väčšieho a najväčšieho menšieho prvku než je daný prvok.

Jediná operácia, ktorú treba domyslieť, je hľadanie najľavejšieho úseku dĺžky aspoň \(L\). To dokážeme tak, náš treap upravíme, nech si každý vrchol pamätá okrem svojho intervalu aj dĺžku najdlhšieho intervalu vo svojom podstrome. Nájsť najľavejší úsek dĺžky aspoň \(L\) vieme nasledovnou rekurziou z koreňa treapu:

Ak má môj ľavý podstrom dosť dlhý úsek, rekurzívne ho nájdem a vrátim ho – existuje dobrý úsek a dokonca existuje dobrý úsek vľavo, čo je to, čo chceme.
Ak môj úsek je dosť dlhý, vrátim ho – lebo už viem, že vľavo nič nie je a lepšie vrátiť svoj úsek než úsek sprava.
Rekurzívne nájdem úsek v pravom podstrome – musí tam byť, lebo viem že v mojom podstrome existuje dlhý úsek a viem že nie je ani vľavo, ani vo mne.

Posledná otázka, ktorú treba zodpovedať, je ako rátať pre každý podstrom dĺžku najdlhšieho úseku. Toto je relatívne triviálne, lebo stačí upraviť funckie treapu split, merge, insert a erase nech počas toho, ako manipulujú stromom prerátavajú hodnotu vo svojom vrchole z hodnôt vo svojom ľavom a pravom synovi a dĺžky svojho úseku.

Použitím treapu vieme všetky operácie potrebné na zodpovedanie jednej požiadavky spraviť v \(O(\log q)\), a teda celková časová zložitosť je \(O(q \cdot \log q)\). Pamäťová zložitosť je stále \(O(q)\).

Riešenie intervaláčom

Existuje aj riešenie, ktoré stačí na 6 bodov, ktoré používa dynamický lazy intervalový strom. Takéto riešenie sa dá často použiť a je dobré ho poznať. V každom vrchole stromu si pamätáme najdlhší voľný interval v podstrome vrcholu, plus počet po sebe idúcich voľných izieb od ľavého konca (prefix) a od pravého konca (sufix). Keď máme tieto informácie pre ľavý a pravý podstrom, vieme ich zrátať aj pre ich rodiča:

Najdlhší voľný interval môže byť buď najdlhší voľný interval z ľavého podstromu alebo z pravého, alebo to môže byť kombinácia sufixu ľavého vrcholu a prefixu pravého vrcholu.
Prefix intervalu je rovnaký ako prefix ľavého intervalu, okrem prípadu, kedy je prefix ľavého intervalu rovnako veľký ako celý ľavý interval (čo znamená, že celý ľavý interval je voľný). V takom prípade je prefix celého intervalu zlúčením ľavého intervalu s prefixom pravého intervalu.
Sufix intervalu sa ráta podobne ako prefix.

Ak použijeme dynamickú alokáciu vrcholov na to, aby sme vytvorili iba tie časti stromu, ktoré sú potrebné, tak vieme dosiahnuť časovú zložitosť \(O(q \cdot \log n)\), čo je trochu horšie, než vzorové riešenie. Trochu vačším problémom je však pamäťová zložitosť, ktorá je tiež \(O(q \cdot \log n)\), čo je príliš veľa na poslednú sadu vstupov.

Program

Riešenie treapom:

#include <algorithm>
#include <chrono>
#include <iostream>
#include <optional>
#include <random>

#define F first
#define S second

using namespace std;
using namespace chrono;

using ll = long long;

struct Vrchol {
    Vrchol* lavy;
    Vrchol* pravy;
    pair<ll, ll> usek;
    double priorita;
    ll maximum;
};

void update_max(Vrchol* koren) {
    koren->maximum = koren->usek.second - koren->usek.first;
    if (koren->lavy)
        koren->maximum = max(koren->maximum, koren->lavy->maximum);
    if (koren->pravy)
        koren->maximum = max(koren->maximum, koren->pravy->maximum);
}

pair<Vrchol*, Vrchol*> split(Vrchol* koren, pair<ll, ll> hranica) {
    if (!koren)
        return {nullptr, nullptr};

    if (koren->usek <= hranica) {
        auto par = split(koren->pravy, hranica);
        koren->pravy = par.first;
        update_max(koren);
        return {koren, par.second};
    }
    auto par = split(koren->lavy, hranica);
    koren->lavy = par.second;
    update_max(koren);
    return {par.first, koren};
}

Vrchol* merge(pair<Vrchol*, Vrchol*> par) {
    if (!par.first && !par.second)
        return nullptr;
    if (!par.first)
        return par.second;
    if (!par.second)
        return par.first;

    if (par.first->priorita >= par.second->priorita) {
        par.first->pravy = merge({par.first->pravy, par.second});
        update_max(par.first);
        return par.first;
    }
    par.second->lavy = merge({par.first, par.second->lavy});
    update_max(par.second);
    return par.second;
}

mt19937_64 mt(high_resolution_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dist(0, 1);

Vrchol* insert(Vrchol* koren, pair<ll, ll> usek, double priorita = dist(mt)) {
    if (!koren || priorita > koren->priorita) {
        auto par = split(koren, usek);
        Vrchol* novy = new Vrchol{par.first, par.second, usek, priorita, 0};
        update_max(novy);
        return novy;
    }

    if (usek <= koren->usek) {
        koren->lavy = insert(koren->lavy, usek, priorita);
        update_max(koren);
        return koren;
    }

    koren->pravy = insert(koren->pravy, usek, priorita);
    update_max(koren);
    return koren;
}

Vrchol* erase(Vrchol* koren, pair<ll, ll> usek) {
    if (!koren)
        return nullptr;

    if (usek == koren->usek)
        return merge({koren->lavy, koren->pravy});

    if (usek < koren->usek) {
        koren->lavy = erase(koren->lavy, usek);
        update_max(koren);
        return koren;
    }

    koren->pravy = erase(koren->pravy, usek);
    update_max(koren);
    return koren;
}

optional<pair<ll, ll>> find_rooms(Vrchol* koren, ll rooms) {
    if (!koren || koren->maximum < rooms)
        return nullopt;

    auto res = find_rooms(koren->lavy, rooms);
    if (res)
        return res;
    if (koren->usek.second - koren->usek.first >= rooms)
        return koren->usek;
    return find_rooms(koren->pravy, rooms);
}

optional<pair<ll, ll>> find_before(Vrchol* koren, pair<ll, ll> usek) {
    if (!koren)
        return nullopt;

    if (usek.first < koren->usek.second)
        return find_before(koren->lavy, usek);

    if (usek.first == koren->usek.second)
        return koren->usek;

    return find_before(koren->pravy, usek);
}

optional<pair<ll, ll>> find_after(Vrchol* koren, pair<ll, ll> usek) {
    if (!koren)
        return nullopt;

    if (usek.second < koren->usek.first)
        return find_after(koren->lavy, usek);

    if (usek.second == koren->usek.first)
        return koren->usek;

    return find_after(koren->pravy, usek);
}

struct Solver {
    Vrchol* a{};
    vector<pair<ll, ll>> u{};

    Solver(ll n) : a(insert(nullptr, {0, n})) {}

    ll check_in(ll l) {
        auto opt = find_rooms(a, l);
        pair<ll, ll> p = *opt;
        a = erase(a, p);

        pair<ll, ll> o{p.F, p.F + l};
        if (o.S < p.S)
            a = insert(a, {o.S, p.S});

        u.push_back(o);

        return o.F;
    }

    void check_out(ll l) {
        pair<ll, ll> o = u[l];

        auto o_prev = find_before(a, o);
        if (o_prev) {
            o.F = o_prev->F;
            a = erase(a, *o_prev);
        }

        auto o_next = find_after(a, o);
        if (o_next) {
            o.S = o_next->S;
            a = erase(a, *o_next);
        }

        a = insert(a, o);
    }
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, q;
    cin >> n >> q;

    Solver solver(n);
    while (q--) {
        char c;
        ll l;
        cin >> c >> l;

        if (c == 'I') {
            cout << solver.check_in(l) << '\n';
        } else {
            solver.check_out(l);
        }
    }
}

Riešenie intervaláčom:

#include <iostream>
#include <optional>
#include <vector>

#define F first
#define S second

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

bool cmp_size_order(const pll& a, const pll& b) {
    if (a.S - a.F != b.S - b.F)
        return a.S - a.F < b.S - b.F;
    return a > b;
}

class Node {
public:
    Node(ll begin, ll end, ll value)
        : begin_(begin)
        , end_(end)
        , prefix_(gen_prefix(value))
        , suffix_(gen_suffix(value))
        , max_(prefix_)
        , lazy_(value) {}

    pll gen_prefix(ll value) {
        if (value)
            return {begin_, end_};
        return {begin_, begin_};
    }

    pll gen_suffix(ll value) {
        if (value)
            return {begin_, end_};
        return {end_, end_};
    }

    void propagate() {
        if (lazy_) {
            left_->prefix_ = left_->gen_prefix(*lazy_);
            left_->suffix_ = left_->gen_suffix(*lazy_);
            left_->max_ = left_->prefix_;
            left_->lazy_ = lazy_;
            right_->prefix_ = right_->gen_prefix(*lazy_);
            right_->suffix_ = right_->gen_suffix(*lazy_);
            right_->max_ = right_->prefix_;
            right_->lazy_ = lazy_;
            lazy_ = nullopt;
        }
    }

    void set(ll begin, ll end, ll value) {
        if (begin >= end_ || end <= begin_)
            return;
        if (begin <= begin_ && end >= end_) {
            prefix_ = gen_prefix(value);
            suffix_ = gen_suffix(value);
            max_ = prefix_;
            lazy_ = value;
            return;
        }
        if (!left_) {
            ll mid = (begin_ + end_) / 2;
            left_ = new Node(begin_, mid, *lazy_);
            right_ = new Node(mid, end_, *lazy_);
        }
        propagate();
        left_->set(begin, end, value);
        right_->set(begin, end, value);

        prefix_ = left_->prefix_;
        if (prefix_.S == right_->prefix_.F)
            prefix_.S = right_->prefix_.S;

        suffix_ = right_->suffix_;
        if (suffix_.F == left_->suffix_.S)
            suffix_.F = left_->suffix_.F;

        max_ = {left_->suffix_.F, right_->prefix_.S};
        if (cmp_size_order(max_, left_->max_))
            max_ = left_->max_;
        if (cmp_size_order(max_, right_->max_))
            max_ = right_->max_;
    }

    optional<pll> find(ll len) {
        if (max_.S - max_.F < len)
            return nullopt;
        if (!left_) {
            ll mid = (begin_ + end_) / 2;
            left_ = new Node(begin_, mid, *lazy_);
            right_ = new Node(mid, end_, *lazy_);
        }
        propagate();

        auto res = left_->find(len);
        if (res)
            return res;

        if (right_->prefix_.S - left_->suffix_.F >= len)
            return {{left_->suffix_.F, right_->prefix_.S}};

        return right_->find(len);
    }

private:
    Node* left_ = nullptr;
    Node* right_ = nullptr;
    ll begin_;
    ll end_;
    pll prefix_;
    pll suffix_;
    pll max_;
    optional<ll> lazy_;
};

int main(int argc, char** argv) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, q;
    cin >> n >> q;

    Node root(0, n, 1);
    vector<pll> u{};
    while (q--) {
        char c;
        ll l;
        cin >> c >> l;

        if (c == 'I') {
            pll p = *root.find(l);
            pll o = {p.F, p.F + l};
            root.set(o.F, o.S, 0);
            u.push_back(o);

            cout << o.F << '\n';
        } else {
            pll o = u[l];
            root.set(o.F, o.S, 1);
        }
    }
}

Brute-force riešenie:

#include <algorithm>
#include <iostream>
#include <vector>

#define ALL(x) (x).begin(), (x).end()
#define F first
#define S second

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

int main(int argc, char** argv) {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    ll n, q;
    cin >> n >> q;

    vector<pll> a{{0, n}};
    vector<pll> u{};
    while (q--) {
        char c;
        ll l;
        cin >> c >> l;

        if (c == 'I') {
            vector<pll> f;
            copy_if(ALL(a), back_inserter(f), [&l](pll p) {
                return p.S - p.F >= l;
            });
            pll p = *min_element(ALL(f));
            a.erase(remove(ALL(a), p), a.end());

            pll o{p.F, p.F + l};
            if (o.S < p.S)
                a.push_back({o.S, p.S});

            u.push_back(o);

            cout << o.F << '\n';
        } else {
            pll o = u[l];

            auto o_prev = find_if(ALL(a), [&o](pll p) {
                return p.S == o.F;
            });
            if (o_prev != a.end()) {
                o.F = o_prev->F;
                a.erase(o_prev);
            }
            
            auto o_next = find_if(ALL(a), [&o](pll p) {
                return p.F == o.S;
            });
            if (o_next != a.end()) {
                o.S = o_next->S;
                a.erase(o_next);
            }

            a.push_back(o);
        }
    }
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.

8. Abnormálne Veľký Hotel vzorové riešenie