34ος ΠΔΠ B' Φάση: Ο ξενοδόχος τρελλάθηκε (crazyhotel) - Λύση

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

Μας δίνεται πίνακας \(A\) με \(N\) μη αρνητικές τιμές \(A_i\) (το κόστος διαμονής της ημέρας \(i\)) και δύο τιμές ακόμα, το μέγιστο επιτρεπτό άθροισμα \(S\) και η μέγιστη επιτρεπτή τιμή \(T\). Ζητείται να βρούμε πόσοι είναι οι συνδυασμοί συνεχόμενων αριθμών με άθροισμα που δεν ξεπερνά το \(S\) και καμία τους τιμή δεν ξεπερνά το \(T\).

Παρατήρηση 1: Έστω ότι έχουμε \(k\) συνεχόμενους αριθμούς \(A_i,A_{i+1},A_{i+2},\dots,A_{i+k-1}\) που το άθροισμα τους δεν ξεπερνά το \(S\) και κανένας εξ’ αυτών δεν έχει τιμή που να ξεπερνά το \(T\). Αυτοί οι \(k\) αριθμοί, δίνουν \(k\) δυνατά διαστήματα συνεχόμενων αριθμών που να περιλαμβάνουν το \(A_i\). Αυτοί οι συνδυασμοί είναι:
\(A_i\)
\(A_i + A_{i+1}\)
\(A_i + A_{i+1} + A_{i+2}\)
\(A_i + A_{i+1} + A_{i+2} + A_{i+3}\)
\(\vdots\)
\(A_i + A_{i+1} + A_{i+2} + A_{i+3} + \dots + A_{i+k-1}\)

Οπότε αρκεί σε κάθε θέση \(\mathit{left}\), με \(1 \le \mathit{left} \le N\), να βρεθεί η μεγαλύτερη θέση \(\mathit{right}\) (\(\mathit{left} \le \mathit{right} \le N\)), ώστε το άθροισμα όλων των στοιχείων \(A_\mathit{left} + A_{\mathit{left}+1} + \dots + A_{\mathit{right}-1} + A_{\mathit{right}} \le S\) και κανένας από αυτούς τους αριθμούς να μην υπερβαίνει το \(T\).

Παρατήρηση 2: Το διάστημα \(A_\mathit{left}\) έως και \(A_\mathit{right}\), περιλαμβάνει \(\mathit{right}-\mathit{left}+1\) στοιχεία.

Μη αποδοτική λύση brute force. Πολυπλοκότητα \(\mathcal{O}(N^2)\).

Για κάθε θέση \(\mathit{left}\) εκτελούμε ένα βρόγχο while ώστε να βρούμε τη θέση \(\mathit{right}\). Αθροίζουμε τα μήκη όλων των διαστημάτων \([\mathit{left},\mathit{right}]\) που ικανοποιούν τους περιορισμούς των \(S\) και \(T\).

#include <cstdio>

const long MAXN = 1'000'000L;
long N,S,T, ans, A[MAXN+1];

int main(){
    FILE *in = fopen("crazyhotel.in","r");
    FILE *out = fopen("crazyhotel.out","w");
    fscanf(in,"%ld%ld%ld",&N,&S,&T);
    for(int i=1;i<=N;i++)
        fscanf(in,"%ld",&A[i]);
    for(long left=1;left<=N;left++){	
        //βρες την τελευταία μέρα right που μπορούμε να μείνουμε, 
        //ξεκινώντας από την ημέρα left και ξοδεύοντας το πολύ S χρήματα 
        long right = left-1, intsum = 0;
        while(right+1<=N && A[right+1]<=T && intsum+A[right+1]<=S){
            right++;
            intsum += A[right];
        }
        ans += right - left + 1;
    }
    fprintf(out,"%ld\n",ans);
    fclose(in);
    fclose(out);
    return 0;
}

Βέλτιστη λύση με χρήση δύο δεικτών (two pointers). Πολυπλοκότητα \(\mathcal{O}(N)\).

Η τεχνική αυτή χρησιμοποιεί τους δύο pointers \(\mathit{left}, \mathit{right}\) για να βρει όλα τα διαστήματα που μας ενδιαφέρουν στον πίνακα.

Στην προηγούμενη λύση, η θέση \(\mathit{left}\) αυξάνεται κατά \(1\) σε κάθε επανάληψη του εξωτερικού for μέχρι να προσπελάσει ολόκληρο τον πίνακα. Η θέση \(\mathit{right}\) αντιστοιχεί στη μεγαλύτερη θέση του πίνακα όπου \(A_\mathit{left}+A_{\mathit{left}+1}+A_{\mathit{left}+2}+\dots+A_\mathit{right} \leq S\) και κανένα στοιχείο του διαστήματος δεν υπερβαίνει το \(T\).

Στην επόμενη επανάληψη του εξωτερικού for, το \([\mathit{left},\mathit{right}]\) θα συρρικνωθεί από αριστερά, στο \([\mathit{left}+1,\mathit{right}]\) και καθώς το \(A_\mathit{left}\) που έφυγε από το επιλεγμένο διάστημα, ήταν μη αρνητικός αριθμός, το άθροισμα του συρρικνωμένου διαστήματος δεν θα μεγαλώσει. Καθώς το \(\mathit{left}\) μετακινείται προς τα δεξιά, το \(\mathit{right}\) θα μετακινείτε και αυτό προς τα δεξιά, όσο και αν χρειαστεί, ώστε να βρούμε τη νέα μέγιστη θέση και να συνεχίσουν να ισχύουν οι περιορισμοί των \(S\) και \(T\).

Συνολικά θα μετακινήσουμε κάθε δείκτη \(N\) βήματα, οπότε η πολυπλοκότητα είναι \(\mathcal{O}(N)\).

Για τον υπολογισμό του αθροίσματος κάθε διαστήματος \([\mathit{left},\mathit{right}]\) μπορούν να χρησιμοποιηθούν τα prefix sums (ή cumulative sums) όπως στον παρακάτω κώδικα:

    for(int i=1;i<=N;i++){
        fscanf(in,"%ld",&A[i]);
        PS[i] = PS[i-1] + A[i];
    }
    long left, right = 0;
    for(left=1;left<=N;left++){	
        //βρες την τελευταία μέρα right που μπορούμε να μείνουμε, 
        //ξεκινώντας από την ημέρα left και ξοδεύοντας το πολύ S χρήματα 
        if(right<left-1)//πρέπει Ν>=right+1>=L
            right=left-1;
        while(right+1<=N && A[right+1]<=T && PS[right+1]-PS[left-1]<=S)
            right++;
        ans += right - left + 1;
    }