24ος ΠΔΠ Γ' Φάση: Σουβλάκια (souvlakia) - Λύση

Επεξήγηση εκφώνησης

Το πρόβλημα αναλύεται σε δυο μέρη, το εισαγωγικό και το κυρίως πρόβλημα.

Εισαγωγικό πρόβλημα: Μας δίνεται γράφος με \(N\) κόμβους (καταστήματα) και για κάθε κατάστημα \(s_i\), ζητείται να υπολογίσουμε τρείς τιμές \((x_i,y_i,z_i)\) ως τις αποστάσεις των διαδρομών από το κατάστημα \(s_i\) προς τρία άλλα προεπιλεγμένα καταστήματα. Εφόσον δεν υπάρχουν αρνητικά βάρη στις ακμές, είναι ευνόητο ότι με τη χρήση του greedy αλγορίθμου εύρεσης καλύτερης διαδρομής του Dijkstra, θα μπορέσουμε να βρούμε τις αποστάσεις αυτές. Οι τιμές των αποστάσεων αυτών \(x,y,z \in [0, D \cdot N]\), όπου \(D = 2 \cdot 10^4\) το μέγιστο βάρος κάθε ακμής.
Το διάστημα τιμών προκύπτει αν αναλογιστούμε ότι για ένα από τα προεπιλεγμένα καταστήματα η απόσταση από τον εαυτό του είναι \(0\) (ελάχιστη τιμή) και μια διαδρομή μπορεί να έχει έως \(N\) καταστήματα, οπότε ως μέγιστη απόσταση έχουμε την τιμή \(D \cdot N\). Εκτελούμε τρεις φορές τον αλγόριθμο του Dijkstra (μία φορά για το κάθε προεπιλεγμένο κατάστημα), υπολογίζοντας τις αποστάσεις κάθε καταστήματος από τα τρία προεπιλεγμένα. Τώρα που υπολογίσαμε τις τρείς αποστάσεις για κάθε κατάστημα, συνεχίσουμε στο κυρίως πρόβλημα μας του οποίου η επεξήγηση ακολουθεί.

Κυρίως πρόβλημα: Μας δίνεται ένας πίνακας με \(N\) triplets (τριάδες) μη αρνητικών ακεραίων (οι αποστάσεις από τα τρία καταστήματα), έστω \((x,y,z)\). Ζητούμενο είναι να μπορούμε να απαντήσουμε σε queries της μορφής: για το κατάστημα \(s_i\) με τριάδα \((x_i,y_i,z_i)\), υπάρχει τουλάχιστο ένα άλλο κατάστημα \(s_j\) με τριάδα \((x_j,y_j,z_j)\) και να ισχύουν ταυτόχρονα οι ανισότητες \(x_j\lt x_i, y_j\lt y_i, z_j\lt z_i\)
Αν υπάρχει τέτοιο κατάστημα, τότε το κατάστημα \(s_i\) δεν είναι επιλέξιμο και η απάντηση που πρέπει να τυπώσουμε είναι “NO”, αλλιώς είναι “YES”.

Στη συνέχεια θα δωθούν με τη σειρά διαφορετικές λύσεις με σκοπό να μεταβούμε ομαλά από την εύκολη και μη αποδεκτή λύση (brute force), σε λύσεις με segment tree και binary indexed tree, implicit segment tree, coordinate compression + binary indexed tree μέχρι την τελική optimal λύση.

Λύση Brute Force \(\mathcal{O}(N^2)\)

Δοκιμάζουμε για κάθε κατάστημα \(s_i\) από τα \(N\) αν υπάρχει κάποιο άλλο \(j\) που να έχει \(x_j\lt x_i\) και \(y_j\lt y_i\) και \(z_j\lt z_i\). Συνολική πολυπλοκότητα \(\mathcal{O}(N^2)\). Η λύση αυτή περνά τα 8 από τα 11 test cases. Πολυπλοκότητα Dijkstra \(\mathcal{O}((N+M)\cdot \log {N})\) και απαντήσεων ερωτημάτων \(\mathcal{O}(N^2)\). Η συνολική πολυπλοκότητα περιορίζεται από τον χειρότερο όρο άρα είναι της τάξης \(\mathcal{O}(N^2)\). Παρακάτω δίνεται μία ενδεικτική υλοποίηση αυτής της λύσης.

#include <cstdio>
#include <algorithm>
#include <climits>
#include <cassert>
#include <vector>
#include <list>
#include <cstring>
#include <cmath>
#include <set>
#include <map>

