7. Kto Spasí Pochúťku vzorové riešenie

9 1
14 -2 2 4 6 8 10 12 16
1 5 1 1 1 5 1 1 4

4

2 5
5 100
2 2

Torta nebude

Ako prvé, poďme si úlohu trochu učesať. Na prvé prečítanie úloha môže vyzerať trochu desivo, ale na druhé prečítanie už skúsenejší riešiteľ všimne, že úloha je o hľadaní najkratšej cesty v grafe.

Vrcholy v tomto prípade sú vedúci a T2, a medzi vedúcimi A a B je hrana, ak si vedia medzi sebou premeniť tortu a hrana medzi vedúcim a T2 je ak vedúci vie doniesť tortu do T2. V tomto grafe je následne úloha nájsť najkratšiu cestu medzi Timkou a T2, alebo rozhodnúť, že žiadna cesta neexistuje.

Ako na to?

Máme celý graf

Riešenie, ktoré nám prirodzene napadne je vygenerovať si celý graf, a následne na ňom zbehnúť náš obľúbený rýchly algoritmus na hľadanie najkratších ciest v grafoch – BFS.

Ako vygenerujeme graf? Pre každú dvojicu vedúcich stačí skontrolovať, či minimum ich dosahov je aspoň vzdiaľenosť do polcesty medzi nimi. Takto vieme postaviť graf v čase \(O(N^2)\) a následne v lineárnom čase vo veľkosti grafu spustiť BFS. Graf však môže mať tiež veľkosť najviac \(O(N^2)\) – v prípade, že sú všetci vedúci ochotný ísť ďaleko.

Ak niečo ďalej nezlepšíme, dostaneme kvadratické riešenie, ktoré nám dá 4 body. Toto riešenie vieme implementovať aj v lineárnej pamäti (napríklad si graf konštruujeme postupne, a nepamätáme si všetky hrany naraz).

Malé grafy

BFS vieme robiť v čase lineárnom od veľkosti grafu. Ak je graf reprezentovaný v zadaní malý, keby sme ho vedeli rýchlo zkonštruovať, vieme ho aj rýchlo prehľadať.

Predstavme si, že máme vedúcich v zadaní utriedených podľa pozície. \(i\)-ty vedúci, stojaci na pozícii \(x_i\), ochotný prejsť \(d_i\) si vie tortu potenciálne vymeniť iba s vedúcimi na pozíciách medzi \(x_i - 2d_i\) a \(x_i + 2d_i\).

Mohli by sme si preto napríklad spraviť nasledovné: utrieďme si vedúcich podľa pozície. Keď sa v BFS dostaneme k vedúcemu číslo \(i\), začneme si pole prechádzať (do oboch strán) kým neprídeme k vedúcemu nachádzajúcemu sa mimo intervalu, kde \(i\)-ty vedúci vie potenciálne tortu vymeniť. Pre každého vedúceho v intervale si už vieme overiť existenciu hrany v konštantnom čase.

Takto \(i\)-teho vedúceho v BFS spracujeme v čase \(O(d_i)\), takže dokopy dostaneme časovú zložitosť \(O(n \max_i d_i+ n\log n)\) (\(O(n\log n)\) je preto, lebo musíme triediť). Pamäťovú zložitosť vieme stále mať lineárnu, keďže zostrojený graf nedržíme v pamäti. Takéto riešenie nám dá \(6\) bodov.

Kde je to pomalé?

Problém je, že vo všeobecnosti môžu byť jednotlivé \(d_i\) veľké, takže aj počet hrán v grafe príliš veľký, aby sme sa na ne pozreli. Všimnime si, že keď už v BFS pridáme vrchol do fronty (alebo už spracujeme), tak keď sa pri spracovávaní iných vrcholov pozeráme na hrany idúce do tohto vrcholu, je to zbytočné, pretože tento vrchol už druhý krát nebudeme pridávať do fronty (a teda druhý krát spracovávať).

Mohli by sme si vrchol z grafu po jeho prvotnom pridaní do grafu vymazať aby sme sa tomuto vyhli? Na prvý pohľad to neznie sľubne, keďže nevieme rozumne efektívne vymazávať elementy zo stredu poľa.

Problém je ale aj to, že keby sme aj vedeli, stále sa nám môže stať, že väčšina vedúcich ku ktorým je \(i\)-ty vedúci nablízku sú príliš leniví aby si ním vymenili tortu. Takže by sme potrebovali vymyslieť spôsob akým sa nepozerať na príliš veľa neexistujúcich hrán.

