36ος ΠΔΠ B' Φάση: All that jazz (allthatjazz) - Λύση

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

Ζητείται να βρούμε τον μέγιστο αριθμό συναυλιών (πλήθος διαδοχικών αριθμών \(D_i\)) που χωρούν σε οποιοδήποτε “παράθυρο” το πολύ \(K\) ημερών. Έστω ότι ξεκινάμε να μετράμε από την ημερομηνία \(D_i\) (\(1\le i \le N\)), τότε μας ενδιαφέρει να βρούμε την τελευταία (δεξιότερη) ημερομηνία \(D_m\) με \(i\le m\) και \(D_m - D_i \lt K\). Προϋπόθεση βέβαια είναι ο πίνακας \(D\) να είναι ταξινομημένος με αύξουσα σειρά.

Εξαντλητική αναζήτηση \(\mathcal{O}(Q \cdot N^2)\)

Για κάθε δυνατή ημερομηνία έναρξης \(D_i\), αναζητούμε την μέγιστη ημερομηνία \(D_m\) ώστε \(D_m-D_i \lt K\).

Θα χρησιμοποιήσουμε τρεις εμφωλευμένους βρόγχους: τον εξωτερικό για τα \(Q\) ερωτήματα, τον ενδιάμεσο για την δοκιμή κάθε δυνατού \(i\) και το εσωτερικό για την εύρεση του \(m\). Επομένως, ο απαιτούμενος χρόνος είναι της τάξης \(\mathcal{O}(Q \cdot N^2)\)

#include <algorithm>
#include <cstdio>
#include <vector>

int main(){
    FILE *in = fopen("allthatjazz.in", "r");
    FILE *out= fopen("allthatjazz.out", "w");
    long N,Q;
    fscanf(in, "%ld\n", &N);
    std::vector<long> D(N);
    for(long i = 0; i < N; i++)fscanf(in, "%ld", &D[i]);
    std::sort(D.begin(), D.end());
    fscanf(in, "%ld\n", &Q);
    while(Q-- > 0){
        long K;
        fscanf(in, "%ld", &K);
        long ans = 0;
        for(long i = 0; i < N; i++){
            if(i && D[i]==D[i-1])continue;//υπολογίσαμε ξανά αρχή από την ημέρα αυτή
            for(long m = i; m<N && D[m]-D[i]<K; m++)
                ans = std::max(ans, m-i+1);
        }
        fprintf(out, "%ld\n", ans);
    }
    fclose(out);
    fclose(in);
    return 0;
}

Λύση με δυαδική αναζήτηση \(\mathcal{O}(Q \cdot N \cdot \log{N})\)

Στην πρoηγούμενη λύση μπορούμε να βελτιώσουμε τον εσωτερικό βρόγχο από \(N\) βήματα σε \(\log{N}\) με τη χρήση δυαδικής αναζήτησης (καθώς ο πίνακας \(D\) είναι ταξινομημένος). Η βιβλιοθήκη stl (standard template library) της C++ παρέχει έτοιμες συναρτήσεις για δυαδική αναζήτηση, όπως τη lower_bound και την upper_bound.

H lower_bound εντοπίζει την αριστερότερη θέση που βρίσκεται αριθμός ίσος ή μεγαλύτερος από την τιμή αναζήτησης, ενώ η upper_bound επιστρέφει την αριστερότερη θέση με αριθμό μεγαλύτερο από την τιμή αναζήτησης.
Και οι δυο συναρτήσεις όταν εφαρμοστούν σε πίνακα, επιστρέφουν αντικείμενο τύπου random iterator. Αφαιρώντας από τον επιστρεφόμενο iterator, τον iterator της πρώτης θέσης του πίνακα D.begin(), έχουμε τη θέση στον πίνακα \(D\) σε ακέραια τιμή.

        long ans = 0;
        for(long i = 0; i < N; i++){
            long m = upper_bound(D.begin(), D.end(), D[i]+K-1) - D.begin();
            ans = std::max(ans, m-i);
        }

Δείτε ολόκληρο τον κώδικα εδώ

Βέλτιστη λύση με δύο δείκτες \(\mathcal{O}(Q \cdot N)\)

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

Ας παρατηρήσουμε όμως, ότι αν ξεκινήσουμε από τη μέρα \(i+1\), σίγουρα θα φτάσουμε τουλάχιστον έως την ημέρα \(m\) που είχαμε φτάσει ξεκινώντας από τη θέση \(i\). Αρκεί λοιπόν να διατηρήσουμε δύο δείκτες, ο ένας να είναι ο \(i\) που δείχνει τη μέρα \(D_i\) που ξεκινάμε την παρακολούθηση συναυλιών και έναν δείκτη \(m\) που δείχνει την τελευταία συναυλία στη μέρα \(D_m\) που μπορούμε να παρακολουθήσουμε ώστε να μην υπερβούμε τις \(K\) μέρες. Και οι δύο δείκτες μόνο αυξάνονται.

Για κάθε \(i\) ο δείκτης \(m\) μπορεί να αυξηθεί έως \(N\) φορές, όμως για όλα τα \(i\), ο δείκτης \(m\) θα αυξηθεί συνολικά \(N\) φορές. Άρα για κάθε ερώτημα, θα χρειαστούμε χρόνο \(\mathcal{O}(N)\), οπότε για τα \(Q\) ερωτήματα θα χρειαστούμε \(\mathcal{O}(Q \cdot N)\) χρόνο.

        long ans = 0;
        for(long i = 0, m = 0; i < N; i++){//ο 1ος δείκτης είναι ο i (αρχή παραθύρου)
            if(i && D[i]==D[i-1])continue;//υπολογίσαμε ξανά αρχή από την ημέρα αυτή
            m = std::max(m, i);//να μην προσπεράσει η αρχή (i) το τέλος (m) του παραθύρου
            while(m < N && D[m]-D[i] < K){//ο 2ος δείκτης είναι ο m (τέλος παραθύρου πλάτους<=K)
                ans = std::max(ans, m-i+1);
                m++;
            }
        }

Δείτε ολόκληρο τον κώδικα εδώ