33ος ΠΔΠ Α' Φάση: Τραπεζικές συναλλαγές (bankacc) - Λύση

Λύση με πίνακα ακεραίων (1ο subtask, 50%)

Μας ζητείται να εκτελέσουμε ερωτήματα σε κάποια δομή αντιστοίχισης των τραπεζικών λογαριασμών (ακέραιες τιμές) στα ποσά των λογαριασμών (ακέραιες τιμές). Για το πρώτο και δεύτερο subtask όπου οι αριθμοί τραπεζικών λογαριασμών έχουν τιμές έως \(1.000.000\), η δομή που μπορεί να χρησιμοποιηθεί είναι ένας πίνακας ακεραίων με τους αριθμούς λογαριασμών να είναι οι θέσεις του πίνακα. Για κάθε μια τραπεζική συναλλαγή, χρειαζόμαστε προσπέλαση σε ένα στοιχείο στον πίνακα μας, άρα η συνολική πολυπλοκότητα της λύσης είναι \(\mathcal{O}(N)\).

#include <cstdio>

const long MAXN = 1'000'000;    
long Acc[MAXN];

int main(){
    freopen("bankacc.in", "r",stdin);
    freopen("bankacc.out","w",stdout);
    long N;
    scanf("%ld",&N);
    for(size_t i=0;i<N;i++){
        long A,x;
        char tp;
        scanf(" %c %ld",&tp,&A);
        switch(tp){
            case 'q':
                printf("%ld\n",Acc[A]);
                break;
            case 'd':
                scanf("%ld",&x);
                Acc[A] += x;
                printf("s\n");
                break;
            case 'w':
                scanf("%ld",&x);
                if(Acc[A] < x){
                    printf("f\n");
                }else{
                    Acc[A] -= x;
                    printf("s\n");
                }
                break;
        }
    }
    return 0;
}

Για την πλήρη επίλυση του προβλήματος, όπου οι αριθμοί τραπεζικών λογαριασμών κυμαίνονται μεταξύ \(1\) και \(999.999.999\) δεν μπορούμε να χρησιμοποιήσουμε έναν απλό πίνακα ακεραίων. Ένας πίνακας με ακέραιους 32bit για όλους τους λογαριασμούς, θα καταλάμβανε μνήμη 4Gb, πολύ παραπάνω από τα 64Mb που διαθέτουμε. Παρόλο που το εύρος των αριθμών λογαριασμών είναι υπερβολικά μεγάλο για τη μνήμη και το χρόνο που έχουμε στη διάθεση μας, ο μέγιστος αριθμός λογαριασμών που θα μας δωθεί, δεν ξεπερνά το \(1.000.000\). Οι υπόλοιποι \(998.999.999\) αριθμοί λογαριασμών δεν θα χρησιμοποιηθούν.

Μία τέτοια δομή αντιστοίχησης με μικρή κάλυψη στοιχείων, λέγεται αραιός πίνακας (sparse array). Θα δούμε στη συνέχεια λύσεις που θα φροντίσουν να δεσμεύουν μνήμη της τάξης \(\mathit{O}(N)\) για να αποθηκεύουν μόνο τους λογαριασμούς που χρειάζονται, τόσο με έτοιμα containers της stl όσο και με μια offline λύση που δεν απαιτεί stl ¹.

Χρήση έτοιμων containers της stl

Γνώσεις που θα χρειαστούμε: map, unordered_map, hash value

Η C++ στη βιβλιοθήκη stl μας δίνει έτοιμες δομές αντιστοίχισης κλειδιών αναζήτησης σε συσχετιζόμενες τιμές. Στις δομές αντιστοίχισης, τα κλειδιά αναζήτησης δεν είναι απαραίτητο να είναι συνεχόμενα αρα είναι κατάλληλες για αποθήκευση αραιών πινάκων. Δύο τέτοιες δομές της stl, είναι η map και η unordered_map.

Σαν κλειδί αναζήτησης θα χρησιμοποιούμε τους αριθμούς λογαριασμών και σαν συσχετιζόμενες τιμές, τα ποσά των λογαριασμών. Η unordered_map εκτελεί hash υπολογισμούς στα κλειδά αναζήτησης (αριθμούς λογαριασμών) για να εντοπίζει τις τιμές (ποσά λογαριασμών) που αντιστοιχούν. Εσωτερικά τα δεδομένα στην unordered_map δεν έχουν συγκεκριμένη διάταξη. Η μέση πολυπλοκότητα αναζήτησης ενός στοιχείου είναι σταθερή. Η unordered_map είναι στη γενική περίπτωση πιο γρήγορη στην αναζήτηση συγκεκριμένων στοιχείων από την map, αλλά λόγω της έλλειψης διάταξης των στοιχείων, δεν είναι αποτελεσματική στην αναζήτηση εύρους κλειδιών.