Mohli by sme to vyriešiť použitím vhodnej dátovej štruktúry?

Meníme pole za intervaláč

Najskôr sa pozrime na druhý problém. Kedy si dvaja vedúci \(i\) a \(j\) vedia vymeniť tortu? Keď je rozdiel ich vzdialeností najviac \(2\min(d_i, d_j)\), inak povedané (BUNV \(x_i < x_j\)) ak \(x_j \leq x_i + 2d_i\) a zároveň \(x_i \geq x_j - 2d_j\).

Predstavme si, že by sme vedeli spraviť nasledovné: pre všetkých vedúcich stojacich medzi \(x_i\) a \(x_i +2d_i\), pozrime sa na takého vedúceho \(j\) pre ktorého je \(x_j - 2d_j\) čo najmenšie. Ak \(x_j - 2d_j > x_i\), potom ani žiadny ostatní vedúci v napravo od \(i\)-tého vedúceho si s ním môžu vymeniť tortu (ak sú príliš ďaleko od \(i\)-teho vedúceho, ten im nie je ochotný predať tortu; všetci vedúci v dosahu \(i\)-teho vedúceho ale majú \(x_{j^\prime}-2d_{j^\prime} > x_j - 2d_j > x_j\), teda nie sú ochotní chodiť až ku vedúcemu \(i\)). Podobne vieme pre vedúcich naľavo od vedúceho \(i\) hľadať zase blízkeho vedúceho \(j\) s najvyšším \(x_j + 2d_j\).

Hľadanie maxím a miním v intervale znie ako práca pre intervalový strom¹.

Ten má aj výhodu, že v ňom vieme rýchlo (v \(O(\log n)\)) updatovať dáta.

Mohli by sme preto spraviť nasledovné: majme dva intervalové stromy. Minimový s hodnotami \(x_j - 2d_j\), a maximový s hodnotami \(x_j + 2d_j\).

Vždy keď spracovávame vedúceho \(i\) v BFS, pozrieme sa na vedúcich v dosiahnuteľnom intervale naľavo v maximovom intervaláči. Nech \(j\) je iný vedúci s najvyššou hodnotou \(x_j + 2d_j\) nachádzajúci sa na pozíciach medzi \(x_i - 2d_i\) a \(x_i\). Potom, ak si s ním nevieme predať tortu, skončili sme – žiadny iný dosiahnuteľný vedúci napravo od \(i\)-teho vedúceho si s ním tortu nevymení. Ak sme ale naďabili na hranu, potom môžme pokračovať.

Aby sme sa ale vyhli spracovaniu nájdeného vedúceho neskôr v BFS (ako sme si všimli hore, to robí problémy), vymažeme ho zo stromov. Vymazať pozíciu v strede intervalového stromu na prvý pohľad znie ako pomalé, avšak namiesto vymazania môžeme nastaviť pozíciu vedúcemu v minimovom strome na \(-\infty\) a v maximovom strome na \(+\infty\) (kde nekonečno je nejaké dostatočne veľké číslo), takže keby sme ho našli ako minimum/maximum tak hľadania vždy ukončíme (keďže to znamená, že žiadny nespracovaný/nevidený vedúci intervale nie je).

Keď \(j\)-teho vedúceho týmto spôsobom vyhodíme zo stromu, môžme pokračovať hľadanie vedúcich ktorým možno odovzdať tortu, až kým nám buď dôjdu vedúci, alebo všetci vedúci v intervale sú príliš lenivý vymeniť si tortu s \(i\)-tym vedúcim.

Následne toto isté opakujeme pre dosiahnuteľných vedúcich napravo od \(i\)-teho, pomocou minimového intervaláča.

Každého vedúceho spracujeme najviac raz, a dokopy sa cez intervaláče pozrieme na najviac \(O(n)\) možných hrán (najviac \(n\) hrán ktorými sa v BFS vyberieme, a pre každý vrchol sa pozrieme na najviac dve počet neexistujúce hrany resp. hrany do už navštíveného vrchola). Každá otázka, alebo update do intervaláča má časovú zložitosť \(O(\log n)\), takže časová zložitosť tohto algoritmu je \(O(n\log n)\). Intervaláč vieme postaviť v pamäti \(O(n)\), takže aj celý algoritmus vieme implementovať v lineárnej pamäti.

Technické detaily

Zabudli sme spomenúť dve veci: T2, a ako sa v intervaláči pozrieť na interval vedúcich na nejakom intervale pozícií.