using namespace std;

const long 
    MAXN = int32_t(1e5),//μέγιστος αριθμός shops
    MAXQ = int32_t(5e4),//μέγιστος αριθμός queries
    INF  = INT32_MAX;  //INF for dijkstra
    
long N,M,Q,C[3];

struct shop {
#define X  d[0]
#define Y  d[1]
#define Z  d[2]
    long d[3];//triplet αποστάεων (X,Y,Z)
    shop(){ X=Y=Z=INF; }//αρχική τιμή για dijsktra
} S[MAXN+1];

void dijsktra(long src,int dupd,vector<vector<pair<long,long>>>& edge){
    //src είναι το τρέχον προεπιλεγμένο κατάστημα
    //dupd είναι η θέση στον πίνακα Shop[*].d[dupd] που θα ενημερωθεί
    set<pair<long,long>> DS;//<distance,shopid> χρήση σαν priority queue
    
    DS.insert({0,src});
    S[src].d[dupd] = 0;
    
    while(!DS.empty()){//explore
        auto x = *(DS.begin());//head της priority queue
        DS.erase(DS.begin());
        long daddy = x.second;
        for(auto y : edge[daddy]){
            long child = y.first, dist = y.second;
            if(S[daddy].d[dupd]!=INF && S[child].d[dupd] > S[daddy].d[dupd] + dist){
                //this is an improvement
                if(S[child].d[dupd]!=INF)//αν υπήρχε στην "queue" διαγραψέ το
                    DS.erase(DS.find({S[child].d[dupd],child}));
                S[child].d[dupd] = S[daddy].d[dupd] + dist;
                DS.insert({S[child].d[dupd],child});
            }
        }
    }
}

int main(){
#ifdef CONTEST
    freopen("souvlakia.in", "r",stdin);
    freopen("souvlakia.out","w",stdout);
#endif
    scanf("%ld%ld",&N,&M);
    
    {//το vector παρακάτω δεσμεύει μνήμη μέχρι το κλείσιμο αυτού του bracket
        //δηλαδή 400.000 * 2 * 3 * sizeof(long) = 2.400.000 * sizeof(long)
        vector<vector<pair<long,long>>> edge(N+1);//<edge_to, distance>
        for(long a,b,d,i=0;i<M;++i){
            scanf("%ld%ld%ld",&a,&b,&d);
            edge[a].push_back({b,d});
            edge[b].push_back({a,d});
        }
        scanf("%ld%ld%ld%ld",&C[0],&C[1],&C[2],&Q);

        for(int i=0;i<3;++i)
            dijsktra(C[i],i,edge);
    }//η μνήμη του vector απελευθερώθηκε (destructor called)

    for(long q,i=0;i<Q;++i){
        scanf("%ld",&q);
        bool capable = true;
        for(long i=1;i<=N;i++){
            if(i == q)continue;
            if(S[i].X<S[q].X && S[i].Y<S[q].Y && S[i].Z<S[q].Z){
                capable = false;
                break;
            }
        }    
        printf(capable?"YES\n":"NO\n");
    }
    return 0;
}

Λύση με Segment Tree και RMQ - \(\mathcal{O}(N \cdot \log {(D \cdot N)})\)

Γνώσεις που θα χρειαστούμε: Segment Tree, RMQ

Η δυσκολία που παρουσιάζει το πρόβλημα είναι ότι έχουμε τρείς διαφορετικές συνθήκες ανεξάρτητες μεταξύ τους. Τη μια συνθήκη θα την αφαιρέσουμε εύκολα αν φροντίσουμε να έχουμε τελειώσει με όλα τα καταστήματα που είναι δυνατόν να καταστήσουν μη επιλέξιμο (ακυρώσουν) ένα κατάστημα \(s_i\) πριν φτάσουμε να επεξεργαστούμε το \(i\). Για το σκοπό αυτό αρκεί να ταξινομήσουμε σε αύξουσα σειρά τα καταστήματα ως προς την πρώτη τιμή, οπότε όταν θα φτάνουμε στο κατάστημα με \(x_i\) θα έχουμε τελειώσει με όλα τα καταστήματα \(j\) με \(x_j \lt x_i\)¹. Όσα καταστήματα βρίσκονται μετά από το \(s_i\) δεν το επηρεάζουν, διότι δεν έχουν μικρότερο \(x\).
Αυτό βέβαια αυτομάτως σημαίνει ότι δεν μπορούμε να απαντήσουμε τα queries με τη σειρά που μας δίνονται και θα πρέπει να τα προϋπολογίσουμε με τη σειρά που μας βολεύει και να τα απαντήσουμε αργότερα, δηλαδή offline.

