33ος ΠΔΠ B' Φάση: Τα δώρα των διδύμων (twingift) - Λύση

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

Μας δίνονται δυο πίνακες \(A\) και \(B\) με ακέραιες τιμές και πρέπει να υπολογίσουμε πόσοι συνδυασμοί ζευγαριών \(A_i,B_j\), ικανοποιούν τη συνθήκη \(L \le A_i + B_j \le R\), όπου \(L,R\) γνωστοί ακέραιοι αριθμοί.

Στη συνέχεια θα δωθούν λύσεις και θα επεξηγηθούν με σχήματα για το ακόλουθο αρχείο εισόδου:

Εξαντλητική εξέταση (Brute force)

Για κάθε αριθμό στον ένα πίνακα, ελέγχουμε ποιοι αριθμοί από τον άλλο πίνακα ικανοποιούν τη συνθήκη. Δείτε στο παρακάτω σχήμα τον πίνακα \(B\) επάνω και τον \(A\) κάτω.

Τα στοιχεία των πινάκων που συνδιάζονται, έχουν ίδια απόχρωση. Το \(28\) του πίνακα \(B\), συνδιάζεται και με το \(1\) και με το \(2\) του πίνακα \(A\) οπότε περιέχει και τις δύο αποχρώσεις.

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

#include <cstdio>

const long MAXN = 1'000'000L;

long A[MAXN], NA /*N*/, B[MAXN], MB /*M*/, L,R;

int main(){
    freopen("twingift.in","r",stdin);
    freopen("twingift.out","w",stdout);
    
    scanf("%ld%ld%ld%ld",&NA,&MB,&L,&R);
    for(long i=0;i<NA;i++)scanf("%ld",A+i);
    for(long i=0;i<MB;i++)scanf("%ld",B+i);
    
    long ans = 0;
    for(long i=0;i<NA;i++){
        long LL = L-A[i], RR = R-A[i];
        for(long j=0;j<MB;j++)
            if(LL<=B[j] && B[j]<=RR)
                ans++;
    }
    
    printf("%ld\n",ans);
    return 0;
}

Δυαδική αναζήτηση (Binary search)

Στην εξαντλητική αναζήτηση οι αριθμοί \(B_j\) που συνδυάζονται με το στοιχείο \(A_i\) είναι ανακατεμένοι με τους υπόλοιπους αριθμούς του πίνακα και αυτό δεν μας δίνει τη δυνατότητα να περιορίσουμε το εύρος της αναζήτησης μας. Όταν ελέγχουμε ένα συγκεκριμένο στοιχείο \(A_i\), τότε η συνθήκη \(L \le A_i + B_j \le R\) είναι ισοδύναμη με¹:

Παρατηρούμε ότι τα στοιχεία \(B_j\) ανήκουν σε ένα διάστημα \([L-A_i,R-A_i]\).

Για να αξιοποιήσουμε το στοιχείο αυτό, ταξινομούμε τον πίνακα \(B\) ώστε με τη μέθοδο της δυαδικής αναζήτησης, να εντοπίζουμε σε λογαριθμικό χρόνο το πρώτο στοιχείο του που είναι \(B_{\mathit{left}} \ge L-A_i\) και το τελευταίο του στοιχείο που είναι \(B_{\mathit{right}} \le R - A_i\) και υπολογίζουμε το πλήθος² τους.

#include <cstdio>
#include <algorithm>

using namespace std;

const long MAXN = 1'000'000L;

long A[MAXN], NA /*N*/, B[MAXN], MB /*M*/, L,R;

long solve(long a[],long na,long b[],long nb){
    long ans = 0;
    sort(b,b+nb);
    for(long i=0;i<na;i++)
        ans += upper_bound(b,b+nb,R-a[i])-lower_bound(b,b+nb,L-a[i]);
    return ans;
}

int main(){
    freopen("twingift.in","r",stdin);
    freopen("twingift.out","w",stdout);
    
    scanf("%ld%ld%ld%ld",&NA,&MB,&L,&R);
    for(long i=0;i<NA;i++)scanf("%ld",A+i);
    for(long i=0;i<MB;i++)scanf("%ld",B+i);
    
    printf("%ld\n", (MB>NA) ? solve(A,NA,B,MB) : solve(B,MB,A,NA) );

    return 0;
}

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

Δύο δείκτες (two pointers)

Αν ταξινομήσουμε και τους δύο πίνακες, τότε καθώς θα αυξάνεται το \(i\), θα έχουμε

άρα το διάστημα \([L-A_i,R-A_i]\) θα μετακινείτε προς τις μικρότερες τιμές του πίνακα \(B\). Διατηρούμε δύο δείκτες left και right για να δείχνουν τα όρια του διαστήματος \([L-A_i,R-A_i]\) στον πίνακα \(B\). Οι δείκτες αυτοί θα μετακινούνται μόνο προς τη μια κατεύθυνση (προς τις μικρότερες τιμές του \(B\)) άρα η πολυπλοκότητα της καταμέτρησης όλων των ζητούμενων τιμών στους ταξινομημένους πίνακες, είναι γραμμική.

Με τη μέθοδο αυτή, δεν χρειαζόμαστε τη δυαδική αναζήτηση, έχουμε όμως την επιπλέον επιβάρυνση της ταξινόμησης και του πρώτου πίνακα. Η χρονική πολυπλοκότητα του αλγορίθμου είναι της τάξης \(\mathcal{O}(N \cdot \log N + M \cdot \log M)\). Στο παρακάτω σχήμα έχει αποτυπωθεί ο \(B\) κατά φθίνουσα σειρά και ο \(A\) κατά αύξουσα. Οι δείκτες left και right είναι τα νοητά άκρα της κάθε χρωματισμένης περιοχής

Αναλυτικά, παρουσιάζονται σε ξεχωριστά σχήματα τα επιμέρους βήματα του αλγορίθμου:

#include <cstdio>
#include <algorithm>

using namespace std;

const long MAXN = 1'000'000L;

long A[MAXN], NA /*N*/, B[MAXN], MB /*M*/, L,R;

int main(){
    freopen("twingift.in","r",stdin);
    freopen("twingift.out","w",stdout);
    
    scanf("%ld%ld%ld%ld",&NA,&MB,&L,&R);
    for(long i=0;i<NA;i++)scanf("%ld",A+i);
    for(long i=0;i<MB;i++)scanf("%ld",B+i);
    
    sort(A,A+NA);
    sort(B,B+MB);
    
    long ans = 0, left = MB, right = MB;
    
    for(long i=0;i<NA;i++){
        long LL = L-A[i], RR = R-A[i];//όρια για υποσύνολο του B
        
        //Μετακίνησε το left όσο πιο αριστερά γίνεται 
        //παραμένοντας εντός του διαστήματος [LL,RR]
        while(left>0 && B[left-1]>=LL)left--;
        
        //Μετακίνησε το right όσο γίνεται προς τα αριστερά 
        //παραμένοντας εκτός του διαστήματος [LL,RR]
        //(ώστε να λειτουργεί παρόμοια με το upper_bound)
        while(right>0 && B[right-1]>RR)right--;

        if(!right)break;//δεν υπάρχουν άλλοι συνδυασμοί
        
        ans += right-left;
    }
    
    printf("%ld\n",ans);
    return 0;
}