38ος ΠΔΠ Α' Φάση: Χαμένα κουτιά (missing) - Λύση

Συγγραφέας: Κωνσταντίνος Μποκής

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

Σε μια ακολουθία $N$ συνεχόμενων ακέραιων αριθμών $1,2,3,\ldots ,N$, λείπουν $K$ από αυτούς ενώ οι υπόλοιποι $M$ είναι κρυμμένοι. Ζητείται να βρεθούν οι $K$ αριθμοί που λείπουν χρησιμοποιώντας το πολύ $Q$ ερωτήσεις. Κάθε ερώτηση, αποκαλύπτει έναν κρυμμένο αριθμό σε θέση που επιλέγουμε. Μας δίνεται το πλήθος των κρυμμένων αριθμών $M$ και ότι δεν λείπει κανένας αριθμός μετά από τον δεξιότερο κρυμμένο.

Δεν γνωρίζουμε πόσοι αριθμοί λείπουν, ούτε πόσοι είναι όλοι οι αριθμοί της ακολουθίας. Εφόσον γνωρίζουμε ότι δεν λείπει κανένας αριθμός μετά τον τελευταίο, ο τελευταίος είναι ο $N$. Θα ξοδέψουμε ένα ερώτημα για να ανακαλύψουμε τον $N$, και ταυτόχρονα υπολογίζουμε ότι λείπουν $K=N-M$.

Κάθε ερώτημα απαιτεί μια εκτύπωση στο standard output, άδειασμα της προσωρινής μνήμης (fflush) και διάβασμα της απάντησης. Θα χρησιμοποιήσουμε την παρακάτω βοηθητική συνάρτηση query που κάνει αυτές τις εργασίες για να οργανώσουμε καλύτερα τον κώδικα.

int query(int x){
    printf("? %d\n",x);
    fflush(stdout);
    scanf("%d",&x);
    if(x==-1) exit(0);
    return x;
}

Λύση brute force (13%)

Στο υποπρόβλημα αυτό, έχουμε στη διάθεση μας αρκετά ερωτήματα για να ανακαλύψουμε έναν έναν όλους τους κρυμμένους αριθμούς. Όσοι αριθμοί ανάμεσα στο $1$ και στο $N$ δεν περιέχονται σε αυτούς που ανακαλύψαμε, είναι αυτοί που λείπουν. Αυτή η λύση χρησιμοποιεί $N$ ερωτήματα και μπορείτε να δείτε τον κώδικα εδώ.

Λύση με δυαδική αναζήτηση για $K=1$ (24%)

Στο υποπρόβλημα αυτό, λείπει μόνο ένας αριθμός.

Παρατήρηση 1η: κάθε θέση $i$ περιέχει τον αριθμό $i$ αν δεν λείπει κανένας μικρότερος αριθμός. Αν παραδείγματος χάριν, λείπει μόνο ο αριθμός $a$, όλοι οι αριθμοί $1,2,\ldots,a-1$ βρίσκονται στην αναμενόμενη θέση τους $1,2,\ldots,a-1$ και όλοι οι αριθμοί $a+1,a+2,\ldots,N$ βρίσκονται μια θέση αριστερότερα, δηλαδή στις $a,a+1,\ldots,N-1$ αντίστοιχα.

Κάνοντας δυαδική αναζήτηση, εντοπίζουμε την πρώτη θέση $i$ στην οποία ο αριθμός που κρύβεται σε αυτή, δεν είναι ίσος με το $i$.

    int leftpos = 1, rightpos = M, missing=-1;
    while(leftpos<=rightpos){
        int midpos = (rightpos + leftpos + 1)/2, midval = query(midpos);
        if(midpos<midval){
            missing = midval;
            rightpos= midpos-1;
        } else {
            leftpos = midpos+1;
        }
    }

Απαιτούνται $\mathcal{O}(\log_2{N})$ ερωτήματα για τη λύση αυτή. Ολόκληρος ο κώδικας εδώ

Λύση με δυαδική αναζήτηση ενός διαστήματος (18%)

Στο υποπρόβλημα αυτό, λείπει ένα συνεχόμενο διάστημα αριθμών. Αναζητούμε όπως και στην προηγούμενη λύση, τον πρώτο αριθμό $x$ που δεν βρίσκεται στην θέση του και συγκεκριμένα θα βρίσκεται $K$ θέσεις αριστερότερα από την αναμενόμενη θέση του. Οι προηγούμενοι $K$ αριθμοί $x-K,x-K+1,x-K+2,\ldots,x-1$ είναι αυτοί που λείπουν, οπότε και τους τυπώνουμε. Για παράδειγμα, στην ακολουθία $[1,2,3,4,6,9,10]$ με $K=3$ βρίσκουμε το $8$ και έπειτα τυπώνουμε τους αριθμούς $5,6,7$ αμέσως πριν το $8$.

    int leftpos = 1, rightpos = M, missing_gap = -1;
    while(leftpos<=rightpos){
        int midpos = (leftpos+rightpos+1)/2, midval = query(midpos);
        if(midpos < midval){
            missing_gap = midval;
            rightpos = midpos-1;
        } else {
            leftpos  = midpos+1;
        }
    }

Απαιτούνται $\mathcal{O}(\log_2{N})$ ερωτήματα για τη λύση αυτή. Ολόκληρος ο κώδικας εδώ

Υποβέλτιστη λύση με δυαδική αναζήτηση (17%)