Για το \(y_i\) του καταστήματος \(s_i\) θέλουμε να ξέρουμε αν υπάρχει ένα τουλάχιστο κατάστημα \(s_j\) με \(y_j \lt y_i\) και \(z_j \lt z_i\). Ας δούμε το παρακάτω σχήμα όπου το κατάστημα \(s_i(y_i,z_i)\) ακυρώνεται αν υπάρχει έστω και ένα κατάστημα στη γραμμοσκιασμένη περιοχή ².

Παρατηρήστε ότι τα πράσινα σημεία δεν επηρεάζουν το κατάστημα \(s_i\) ενώ το κόκκινο σημείο το ακυρώνει.
Ο έλεγχος της επιλεξιμότητας ενός καταστήματος \((y_i,z_i)\) γίνεται ως εξής: έστω \(z_{min}\) το μικρότερο \(z\) όλων των καταστημάτων που έχουν \(y\le y_i-1\), αν \(z_{min} \lt z_i\), τότε υπάρχει κάποιο κατάστημα στη γραμμοσκιασμένη περιοχή και το κατάστημα \(s_i\) ακυρώνεται (η απάντηση είναι “NO”), αλλιώς η απάντηση είναι “YES”. Η δομή που απαντά τέτοια ερωτήματα λέγεται range minimum query³ και θα τη συμβολίζουμε ώς μια συνάρτηση \(\mathit{RMQ}(Y)\). Στο παραπάνω σχήμα το \(\mathit{RMQ} (y_i-1)\) θα έδεινε το \(z\) του κόκκινου σημείου.

Ας παρατηρήσουμε πως λειτουργεί η range minimum query με το παρακάτω σχήμα αφού έχουν γίνει οι απαραίτητες ενημερώσεις του από τα καταστήματα \(s_1\) έως και \(s_7\) ²

Μια υλοποίηση του RMQ, γίνεται με segment tree. Η προσπέλαση των καταστημάτων γίνεται κατά ομάδες. Ως ομάδα θεωρούνται τα καταστήματα με ίδιο \(x\)⁴. Καθώς τελειώσουμε με τον έλεγχο των καταστημάτων κάθε ομάδας, κάνουμε την ανάλογη ενημέρωση στη δομή μας με τα νέα ζεύγη \((y_i,z_i)\) ώστε να ετοιμάσουμε τη δομή μας για τον έλεγχο των επόμενων ομάδων.

Η λύση αυτή ενώ χρονικά είναι ικανοποιητική, δεν περνά τα αυστηρά όρια μνήμης του προβλήματος ακόμα και αν επαναχρησιμοποιήσουμε τη μνήμη που δεν χρειάζεται πλέον⁵ καθώς απαιτεί μνήμη της τάξης \(\mathcal{O}(D\cdot N)\)⁶ για το segment tree με πεδίο ορισμού \(D\cdot N\) τιμών.

Μία ενδεικτική λύση με segment tree ακολουθεί, χωρισμένη σε τρία τμήματα:

Τμήμα 1^o: Περιέχει σταθερές, το τμήμα του Dijkstra⁷ και μερικές βοηθητικές συναρτήσεις για γρήγορη είσοδο/έξοδο στα αρχεία.⁸

#ifdef CONTEST
    #define NDEBUG    //disable assert() checks
#endif

#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstdint>
#include <cassert>
#include <vector>
#include <list>
#include <cstring>
#include <cmath>
#include <set>

using namespace std;

const int32_t 
    MAXN = int32_t(1e5),//μέγιστος αριθμός shops
    MAXQ = int32_t(5e4),//μέγιστος αριθμός queries
    INF  = INT32_MAX;  //INF for dijkstra

int32_t    N,M,Q,C[3];

struct shop {
#define X  d[0]
#define Y  d[1]
#define Z  d[2]
    int32_t d[3];//Οι 3 αποστάσεις (X,Y,Z)
    list<int32_t> queryid;//ερωτήματα που αφορούν το κατάστημα
            //χρήση λίστας διότι μπορεί να υπάρχουν περισσότερα ερωτήματα για το κατάστημα
    shop(){ X=Y=Z=INF; }//αρχικές τιμές για dijsktra
    bool operator <(const shop& b) const { 
        return X < b.X;
    }
} S[MAXN+1];