Začnime tým jednoduchším: T2. Potom, ako sme spočítali vzdialenosti od Timky pre všetkých vedúcich vieme spočítať minimálnu vzdialenosť do T2 jednoducho: v konštantnom čae sa pre každého vedúceho spýtame, či vie dostiahnuť T2, a to tak, že nájdeme vedúceho s minimálnou vzdialenosťou od Timky ktorý vie tortu dostať do T2.

Čo s druhým problémom? Jedno z riešení je použiť kompresiu súradníc: dať v intervalom strome vedúcich v utriedenom poradí podľa ich pozície, a pomocou utriedenej množiny (kde si uskladníme dvojice (pozícia, relatívna pozícia)) zistiť ktoré relatívne pozície pripadajú ku danému intervalu pozícií.

Druhé riešenie je mať súradnice priamo v intervaláčoch: majme vedúcich vložených do intervaláča podľa ich utriedených pozícií, ale priamo v intervaláči si zapamätajme aj súradnice. Potom v každom vrchole si môžeme navyše pamätať minimálnu a maximálnu pozíciu v listoch patriacich pod vrchol. Takto sa môžeme intervaláč pýtať priamo na interval pozícií, bez toho aby sme museli riešiť navyše kompresiu súradníc.

Žiadne z týchto dvoch riešení nezhoršuje časovú zložitosť celkového riešenia.

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define FOB(i,n)	for(int i=n;i>=1;i--)
#define MP(x,y)	make_pair((x),(y))
#define ii pair<int, int>
#define lli long long int
#define ld long double
#define ulli unsigned long long int
#define lili pair<lli, lli>
#ifdef EBUG
#define DBG	if(1)
#else
#define DBG	if(0)
#endif
#define SIZE(x) int(x.size())
const int infinity = 2000000999;
const long long int inff = 4000000000000000999;

typedef complex<long double> point;

template<class T>
T get() {
    T a;
    cin >> a;
    return a;
}

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {
    out << "[" << par.first << ";" << par.second << "]";
    return out;
}

template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    out << "}";
    return out;
}

template <class T, class U>
ostream& operator<<(ostream& out, const map<T,U> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    
    out << "}"; return out;
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  FOR(i, v.size()){
    if(i) out << " ";
    out << v[i];
  }
  out << endl;
  return out;
}

bool ccw(point p, point a, point b) {
    if((conj(a - p) * (b - p)).imag() <= 0) return false;
    else return true;
}

struct intervalac {
    int N;
    vector<ii> miniL, maxiR;
    vector<int> minD, maxD;
    vector<int> start, range;
    
    intervalac(int n, vector<int> &d, vector<int> &pos) {
        N = pow(2, (ceil(log2(n))));
        
        miniL.resize(2 * N, {infinity, -1});
        maxiR.resize(2 * N, {-infinity, -1});
        minD.resize(2 * N, infinity);
        maxD.resize(2 * N, infinity);
        
        range.resize(2 * N, N);
        start.resize(2 * N, 0);
        
        for (int i = 2; i < 2 * N; i ++) {
            range[i] = range[i / 2] / 2;
            start[i] = start[i / 2] + (i % 2 ? range[i] : 0);
        }
        
        for (int i = N + n - 1; i > 0; i --) {
            if (i >= N) {
                miniL[i] = {pos[i - N] - 2 * d[i - N], i - N};
                maxiR[i] = {2 * d[i - N] + pos[i - N], i - N};
                minD[i] = pos[i - N];
                maxD[i] = pos[i - N];
            }
            else {
                miniL[i] = (miniL[i * 2].first > miniL[i * 2 + 1].first ? miniL[i * 2 + 1] : miniL[i * 2]);
                maxiR[i] = (maxiR[i * 2].first > maxiR[i * 2 + 1].first ? maxiR[i * 2] : maxiR[i * 2 + 1]);
                minD[i] = min(minD[i * 2], minD[i * 2 + 1]);
                maxD[i] = max(maxD[i * 2], maxD[i * 2 + 1]);
            }
        }
        
//         DBG cout << "minD:" << minD << "maxD: " << maxD;
    }
    
