Αρχική > 37ος ΠΔΠ > counter (εκφώνηση)

37ος ΠΔΠ Γ' Φάση: Ο μετρητής του παππού (counter) - Λύση

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

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

Μας δίνεται ο κώδικας μιας τροποποιημένης δυαδικής αναζήτησης που επιστρέφει τον αριθμό των συγκρίσεων στοιχείων της ακολουθίας ακεραίων \(A\) με έναν ακέραιο αριθμό αναζήτησης \(x\). Ο αριθμός που επιστρέφεται ονομάζεται \(\texttt{counter}\). Επίσης, μας δίνονται \(Q\) ερωτήματα με κάθε ερώτημα να περιέχει ένα διάστημα συνεχόμενων ακεραίων αριθμών \(x\) και ζητείται το άθροισμα των τιμών \(\texttt{counter}\) που θα επέστρεφαν οι κλήσεις στην τροποποιημένη δυαδική αναζήτηση για κάθε ένα από τα \(x\) που περιέχονται στο διάστημα.

Θεωρία: Έστω πίνακας \(N\) ταξινομημένων αριθμών \(A_1 \le A_2 \le \ldots \le A_N\) και ένας αριθμός \(x\). Να βρεθεί αν ο \(x\) περιέχεται στον πίνακα, και αν ναι, σε ποιά θέση βρίσκεται. Αρχικά, ορίζουμε το διάστημα αναζήτησης με δύο δείκτες, το αριστερό (\(\texttt{leftp}=1\)) και δεξί (\(\texttt{rightp}=N\)) άκρο του πίνακα.

Κάνουμε διαδοχικές επαναλήψεις συγκρίνοντας το \(x\) με το μεσαίο στοιχείο \(A_{mid}\) στο διάστημα αναζήτησης, δηλαδή το \(A_{(\texttt{leftp}+\texttt{rightp})/2}\).

Η σύγκριση θα έχει σαν αποτέλεσμα:

  • είτε να βρούμε το στοιχείο \(x\) (αν \(A_{mid} = x\)),
  • είτε να ανακαλύψουμε ότι το \(x\) βρίσκεται αριστερότερα του \(A_{mid}\) οπότε προσπερνάμε τα στοιχεία \(A_{mid},\ldots,A_{rightp}\)) μετακινώντας το δείκτη \(\texttt{rightp}\) αριστερά, στη θέση \(\texttt{mid}-1\),
  • είτε δεξιότερα του \(A_{mid}\) οπότε προσπερνάμε τα στοιχεία \(A_{leftp},\ldots,A_{mid}\) μετακινώντας το δείκτη \(\texttt{leftp}\) στη θέση \(\texttt{mid}-1\).

Ο αλγόριθμος σταματά, όταν βρεθεί το στοιχείο \(x\) (δηλαδή \(A_{mid} = x\)) ή αν οι δείκτες διασταυρωθούν (δηλαδή \(\texttt{leftp} > \texttt{rightp}\)) που σημαίνει ότι το \(x\) δεν υπάρχει. Σε κάθε επανάληψη, πετάμε τα μισά στοιχεία του τρέχοντος διαστήματος, επομένως η αναζήτηση ολοκληρώνεται σε \(\mathcal{O}(\log{N})\) βήματα.

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

Υποπρόβλημα 1 (\(L_1 = R_1\))

Σε αυτό το υποπρόβλημα, κάθε ερώτημα περιέχει μόνο έναν αριθμό \(x\), άρα αρκεί να υπολογίσουμε το \(\text{counter}\) για κάθε ερώτημα καλώντας την FindCounter. Ο χρόνος που απαιτείται για κάθε ερώτημα είναι \(\mathcal{O}(\log{N})\), άρα ο συνολικός χρόνος για τα \(Q\) ερωτήματα, είναι \(\mathcal{O}(Q \cdot \log{N})\). Μπορείτε να δείτε τον κώδικα εδώ.

Υποπρόβλημα 2 (ερωτήματα σε υπαρκτά στοιχεία μόνο)

Το διάστημα κάθε ερωτήματος \(L_i, L_i+1,\ldots,R_i\) είναι μια γνησίως αύξουσα ακολουθία αποτελούμενη από \(R_i-L_i+1\) διαδοχικούς ακέραιους αριθμούς.

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