void dijsktra(int32_t src,int dupd,vector<vector<pair<int32_t,int32_t>>>& edge){
    //src είναι ένα από τα 3 καταστήματα
    //dupd είναι η θέση στον πίνακα Shop[*].d[dupd] που ενημερώνουμε
    set<pair<int32_t,int32_t>> DS;//<distance,shopid>
    
    DS.insert({0,src});
    S[src].d[dupd] = 0;
    
    while(!DS.empty()){//εξερεύνησε
        auto x = *(DS.begin());
        DS.erase(DS.begin());
        int32_t daddy = x.second;
        for(auto y : edge[daddy]){//επέκτεινε
            int32_t child = y.first, dist = y.second;
            if(S[daddy].d[dupd]!=INF && S[child].d[dupd] > S[daddy].d[dupd] + dist){
                if(S[child].d[dupd]!=INF)
                    DS.erase(DS.find({S[child].d[dupd],child}));
                S[child].d[dupd] = S[daddy].d[dupd] + dist;
                DS.insert({S[child].d[dupd],child});
            }
        }
    }
}

inline int32_t read_fast(){//γρήγορη είσοδος/έξοδος από τα αρχεία in/out
    int32_t x = 0;
    char c;
    while((c=getchar_unlocked())<'0');//αγνόησε κενά, CR, LF
    do
        x = x*10 + (c-'0');
    while((c=getchar_unlocked())>='0');
    return x;
}

inline void write_fast(bool f){
    const char *s = f ? "YES\n":"NO\n";
    while(*s)
        putchar_unlocked(*s++);
}

Τμήμα 2^o: Η δομή RMQ με χρήση segment tree ⁹

//RMQ με χρήση segment tree
int32_t YMAX = 1;   //μέγιστη τιμή y
int32_t *Zrmq;      //segment tree (RangeMinQuery)for Z
void sinit(){       //δέσμευσε μνήμη και αρχικοποίησε σε (σχεδόν) άπειρο
    for(int32_t i=1;i<=N;++i)
        YMAX = max(YMAX, S[i].Y);
    size_t Zrmqsize = 1 << size_t(ceil(log2(YMAX+1))+1);
    Zrmq = new int32_t[Zrmqsize];
    memset(Zrmq,0x7f,sizeof(*Zrmq) * Zrmqsize);
}

int32_t squery(int32_t yright,int32_t si=0,int32_t ss=0,int32_t se=-1){
    //βρές το z min για τα y στο [0,yright]
    if(se==-1) 
        se = YMAX;
    if(yright<ss || yright<0)
        return INF;//δεν συμμετέχει
    if(se<=yright) 
        return Zrmq[si];//συμμετέχει πλήρως
    int32_t mid = (ss+se)/2;
    return min(
        squery(yright, si*2+1,ss,mid),
        squery(yright, si*2+2,mid+1,se)
    );
}

void supdate(int32_t y,int32_t z,int32_t si=0,int32_t ss=0,int32_t se=-1){
    if(se==-1) 
        se = YMAX;
    if(y<ss || se<y)
        return;//δεν συμμετέχει
    if(ss==se){
        Zrmq[si] = min(Zrmq[si],z);
    }else {
        int32_t mid = (ss+se)/2;
        if(y<=mid) 
            supdate(y,z,si*2+1,ss,mid);
        else
            supdate(y,z,si*2+2,mid+1,se);
        Zrmq[si] = min(Zrmq[si*2+1],Zrmq[si*2+2]);
    }
}
//RMQ

Τμήμα 3^o: Η main με την κύρια λειτουργία του προγράμματος (i/o, sort, solve, answer)