    ii query_upd_mini(int l, int r, int id) {
//         DBG cout << "In query_upd_mini(l = " << l << ", r = " << r << ", id = " << id << "), interval [" << minD[id] << ", " << maxD[id] << "] maxR = " << maxiR[id] << endl;
        if (l > maxD[id] || r < minD[id]) return {infinity, -1};
        if (l <= minD[id] && r >= maxD[id]) return miniL[id];
        
        ii resF = query_upd_mini(l, r, id * 2), resS = query_upd_mini(l, r, id * 2 + 1);
        ii res = min(resF, resS);
        return res;
    }
    
    ii query_upd_maxi(int l, int r, int id) {
        if (l > maxD[id] || r < minD[id]) return {-infinity, -1};
        if (l <= minD[id] && r >= maxD[id]) return maxiR[id];
        ii resF = query_upd_maxi(l, r, id * 2), resS = query_upd_maxi(l, r, id * 2 + 1);
        ii res = max(resF, resS);
        return res;
    }
    
    void update_to_none(int pos, int id) {
//         DBG cout << pos << " <- infinity " << endl;
        if (pos < start[id] || pos >= start[id] + range[id]) return;
        if (range[id] == 1) {
            maxiR[id] = {-infinity, -1};
            miniL[id] = {infinity, -1};
            return;
        }
        update_to_none(pos, id * 2 + 1);
        update_to_none(pos, id * 2);
        miniL[id] = min(miniL[id * 2], miniL[id * 2 + 1]);
        maxiR[id] = max(maxiR[id * 2], maxiR[id * 2 + 1]);
    }
};



int main() {
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);
    
    int n = get<int>();
    int D = get<int>();
    
    vector<ii> pos;
    vector<int> d;
    FOR(i, n) pos.push_back({get<int>(), i});
    FOR(i, n) d.push_back(get<int>());
    
    sort(pos.begin(), pos.end());
    
    vector<int> sorted_pos, sorted_d;
    int timka = -1;
    FOR(i, n) {
        if (pos[i].second == 0) timka = i;
        sorted_pos.push_back(pos[i].first);
        sorted_d.push_back(d[pos[i].second]);
    }
    
    DBG cout << pos;
    
    DBG cout << "Going to build segment tree,\n" << sorted_pos << sorted_d;
    
    intervalac I(n, sorted_d, sorted_pos);
    vector<int> dist(n, infinity);
    
    DBG cout << "timka = " << timka << " n = " << n << endl;
    
    dist[timka] = 0;
    queue<int> Q;
    Q.push(timka);
    I.update_to_none(timka, 1);
    
    // BFS
    
    while (Q.size()) {
        int v = Q.front();
        DBG cout << "v = " << v << " queue size: " << Q.size() << endl;
        Q.pop();
        
        int l = sorted_pos[v] - 2 * sorted_d[v];
        int r = sorted_pos[v] + 2 * sorted_d[v];
        
        while (true) {
            ii zlava = I.query_upd_maxi(l, sorted_pos[v], 1);
            DBG cout << "zlava: " << zlava << endl;
            
            if (zlava.second >= 0 && 2 * min(sorted_d[v], sorted_d[zlava.second]) >= abs(sorted_pos[v] - sorted_pos[zlava.second])) {
                I.update_to_none(zlava.second, 1);
                if (dist[zlava.second] != infinity) {
                    DBG cout << "ALERT FOR " << zlava << endl;
                }
                dist[zlava.second] = dist[v] + 1;
                Q.push(zlava.second);
                continue;
            }
            
            ii zprava = I.query_upd_mini(sorted_pos[v], r, 1);
            
            DBG cout << "zprava: " << zprava << " pos is " << sorted_pos[zprava.second] << " di = " << sorted_d[zprava.second] << " dv = " << sorted_d[v] << " and pos " << sorted_pos[v] << endl;
            
            if (zprava.second >= 0 && 2 * min(sorted_d[v], sorted_d[zprava.second]) >= abs(sorted_pos[v] - sorted_pos[zprava.second])) {
                I.update_to_none(zprava.second, 1);
                if (dist[zprava.second] != infinity) DBG cout << "ALERT! Zprava " << zprava << endl;
                dist[zprava.second] = dist[v] + 1;
                Q.push(zprava.second);
                continue;
            }
            
            break;
        }
    }
    
    int mindistance = infinity;
    
    DBG cout << "   dists: " << dist;
    
    FOR(i, n) {
        if (2 * min(D, sorted_d[i]) >= abs(sorted_pos[i])) {
            mindistance = min(mindistance, 1 + dist[i]);
        }
    }
    
    if (mindistance < infinity) cout << mindistance << endl;
    else cout << "Torta nebude" << endl;
    
}