Για κάθε τιμή \(A_i\), καλούμε τη FindCounter και αποθηκεύουμε το αποτέλεσμα σε έναν πίνακα \(C\). Για τον προϋπολογισμό αυτό, απαιτείται χρόνος \(\mathcal{O}(N \cdot \log{N})\). Κατόπιν, για κάθε ερώτημα βρίσκουμε σε ποιά θέση \(j\) έχουμε \(A_j = L_i\) και σε ποιά θέση \(k\) έχουμε \(A_k=R_i\) κάνοντας δυαδική αναζήτηση (με τις συναρτήσεις της stl: lower_bound, upper_bound), οι οποίες χρειάζονται χρόνο \(\mathcal{O}(\log{N})\).
Η απάντηση στο ερώτημα είναι το άθροισμα \(C_j + C_{j+1}+ \ldots + C_k\). Αντί να υπολογίζουμε αυτό το άθροισμα με επαναληπτικό βρόχο, μπορούμε να χρησιμοποιήσουμε prefix sums, δηλαδή να προϋπολογίσουμε όλα τα αθροίσματα \(PS_i= C_1 + C_2 + \ldots + C_i\) και να απαντάμε το παραπάνω άθροισμα ως τη διαφορά \(S_k-S_{j-1}\) σε σταθερό χρόνο.
O συνολικός χρόνος του αλγορίθμου είναι \(\mathcal{O}(N\cdot \log{N} + Q \cdot \log{N})\) ή \(\mathcal{O}((N + Q) \cdot \log{N})\).

    for (long i = 1; i <= n; i++) C[i] = FindCounter(A[i]);
    for (long i = 1; i <= n; i++) PS[i] = PS[i-1] + C[i];
    
    while (q--) {
        ll L, R;
        scanf("%lld %lld", &L, &R);
        long j = lower_bound(A+1, A+n+1, L) - A;
        long k = upper_bound(A+1, A+n+1, R) - A - 1;
        printf("%lld\n", PS[k] - PS[j-1]);
    }

Μπορείτε να δείτε ολόκληρο τον κώδικα εδώ.

Υποπρόβλημα 3 (\(A_{i+1}=A_i+1\))

Το υποπρόβλημα αυτό μοιάζει με το προηγούμενο, καθώς και εκεί είχαμε διαδοχικά στοιχεία στα διαστήματα των ερωτημάτων του \(A\). Εδώ όμως τα διαστήματα μπορούν να επεκτείνονται και εκτός του \(A\) άρα το κάθε ερώτημα μπορεί:

  • να βρίσκεται ολόκληρο αριστερά του \(A\) στην αριθμογραμμή,
  • να βρίσκεται ολόκληρο εντός του \(A\) (οπότε η απάντηση υπολογίζεται όπως στο προηγούμενο υποπρόβλημα)
  • να βρίσκεται ολόκληρο δεξιότερα του \(A\)
  • να συνδυάζει ένα ή δύο τμήματα εκτός του \(A\) και ένα εντός του \(A\).