int main(){
#ifdef CONTEST
    freopen("souvlakia.in", "r",stdin);
    freopen("souvlakia.out","w",stdout);
#endif
    N = read_fast(), M = read_fast();
    
    {//χρησιμοποίησε ένα προσωρινό vector για τα edges 
        vector<vector<pair<int32_t,int32_t>>> edge(N+1);//<edge_to, distance>
        for(int32_t a,b,d,i=0;i<M;++i){
            a = read_fast(), b = read_fast(), d = read_fast();
            edge[a].push_back({b,d});
            edge[b].push_back({a,d});
        }
        for(int i=0;i<3;i++)
            C[i] = read_fast();
        Q = read_fast();

        for(int i=0;i<3;++i)
            dijsktra(C[i],i,edge);
    }//η μνήμη του vector ελευθερώθηκε 

    //αποθήκευσε τα queries για offline απαντήσεις
    for(int32_t i=0;i<Q;++i)
        S[read_fast()].queryid.push_back(i);//shop[q] πρέπει να απαντήσει το i-th query

    sort(S+1,S+N+1);

    vector<bool> ans(MAXQ+1,false);        //offline answers

    sinit();//δημιούργησε το RMQ
    for(int32_t right = 1, left = 1; left <=N;){
        while(right<=N && S[right].X == S[left].X){
            //έλεγξε την ομάδα καταστημάτων με ίδιο x
            const shop& s = S[right];
            bool capable = (squery(s.Y-1) >= s.Z);
            
            for(auto e:s.queryid)
                ans[e] = capable;
            right++;
        }
        while(left<right){//ενημέρωσε το RMQ
            supdate(S[left].Y, S[left].Z);
            left++;
        }
    }
    
    for(int32_t i=0;i<Q;++i)
        write_fast(ans[i]);
    
    return 0;
}

Η επιλογή να κοπεί το πρόγραμμα σε τρία τμήματα έγινε γιατί στη συνέχεια θα δούμε τις εναλλακτικές μορφές της δομής μας αλλάζοντας μόνο το δεύτερο τμήμα και κρατώντας το πρώτο και τρίτο ως έχουν.

Λύση με BIT και prefix minimum - \(\mathcal{O}(N \cdot \log {(D \cdot N)})\)

Γνώσεις που θα χρειαστούμε: Binary Indexed Tree

To binary indexed tree είναι λίγο οικονομικότερο σε μνήμη (παρόλο που και αυτό είναι της τάξης \(\mathcal{O}(D\cdot N)\)) σε σχέση με το segment tree, αλλά και πάλι ξεπερνά τα αποδεκτά όρια μνήμης του προβλήματος. Το μειονέκτημα του είναι ότι δεν είναι τόσο γενική χρήσης, δεν έχει δηλαδή τόσο ευρύ πεδίο εφαρμογών, όπως το segment tree και γενικά υπολογίζει από την αρχή (ή το τέλος) έως το σημείο του query άρα είναι κατάλληλο για υπολογισμούς prefix ή suffix τιμών υπό προϋποθέσεις.

Μια ενδεικτική λύση έχουμε αντικαθιστώντας το τμήμα 2 του παραπάνω κώδικα με το παρακάτω απόσπασμα:

//RMQ με χρήση Binary Indexed Tree
int32_t *BIT;
int32_t YMAX = 1; //αριθμός διαφορετικών τιμων Y καταστηματων
void sinit(){
    for(int i=1;i<=N;i++)
        if(YMAX<S[i].Y)
	    YMAX = S[i].Y;
    YMAX += 3;//offset για να ξεκινα το αριστερο όριο του ΒΙΤ απο -1
    BIT = new int32_t[YMAX+1];
    memset(BIT,0x7f,sizeof(*BIT)*(YMAX+1));
}
int32_t squery(int32_t y){
    int32_t ymin = BIT[0];
    y+=2;
    while(y>0){
        ymin = min(ymin,BIT[y]);
        y -= y & -y;
    }
    return ymin;
}
void supdate(int32_t y,int32_t z){
    y+=2;
    while(y<=YMAX){
        BIT[y] = min(BIT[y],z);
        y += y & -y;
    }
}

Λύση με Implicit Segment Tree - \(\mathcal{O}(N \cdot \log(D\cdot N))\)

Γνώσεις που θα χρειαστούμε: Implicit Segment Tree

Στην προηγούμενη λύση παρόλο που έχουμε ένα πεδίο ορισμού για τα \(y\) με \(D\cdot N + 1\) τιμές για να κάνουμε τα range query μας, δεν πρόκειται να χρησιμοποιήσουμε περισσότερες από \(N\) διαφορετικές τιμές για αυτά, διότι κάθε κατάστημα μπορεί να συνεισφέρει το πολύ ένα \(y_i\) στη δομή μας. Άρα, αν είχαμε ένα segment tree που να επεκτείνετε (expand) μόνο στα \(y\) που χρειάζεται και μόνο όταν χρειάζεται να επεκταθεί, τότε θα είχαμε μείωση στην απαιτούμενη μνήμη.