Αντίθετα, η map εσωτερικά χρησιμοποιεί ένα ισορροπημένο δυαδικό δέντρο, οπότε τα κλειδιά είναι σε διάταξη (αύξουσα ή φθίνουσα) και μπορούμε να κάνουμε αναζήτηση συγκεκριμένων κλειδιών ή εύρους κλειδιών με πολυπλοκότητα \(\mathcal{O}(\log{N})\) ανά αναζήτηση.

Και οι δύο αυτές δομές αντιστοίχισης, έχουν ορισμένο τον τελεστή [] και λειτουργούν σαν τους πίνακες. Η λύση με τη χρήση της map έχει συνολική πολυπλοκότητα \(\mathcal{O}(N\cdot\log{N})\) και η λύση με unordered_map έχει \(\mathcal{O}(N)\). Και οι δύο λύσεις με δομές αντιστοίχισης, περνούν όλα τα subtask.

Για τη λύση με τη map αντικαθιστούμε τον πίνακα της λύσης του πρώτου subtask με τον παρακάτω κώδικα:

#include <unordered_map>

std::unordered_map<long,long> Acc;

Ενώ για τη λύση με unordered_map:

#include <map>

std::map<long,long> Acc;

Χρήση ταξινόμησης και offline queries

Συνολικά έχουμε \(1.000.000\) τραπεζικές συναλλαγές με διάφορους τραπεζικούς λογαριασμούς. Ας τις αποθηκεύσουμε σε έναν πίνακα και ας τις ομαδοποιήσουμε έτσι ώστε να τελειώνουμε με όλα τα ερωτήματα του κάθε λογαριασμού πριν ασχοληθούμε με τους επόμενους. Αυτό μπορεί να γίνει με ταξινόμηση των συναλλαγών, δίνοντας προτεραιότητα αρχικά στον αριθμό λογαριασμού και κατόπιν στη σειρά που αυτές αναγνώστηκαν από το αρχείο εισόδου. Η ταξινόμηση με τα παραπάνω κριτήρια γίνεται με τον ορισμό του παρακάτω τελεστή:

    bool operator < (const query& z) const {
        if(acc == z.acc)
            return id < z.id;
        return acc < z.acc;
    }

Μετά την ταξινόμηση, η απάντηση κάθε ερωτήματος γίνεται σε σταθερό χρόνο. Έχοντας αλλάξει τη διάταξη των ερωτημάτων, δεν τα απαντάμε με τη σειρά που τα διαβάσαμε αλλά με τη σειρά που τα συναντούμε μετά την ταξινόμηση, οπότε αποθηκεύουμε τα αποτελέσματα σε έναν ενδιάμεσο πίνακα \(\mathit{ans}\) και τα τυπώνουμε σε δεύτερο χρόνο. Η λύση αυτή περνά όλα τα subtasks και η συνολική της πολυπλοκότητα είναι \(\mathcal{O}(N\cdot\log{N})\) λόγω της ταξινόμησης.

#include <cstdio>
#include <algorithm>

const long MAXN = 1'000'000;

struct query {
    long acc, id, x;
    char tp;
    bool operator < (const query& z) const {
        if(acc == z.acc)
            return id < z.id;
        return acc < z.acc;
    }
} Q[MAXN];

enum answers {
    FAIL = -2,
    SUCCESS = -1
};

long ans[MAXN];
    //θα αποθηκεύουμε -2 για fail, 
    //-1 για success ή
    //μη αρνητικό αριθμό για εκτύπωση υπολοίπου

int main(){
    freopen("bankacc.in", "r",stdin);
    freopen("bankacc.out","w",stdout);
    long N;
    scanf("%ld",&N);
    for(size_t i=0;i<N;i++){
        Q[i].id = i;
        scanf(" %c %ld",&Q[i].tp,&Q[i].acc);
        if(Q[i].tp != 'q')
            scanf(" %ld",&Q[i].x);
    }
    
    std::sort(Q,Q+N);
    
    long curr = 0;//υπόλοιπο τρέχοντος λογαριασμού
    for(int i=0;i<N;i++){
        if(i && Q[i].acc!=Q[i-1].acc){
            //περάσαμε στον επόμενο λογαριασμό
            curr = 0;
        }
        switch(Q[i].tp){
            case 'q':
                ans[Q[i].id] = curr;
                break;
            case 'd':
                curr += Q[i].x;
                ans[Q[i].id] = SUCCESS;
                break;
            case 'w':
                if(curr<Q[i].x){
                    ans[Q[i].id] = FAIL;
                }else{
                    ans[Q[i].id] = SUCCESS;
                    curr -= Q[i].x;
                }
                break;
        }
    }
    
    for(int i=0;i<N;i++){
        if(ans[i]>=0)
            printf("%ld\n",ans[i]);
        else if(ans[i]==FAIL)
            printf("f\n");
        else 
            printf("s\n");
    }
    
    return 0;
}