Παρατήρηση: αν σε κάποια επανάληψη της δυαδικής αναζήτησης το διάστημα του \(A\) που εξετάζουμε δεν έχει περιττό αριθμό στοιχείων, η τιμή \(m=(l+r)/2\) θα χωρίσει τον πίνακα σε δύο άνισα διαστήματα (το αριστερό τμήμα \(A_l, A_{l+1}, \ldots, A_{m-1}\) θα έχει ένα στοιχείο λιγότερο από το δεξί \(A_{m+1}, A_{m+2}, \ldots, A_r\) λόγω της στρογγυλοποίησης προς τα κάτω που κάνει η ακέραια διαίρεση.

Αυτό σημαίνει ότι για κάποιο \(x\) που είναι μικρότερο όλων των τιμών του πίνακα \(A\) η FindCounter θα επιστρέψει διαφορετική τιμή από ότι για κάποιο \(x\) που είναι μεγαλύτερο όλων των τιμών του \(A\).

Υπολογίζουμε τις δύο επιπλέον τιμές \(\texttt{leftout}\) για \(x=A_1-1\) και \(\texttt{rightout}\) για \(x=A_N+1\) μόνο μια φορά και κατόπιν απαντάμε τα ερωτήματα ως εξής:

    for (long i = 1; i <= n; i++) C[i] = FindCounter(A[i]);
    int leftout = FindCounter(A[1]-1), rightout = FindCounter(A[n]+1);
    for (long i = 1; i <= n; i++) PS[i] = PS[i-1] + C[i];
    
    while (q--) {
        ll L, R, ans=0;
        scanf("%lld %lld", &L, &R);

        if(R<A[1]){//Ολόκληρο το query βρίσκεται αριστερά του A[]
            ans = (R-L+1)*leftout;
        }else if(L>A[n]){//Ολόκληρο το query βρίσκεται δεξιά του A[]
            ans = (R-L+1)*rightout;
        }else {
            if(L<A[1]){//έχουμε μερικά στοιχεία αριστερά του A[]
                ans += ((A[1]-1) - L + 1) * leftout;
                L = A[1];
            }
            if(A[n]<R){//και μερικά δεξιά του A[]
                ans += (R - (A[n]+1) + 1) * rightout;
                R = A[n];
            }
            long j = lower_bound(A+1, A+n+1, L) - A;
            long k = upper_bound(A+1, A+n+1, R) - A - 1;
            ans += PS[k] - PS[j-1];
        }
        printf("%lld\n",ans);
    }

Ο αλγόριθμος χρειάζεται χρόνο \(\mathcal{O}((N + Q) \cdot \log{N})\). Μπορείτε να δείτε ολόκληρο τον κώδικα εδώ.

Υποπρόβλημα 4 (\(N=2^K-1\))

Στο υποπρόβλημα αυτό, τα δύο διαστήματα που προκύπτουν σε κάθε επανάληψη της δυαδικής αναζήτησης είναι ίσα και μάλιστα έχουν μήκος \(2^{K-1}-1\) μετά την πρώτη επανάληψη, \(2^{K-2}-1\) μετά τη δεύτερη επανάληψη κλπ.

Παρατήρηση: Για οποιοδήπτε στοιχείο δεν υπάρχει στον \(A\), χρειαζόμαστε πάντα τον ίδιο αριθμό επαναλήψεων μέχρι να διασταυρωθούν οι δείκτες στην αναζήτηση και συγκεκριμένα μέχρι από τα αρχικά \(2^K-1\) στοιχεία του πίνακα \(A\), να μην μείνει κανένα και να επιστρέψει την τιμή της η FindCounter. Αυτό θα συμβεί μετά από \(K\) επαναλήψεις όπου θα έχουμε \(2^{K-K}-1=2^0-1=0\) στοιχεία.

Τον αριθμό \(K\) δεν χρειάζεται να τον υπολογίσουμε, τον βρίσκουμε καλώντας τη FindCounter μια και μόνο φορά, για κάποιον ανύπαρκο αριθμό, όπως για παράδειγμα τον \(A_1-1\) ή τον \(A_N+1\).

Για το υποπρόβλημα αυτό, αρκεί να βρούμε πόσοι αριθμοί στο ερώτημα υπάρχουν στον \(A\) και πόσοι όχι. Χρησιμοποιούμε τη lower_bound αναζητώντας τη θέση του μικρότερου αριθμού του \(A\) που έχει τιμή ίση ή μεγαλύτερη του αριστερού άκρου του ερωτήματος. Χρησιμοποιούμε την upper_bound για να βρούμε την πρώτη θέση του \(A\) που βρίσκεται μετά το διάστημα του ερωτήματος. Ελέγχουμε μήπως η τιμή που βρήκε η lower_bound ξεπερνά το δεξί άκρο του ερωτήματος ή μήπως η τιμή που βρήκε η upper_bound φανερώνει ότι η αρχή του πίνακα \(A\) βρίσκεται μετά το ερώτημα, καθώς και στις δύο αυτές περιπτώσεις, όλο το διάστημα του ερωτήματος βρίσκεται εκτός του πίνακα \(A\) και ο υπολογισμός τελειώνει εκεί.

Σε κάθε άλλη περίπτωση, έχουμε στοιχεία του \(A\) που περιέχoνται στο ερώτημα και το πλήθος τους υπολογίζεται από τη διαφορά της θέσης που επέστρεψε η upper_bound από τη θέση που επέστρεψε η lower_bound. Η διαφορά αυτή δίνει το πλήθος των υπαρκτών στοιχείων του ερωτήματος στον \(A\). Τα υπόλοιπα στοιχεία, δεν υπάρχουν στον \(A\).

        long j = lower_bound(A+1, A+n+1, L) - A;
        long k = upper_bound(A+1, A+n+1, R) - A - 1;
        if(j>n || A[j]>R || k<1){//Όλο το [L,R] εκτός του A[]
            ans = outside * (R-L+1);
        } else {
            ans = PS[k] - PS[j-1];//Τα στοιχεία του Α εντός του ερωτήματος
            ans += outside * ((R-L+1) - (k-j+1));//και τα εκτός ερωτήματος
        }

Ο αλγόριθμος χρειάζεται χρόνο \(\mathcal{O}((N + Q) \cdot \log{N})\). Μπορείτε να δείτε ολόκληρο τον κώδικα εδώ.

Υποπρόβλημα 5 (\(Q=1\))

Έχοντας μόνο ένα ερώτημα, θα ξεκινήσουμε να κάνουμε τη δυαδική αναζήτηση για όλα τα στοιχεία του ερωτήματος χωρίζοντας το διάστημα \([L,R]\) διαρκώς και συνεχίζοντας αναδρομικά για τα δύο νέα διαστήματα. Η μέθοδος αυτή της διαίρεσης του γενικού προβλήματος σε μικρότερα όμοια προβλήματα μέχρι την τελική λύση, ονομάζεται διαίρει και βασίλευε (divide and conquer).

Αρχικά έχουμε \(\texttt{counter}=1\) και σε κάθε βήμα της αναδρομής γνωρίζουμε ότι βρίσκουμε το \(A_{\texttt{mid}}\) (με \(\texttt{mid}=(\texttt{leftp}+\texttt{rightp})/2\)) και ξεκινάμε αναδρομή στα δυο διαστήματα αριστερά και δεξιά του \(A_{\texttt{mid}}\) αλλά με αυξημένη τιμή \(\texttt{counter}\) κατά \(1\) (καθώς η FindCounter θα συνέχιζε στα διαστήματα αυτά στην επόμενη επανάληψη). Προσοχή χρειάζεται στο τέλος της αναδρομής, όταν διασταυρωθούν οι δείκτες της αριστερής και δεξιάς θέσης του διαστήματος, διότι το \(\texttt{counter}\) δεν αυξάνεται στη διασταύσωση των δεικτών αλλά μόνο στη σύγκριση \(A_{\texttt{mid}}=x\) όπως μπορούμε να δούμε στον ψευδοκώδικα της εκφώνησης. Δείτε παρακάτω την αναδρομική συνάρτηση:

ll query(ll qleft, ll qright, long leftpos=1,long rightpos=n,int counter=0){
    if(qleft > qright) return 0LL;//βγήκαμε εκτός του query
    if(leftpos>rightpos)//δεν υπάρχουν οι αριθμοί του διαστηματος [qleft,qright] στον A[]
        return (qright-qleft+1)*counter;
    ++counter;//σε κάθε σύγκριση του A[mid] με το x, αυξάνεται το counter
    long mid = (leftpos+rightpos)/2;
    ll ans = 0ll;
    if(qleft <= A[mid] && A[mid] <= qright)
        ans += counter;
    ans += query(qleft, min(qright,A[mid]-1),leftpos,mid-1, counter);
    ans += query(max(qleft,A[mid]+1),qright,mid+1,rightpos,counter);
    return ans;
}

Ο αλγόριθμος χρειάζεται χρόνο \(\mathcal{O}(N\cdot \log{N})\). Μπορείτε να δείτε ολόκληρο τον κώδικα εδώ.

Πλήρης λύση

Επεκτείνοντας τη λογική του προηγούμενου υποπροβλήματος, θα υπολογίσουμε όλα τα διαστήματα συνεχόμενων ανύπαρκτων αριθμών στον πίνακα \(A\). Δηλαδή έστω ότι έχουμε \(A_i=4\) και \(A_{i+1}=11\). Το διάστημα με τους αριθμούς \(5,6,7,8,9,10\) είναι ένα διάστημα συνεχόμενων αριθμών, ανύπαρκτων στον πίνακα \(A\). Η δυαδική αναζήτηση για οποιονδήποτε από τους παραπάνω αριθμούς, θα έφτανε μετά από κάποιες επαναλήψεις να έχει \(\texttt{leftp}=i\) και \(\texttt{rightp}=i+1\).

Καθώς ο αριθμός που αναζητούμε δεν υπάρχει, η επόμενη επανάληψη θα καταλήξει με διασταυρωμένα \(\texttt{leftp}\) και \(\texttt{rightp}\) (δηλαδή \(\texttt{leftp}\gt \texttt{rightp}\)) και θα τέλειωναν οι επαναλήψεις με την τρέχουσα τιμή του \(\texttt{counter}\). Γνωρίζοντας σε κάθε διάστημα συνεχόμενων ανύπαρκτων αριθμών, πόσοι είναι αυτοί, μπορούμε να τους προσθέσουμε στα prefix sums που χρησιμοποιήσαμε στα υποπροβλήματα 2,3,4 και να έχουμε την πλήρη λύση.

    vector<ll> A2;//ο πίνακας a[] επαυξημένος με τα συνεχόμενα διαστήματα 
        //ανύπαρκτων αριθμών. Σε κάθε διάστημα αποθηκεύουμε μόνο το δεξιό του άκρο
        //αριστερό άκρο θα είναι ο προηγούμενος υπαρκτός αριθμός του a[] + 1
    for(long i = 1; i <= n; i++) {
        if(i==1 || A2.back()!=A[i]-1)
            A2.push_back(A[i]-1);//δεξιό άκρο ανύπαρκτου τμήματος
        A2.push_back(A[i]);
    }
    A2.push_back(+inf);//Δεξιότερο ανύπαρκτο διάστημα
    //Tο αριστερότερο ανύπαρκτο διάστημα (-inf,a[1]) έχει
    //δεξιό άκρο το a[1]-1 και έχει προστεθεί στην αρχή του A2[] για i=1
    vector<int> C(A2.size());//οι τιμές των FindCounter για τον A2
    for(long i=0;i<A2.size();i++)C[i] = FindCounter(A2[i]);
    
    vector<ll> PS(A2.size());//prefix sums στον C[]
    PS[0] = 0;
    for(long i=1;i<A2.size()-1;i++)
        PS[i] = PS[i-1] + C[i] * (A2[i]-A2[i-1]);
    
    while (q--) {
        ll L, R, ans = 0;
        long j,k;
        scanf("%lld %lld", &L, &R);

        if(R<A[1]){
            ans = C[0] * (R-L+1);
        }else if(L>A[n]){
            ans = C.back() * (R-L+1);
        } else {
            j = lower_bound(A2.begin(), A2.end(), L) - A2.begin();
            k = prev(upper_bound(A2.begin(), A2.end(), R)) - A2.begin();
            ans += C[j] * (A2[j]-L+1);//τμήμα του αριστερότερου ανύπαρκτου διαστήματος του query
            ans += PS[k] - PS[j];//όλα τα ενδιάμεσα τμήματα υπαρκτών αριθμών και ανύπαρκτων διαστημάτων
            if(R > A2[k])//τμήμα του δεξιότερου ανύπαρκτου διαστήματος στο query
                ans += C[k+1] * (R-A2[k]);
        }
        printf("%lld\n",ans);
    }

Ο αλγόριθμος χρειάζεται χρόνο \(\mathcal{O}((N + Q) \cdot \log{N})\). Μπορείτε να δείτε ολόκληρο τον κώδικα εδώ.

Σε ένα διάστημα ανύπαρκτων αριθμών, η FindCounter ισούται με τη μεγαλύτερη από τις δύο τιμές των υπαρκτών αριθμών στα όρια του διαστήματος. Επομένως, μπορούμε να μειώσουμε τις κλήσεις στη συνάρτηση FindCounter σε μόλις \(N+2\). Μπορείτε να δείτε τον σχετικό κώδικα εδώ.