Το segment tree που θέλουμε θα πρέπει να κάνει expand προς τα φύλλα του μόνο τις \(N\) φορές και κάθε φορά θα δημιουργήσει έως \(\log_2(D\cdot N)\) καινούργιους κόμβους..

Η λύση αυτή περνά όλα τα test cases οριακά.

Η παρακάτω λύση χρησιμοποιεί static memory allocation (το implicit segment tree δεσμεύεται όλο μαζί σαν πίνακας εξ αρχής) με μία απαισιόδοξη προσέγγιση στον αριθμό κόμβων που θα χρειαστούμε ώστε να χωρά την χειρότερη δυνατή περίπτωση.

//RMQ με implicit segment tree 
//οι κομβοι δημιουργούνται όταν απαιτηθεί από την expand()
int32_t stn;//τελευταία χρησιμοποιημένη θέση στον πίνακα κόμβων ST[]
const int32_t SMAX = MAXN * 30;//log2(MAXN * D) == 30
const int32_t YMAX = int32_t(2e4)*MAXN;    //μέγιστη τιμή του y

struct node {
    int32_t left,right;//όρια y που καλύπτει ο κόμβος
    int32_t minZ;//min Shop.Z τιμή για y στο [left,right]
    int32_t leftptr,rightptr;//"pointers" στους απογόνους
        
    node(int32_t le,int32_t ri,int32_t z){
        left = le, right = ri, minZ = z;
        leftptr = rightptr = 0;
    }
    node(){}
} st[SMAX];

void sinit(){
    st[0] = node(0,YMAX,INF);//κόμβος κορυφή
}
void expand(int32_t root){
    node& s = st[root];
    if(!s.leftptr && s.left<s.right){
        int32_t mid = (s.left + s.right)/2;
        assert(stn + 2 < SMAX);
        st[s.leftptr = ++stn] = node(s.left,mid,s.minZ);
        st[s.rightptr= ++stn] = node(mid+1,s.right,s.minZ);
    }
}
int32_t squery(int32_t y,int32_t root = 0){
    node& s = st[root];
    if(s.right <= y)//ο κόμβος συμπεριλαμβάνεται πλήρως
        return s.minZ;
    if(y < s.left)//ο κόμβος δε συμμετέχει
        return INF;
    expand(root);
    assert(s.leftptr);assert(s.rightptr);
    return min(squery(y,s.leftptr),squery(y,s.rightptr));
}
void supdate(int32_t y,int32_t z,int32_t root = 0){
    node& s = st[root];    
    s.minZ = min(s.minZ,z);
    if(s.right == y)
        return;//δεν χρειάζεται επέκταση πιο κάτω
    expand(root);
    if(s.leftptr){
        if(y <= st[s.leftptr].right)
            supdate(y,z,s.leftptr);
        else
            supdate(y,z,s.rightptr);    
    }
}

Μια ενδεικτική παραλλαγή με χρήση dynamic memory allocation μπορείτε να βρείτε εδώ (οι κόμβοι δημιουργούνται δυναμικά όταν και αν χρειαστούν και χρησιμοποιούνται pointers για τη διαχείριση του segment tree). Η χρήση dynamic memory allocation θα καταλάβει μόνο όση μνήμη χρειάζεται αλλά η χρήση pointers απαιτεί μεγαλύτερη ευχέρεια στο χειρισμό της γλώσσας προγραμματισμού.

Λύση με συμπίεση συντεταγμένων - \(\mathcal{O}(N \cdot \log {N})\)

Γνώσεις που θα χρειαστούμε: σύμπτυξη ή συμπίεση συντεταγμένων (coordinate compression)

Έχουμε το πολύ \(N\) τιμές σε κάθε άξονα. Έστω ότι έχουμε ακριβώς \(\mathit{YMAX}\) διαφορετικές τιμές \(y\) \((\mathit{YMAX} \le N)\). Mπορούμε να “συμπιέσουμε” τις τιμές \(y\), δηλαδή να τις αντικαταστήσουμε με διαδοχικούς αριθμούς ανάμεσα στο \(0\) και στο \(\mathit{YMAX}\) αφαιρώντας τα “κενά” ανάμεσα τους. Αντικαθιστούμε το \(y_i\) κάθε καταστήματος \(s_i\) με έναν αριθμό από το \(1\) έως το \(\mathit{YMAX}\) (συμπιεσμένη τιμή) έτσι ώστε να μην χαλάσει η διάταξη (order) μεταξύ των καταστημάτων, δηλαδή για όλους τους συνδυασμούς καταστημάτων \(s_i,s_j\) θα ισχύουν οι συνθήκες:

Με τον τρόπο αυτό περιορίζουμε το πεδίο ορισμού στο οποίο πρέπει να απαντά ερωτήματα το binary indexed tree (ή το segment tree) από \(D\cdot N\) σε \(\mathit{YMAX}\), οπότε δεν ξεπερνάμε τα όρια μνήμης του προβλήματος καθώς:

Αντικαθιστούμε το τμήμα 2 της παραπάνω λύσης με το παρακάτω απόσπασμα που χρησιμοποιεί compression + binary indexed tree. Η λύση αυτή περνά όλα τα test cases.

//RMQ με χρήση Binary Indexed Tree και compressed Y τιμές
int32_t *BIT;
int32_t YMAX = 1; //μέγιστος αριθμός από διαφορετικές τιμές y
void compress_Yvalues(){
    map<int32_t,vector<int32_t>> compressY;//map ασυμπίεστες Y σε συμπιεσμένες τιμές
    
    //βρες τις διαφορετικές τιμές y
    for(int i=1;i<=N;i++)//O(NlogN) εισαγωγή το πολύ N τιμων
        compressY[S[i].Y].push_back(i);
    
    //συμπίεσε τα y αλλά κράτησε τη διάταξη τους
    for(auto it=compressY.begin();it!=compressY.end();it++){//O(N)
        for(auto i: it->second)
		S[i].Y = YMAX;
	YMAX++;
    }
}

void sinit(){
    compress_Yvalues();    
    YMAX += 3;//το BIT έχει πεδίο ορισμού από το 1. Κάνουμε ολίσθηση ώστε να μετρά από το -1
    BIT = new int32_t[YMAX+1];
    memset(BIT,0x7f,sizeof(*BIT)*(YMAX+1));
}
int32_t squery(int32_t y){
    int32_t ymin = BIT[0];
    y+=2;
    while(y>0){
        ymin = min(ymin,BIT[y]);
        y -= y & -y;
    }
    return ymin;
}
void supdate(int32_t y,int32_t z){
    y+=2;
    while(y<=YMAX){
        BIT[y] = min(BIT[y],z);
        y += y & -y;
    }
}

Βέλτιστη λύση με prefix minimum - \(\mathcal{O}(N \cdot \log {N})\)

Στην παραπάνω λύση δείξαμε ότι ψάχνουμε την μικρότερη τιμή \(z_{min}\) από το \(0\) έως κάθε δυνατή θέση \(y_i\) καταστήματος. Κάθε query στη θέση \(y_i\) έχει σαν απάντηση το \(\mathit{RMQ}(y_i)\) δηλαδή το ελάχιστο \(z\) όλων των καταστημάτων που συμμετέχουν στο RMQ έως τώρα και έχουν \(y \in [0,y_i]\). Αυτό που θέλουμε είναι μια ειδική περίπτωση του range query που ψάχνουμε το ελάχιστο \(z\) από όλα τα \(y\) από το αριστερότερο άκρο του άξονα, έως ένα συγκεκριμένο \(y_i\). Η λύση λέγεται prefix minimum, η δημιουργία του οποίου γενικά παίρνει χρόνο \(\mathcal{O}(N)\) (όπως και του prefix sum). Η δυσκολία σε αυτό το prefix minimum είναι ότι θέλουμε να κάνουμε updates σε τυχαία σημεία. Προσέξτε όμως ότι στο παραπάνω σχήμα, οι τιμές του RMQ μένουν σταθερές ή μειώνονται. Για να κάνουμε τα updates αποδοτικά και να διατηρούμε το prefix minimum ενημερωμένο, πρέπει να αξιοποιήσουμε την ιδιότητα αυτή, ότι καμία θέση \(y_j, y_j\gt y_i\) δεν μπορεί να έχει \(\mathit{RMQ}(y_j) \gt \mathit{RMQ}(y_i)\)¹⁰.

Η ακολουθία των \(\mathit{RMQ}(y_i)\) που μας ενδιαφέρουν, είναι φθίνουσα. Αν μάλιστα αγνοήσουμε τα διαδοχικά στοιχεία που έχουν ίσο \(z\) διότι αποτελούν πλεονασμό και κρατήσουμε μόνο το νωρίτερα εμφανιζόμενο σημείο που εμφανίζεται η ίδια τιμή \(z\), καταλήγουμε να αποθηκεύουμε μια γνησίως φθίνουσα ακολουθία από \(z\) τιμές δηλαδή: \(y_i \lt y_j \Leftrightarrow \mathit{RMQ}(y_i) \gt \mathit{RMQ}(y_j)\)