Στο υποπρόβλημα αυτό λείπουν $K$ αριθμοί. Για κάθε $i$-οστό αριθμό που λείπει, οι επόμενοι κρυμμένοι αριθμοί, θα βρίσκονται αριστερότερα τόσες θέσεις, όσες όλοι οι μικρότεροι από αυτούς αριθμοί που λείπουν. Αρκεί να κάνουμε δυαδική αναζήτηση με την επιθυμητή διαφορά ανάμεσα στην θέση ενός κρυμμένου αριθμού και στην τιμή του, για να βρούμε τον $i$-οστό αριθμό.

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

    vector<pair<int,int>> missing;    //αριθμός που λείπει, πλήθος αριθμών που λείπουν στη θέση
    for(int i=0;i<K;i++){
        //δυαδική αναζήτηση για τον αριθμό
        //που βρίσκεται i θέσεις αριστερότερα από την αναμενόμενη θέση του
        int leftpos = 1, rightpos = M, missing_gap = -1;
        while(leftpos<=rightpos){
            int midpos = (leftpos+rightpos+1)/2, midval = query(midpos);
            if(midpos+i < midval){//ο αριθμός δεν βρέθηκε στη θέση του,
                //άρα λείπουν αριθμοί εδώ ή και αριστερότερα
                missing_gap = midval;
                rightpos = midpos-1;
            } else {
                leftpos  = midpos+1;
            }
        }
        if(!missing.empty() && missing.back().first==missing_gap)
            missing.back().second++;
        else
            missing.push_back({missing_gap,1});
    }

Απαιτούνται $\mathcal{O}(K \cdot \log_2{N})$ ερωτήματα για τη λύση αυτή. Ολόκληρος ο κώδικας εδώ

Βέλτιστη λύση με δυαδική αναζήτηση (100%)

Στο προηγούμενο υποπρόβλημα, ξεκινώντας δυαδική αναζήτηση για κάθε έναν από τους $K$ αριθμούς, κάναμε πολλές φορές ερωτήματα για τις ίδιες θέσεις. Αν αποθηκεύσουμε τις απαντήσεις στα ερωτήματα (memoization) ώστε να μην τα επαναλάβουμε, τότε μειώνουμε αρκετά τον αριθμό των ερωτημάτων ώστε ο κώδικας να περνά όλα τα test cases. Ακολουθεί η συνάρτηση query με ενσωματωμένη την τεχνική αυτή. Κάθε κλήση στην query ελέγχει αν υπάρχει ήδη αποθηκευμένη απάντηση στον πίνακα mem (από προηγούμενο ερώτημα) ή αν πρέπει να γίνει νέο ερώτημα.

int mem[MAXN];
int query(int x){//αποθηκεύουμε στο mem[x-1] το query(x), ώστε
    if(!mem[x-1]){//να μην ξανακάνουμε δύο φορές το ίδιο ερώτημα
        printf("? %d\n",x);
        fflush(stdout);
        scanf("%d",&mem[x-1]);
        if(mem[x-1]==-1) exit(0);
    }
    return mem[x-1];
}

Ολόκληρος ο κώδικας εδώ

Βέλτιστη λύση με την τεχνική διαίρει και βασίλευε (100%)

Πληροφορίες για την τεχνική διαίρει και βασίλευε, μπορείτε να βρείτε εδώ. Η τεχνική διαίρει και βασίλευε είναι ένας αναδρομικός τρόπος επίλυσης προβλημάτων που διαιρεί ένα μεγάλο διάστημα σε μικρότερα χωρίς να ελέγχει καμία θέση πάνω από μια φορά (δεν υπάρχουν επικαλύψεις διαστημάτων). Λύνουμε το πρόβλημα στα μικρότερα διαστήματα και κατόπιν συνενώνοντας τις επιμέρους λύσεις, έχουμε τη λύση για το αρχικό πρόβλημα.

Διαιρούμε συνεχώς το διάστημα των θέσεων των κρυμμένων αριθμών σε δύο τμήματα περίπου ίσου μεγέθους αναδρομικά. Ταυτόχρονα διατηρούμε το διάστημα των αριθμών που αναμένεται να βρίσκονται σε αυτές τις θέσεις αν δεν έλειπε κανείς. Καθώς διαιρούμε κάθε διάστημα των κρυμμένων θέσεων, θα βρίσκουμε διαστήματα που:

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

Στις τελευταίες δύο περιπτώσεις δεν χρειάζεται να κάνουμε κανένα επιπλέον ερώτημα (ολοκληρώθηκε η διερεύνηση αυτών των διαστημάτων). Η αναδρομή θα καταλήξει σε βάθος το πολύ $\mathcal{O}(\log_2{N})$ καθώς διαιρεί συνεχώς με το $2$ και τα διαστήματα που θα βρει θα είναι $\mathcal{O}(K)$, άρα ο συνολικός χρόνος του αλγορίθμου θα είναι $\mathcal{O}(K\cdot\log_2{N})$.

vector<int> missing;
void divide_and_conquer(int leftval,int leftpos, int rightval,int rightpos){
    if(leftval>rightval)return;//κενό διάστημα
    if(rightpos-leftpos+1 <= 0){//λείπουν όλοι οι αριθμοί
        for(int i=leftval;i<=rightval;i++)missing.push_back(i);
        return;
    }
    if(rightpos-leftpos==rightval-leftval)return;//υπάρχουν όλοι οι αριθμοί

    int midpos = (rightpos+leftpos+1)/2, midval = query(midpos);

    divide_and_conquer(leftval,leftpos,midval-1,midpos-1);
    divide_and_conquer(midval+1,midpos+1,rightval,rightpos);
}