Μια βολική δομή για να αποθηκεύσουμε αυτή την ακολουθία είναι ένα std::map ή ένα std::set και κάθε φορά θα εισάγουμε ένα νέο ζεύγος \((y_i,z_i)\) ή θα προσπαθούμε να βελτιώσουμε ένα υπάρχον ζεύγος με μικρότερο \(z_i\). Καθώς εισάγουμε ή μεταβάλουμε ένα σημείο της ακολουθίας μας διορθώνουμε (διαγράφουμε) τα ασύμβατα στοιχεία που ακολουθούν το \(y_i\) ώστε η ακολουθία μας να παραμείνει γνησίως φθίνουσα. Ας δούμε όλες τις περιπτώσεις που προκύπτουν από την εισαγωγή ενός σημείου \((y_i,z_i)\) στη δομή μας με τη βοήθεια του παρακάτω σχήματος. Το προηγούμενο σημείο στην ακολουθία είναι το \((y_b,z_b)\) και το επόμενο το \((y_c,z_c)\).

Διακρίνουμε πέντε περιπτώσεις:

• μπλέ σημείο: έχει μεγαλύτερο \(z\) από το προηγούμενο σημείο, άρα αγνοείται και δεν αλλάζει η δομή μας
• κόκκινο σημείο: έχει ίδιο \(z\) με το προηγούμενο σημείο, οπότε πάλι αγνοείται και δεν αλλάζει η δομή μας
• κίτρινο σημείο: το \(z\) του είναι ανάμεσα στο προηγούμενο και στο επόμενο σημείο. Εισάγεται και δεν επηρεάζει την μονοτονία της ακολουθίας.
• πράσινο σημείο: έχει ίδιο \(z\) με το επόμενο σημείο. Το επόμενο σημείο διαγράφεται εφόσον καλύπτεται από αυτό που εισάγουμε τώρα.
• ροζ σημείο: έχει μικρότερο \(z\) από το επόμενο σημείο. Θα διαγραφτούν όλα τα επόμενα σημεία με \(z \ge z_i\).

Κάθε κατάστημα κατά το update στη δομή μας, ελέγχει τη μονοτονία της και διαγράφει \(0\) έως \(N\) στοιχεία για να διατηρήσει την ακολουθία γνησίως φθίνουσα. Το κάθε update έχει \(\mathcal{O}(\log {N})\) πολυπλοκότητα. Παρόλο ότι μπορεί να διαγράψει \(N\) στοιχεία σε ένα update, δεν καταλήγουμε σε \(\mathcal{O}(N^2\cdot \log {N})\) πολυπλοκότητα διότι συνολικά, για όλα τα \(N\) updates, δεν μπορούν να διαγραφούν περισσότερο από \(N\) στοιχεία, άρα έχουμε amortized \(\mathcal{O}(\log {N})\) πολυπλοκότητα ανά update.

Η λύση αυτή είναι optimal και περνά όλα τα test cases. Για μια ενδεικτική υλοποίηση αντικαταστήστε το τμήμα 2 με το παρακάτω:

map<int32_t,int32_t> Zmin;

void sinit(){
    //προσθήκη δυο ακραίων τιμών στο map ώστε να μην χρειάζεται να ελέγχουμε 
    //αν φτάσαμε στα όρια begin(), end().
    Zmin.insert({-2,INF});//κάτω όριο για τα queries
    Zmin.insert({INF,-1});//άνω όριο για να μην φτάσουμε στο end()
}
int32_t squery(int32_t y){
    auto it = Zmin.lower_bound(y-1);
    while(it->first >= y)it--;
    return it->second;
}
void supdate(int32_t y,int32_t z){
    auto curr = Zmin.lower_bound(y);
    while(curr->first > y)curr--;
    if(curr->second <= z)
        return;//αγνόησε το
    else if(curr->first == y)//βελτίωσε προηγούμενο σημείο
        curr->second = z;
    else //εισαγωγή του νέου σημείου
        curr = (Zmin.insert({y,z})).first;
    
    //βελτιστοποίησε προς τα δεξιά
    auto next = ++curr;
    while(next->second >= z)
        next++;
    Zmin.erase(curr,next);//std::map διαγραφή περιοχής
}