28ος ΠΔΠ B' Φάση: Ο χαρταετός (kite) - Λύση

Επεξήγηση προβλήματος

Όπως αναγράφεται και στην εκφώνηση:

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

Άρα τα κομμάτια θα είναι

• ή στην αρχή (από το κομμάτι \(1\) ως το κομμάτι \(n\), \(1\le n\le N\))
• ή στο τέλος (από το κομμάτι \(n\), \(1 \le n \le N\), ως το κομμάτι \(N\))
• ή κάπου στη μέση (από το κομμάτι \(i\), ως το κομμάτι \(j\), \(1 < i \le j < N\))

Αυτές οι τρεις υποπεριπτώσεις μπορούν να ενωθούν σε μία πρόταση ως:

• από το κομμάτι \(i\) ως το κομμάτι \(j\), \(1 \le i \le j \le N​\)

Με λίγα λόγια πρέπει να βρούμε αν υπάρχει συνεχόμενο κομμάτι της καλούμπας με μήκος \(K\).

Λύση πολυπλοκότητας \(\mathcal{O}(N^3)\)

Η πιο απλή λύση στο πρόβλημα είναι ο έλεγχος όλων των πιθανών ζευγών \((i, j)\). Αν το άθροισμα από το \(i\) ως το \(j\) είναι ίσο με \(K\), τότε ανανεώνουμε την τιμή των ελάχιστων κομματιών αν τα κομμάτια από το \(i\) ως το \(j\) είναι λιγότερα (τα κομμάτια από το \(i\) ως το \(j\) είναι \(j-i+1\)).

#include <cstdio>

const size_t MAXN = 2000000;

long N, K;
long M[MAXN + 1]; // Πίνακας με το μήκος των κομματιών

int main () {
    // Διάβασμα αρχείου εισόδου
    freopen("kite.in", "r", stdin);
    scanf("%ld %ld", &N, &K);
    for (long i = 1; i <= N; ++i) { scanf("%ld", &M[i]); }
    
    // Αρχική μέγιστη τιμή: Ν + 1
    // Αν στο τέλος της επανάληψης η τιμή 
    // είναι ακόμα Ν + 1 σημαίνει ότι 
    // κανένα κομμάτι καλούμπας δεν είχε άθροισμα 
    // ίσο με Κ και άρα στην απάντηση πρέπει να τυπώσουμε 0
    long minPieces = N + 1;
    // Για κάθε ζεύγος (i, j), 1 <= i <= j <= N
    for (long i = 1; i <= N; ++i) {
        for (long j = i; j <= N; ++j) {
            // Υπολογισμός αθροίσματος
            long sum = 0;
            for (long k = i; k <= j; ++k) { sum += M[k]; }
            
            // Ανανέωση του ελάχιστου άμα το άθροισμα
            // είναι ίσο με Κ και το μήκος είναι μικρότερο του ελάχιστου
            if (sum == K && j - i + 1 < minPieces) {
                minPieces = j - i + 1;
        	}
        }
    }
    freopen("kite.out", "w", stdout);
    if (minPieces == N + 1) {
        // Δεν βρέθηκε κομμάτι με μήκος Κ
        printf("0\n");
        return 0;
    }
    // Αλλιώς έχουμε βρει κομμάτι
    printf("%ld\n", minPieces);
    return 0;
}

Επειδή κρατάμε ένα πίνακα \(M\) με τα στοιχεία, ο χώρος της λύσης είναι \(\mathcal{O}(N)\).

Σημείωση: Στον παραπάνω κώδικα επανάληψη γίνεται με βάση το \(i\) και μετά το \(j\). Αν γινόταν πρώτα με βάση το μήκος \(l=i−j+1\), \(1\leq l \leq N\) και μετά με βάση το \(i\), τότε δεν χρειάζεται να κρατάμε τη μεταβλητή \(\mathit{minPieces}\) γιατί αν βρούμε μία λύση κατά τη διάρκεια αυτής της επανάληψης τότε θα ξέρουμε ότι είναι η βέλτιστη (γιατί έχουμε εξαντλήσει όλες τις περιπτώσεις με μικρότερο μήκος). Επίσης με το που θα βρεθεί η λύση, θα μπορούμε να τερματίσουμε το πρόγραμμα, γλιτώνοντας επαναλήψεις.

Λύση πολυπλοκότητας \(\mathcal{O}(N^2)\)

Μία από τις επαναλήψεις που μπορούμε να γλιτώσουμε είναι αυτή του αθροίσματος. Στην προηγούμενη λύση είδαμε ότι για κάθε ζεύγος \((i, j)\) υπολογίζαμε το άθροισμα από το \(i\) ως το \(j\). Θέλουμε έναν πιο γρήγορο τρόπο να υπολογίζουμε το άθροισμα.

Έστω \(S(i, j) = \sum_{k=i}^{j}M_k\), το άθροισμα των στοιχείων από το \(i\) έως το \(j\). Αυτό μπορούμε να το γράψουμε ως,

όπου \(C(i) = M_1 + M_2 + \dotsb + M_{i-1}+M_{i} = C(i-1) + M_i\), είναι το άθροισμα των στοιχείων από το \(1\) ως το \(i\). Χρειάζεται να προϋπολογίσουμε το \(C(i)\) στην αρχή του προγράμματος, αλλά είναι γρήγορο και δεν πιάνει πολύ χώρο (\(\mathcal{O}(N)\) χρόνο και \(\mathcal{O}(N)​\) χώρο).

// ...
    // Αφού διαβάσουμε τα μήκη στον πίνακα M μπορούμε 
    // να υπολογίσουμε τον πίνακα C
    long C[N + 1];
    C[0] = 0; // Δεν περιέχει κανένα κομμάτι άρα έχει τιμή 0
    for (long i = 1; i <= N; ++i) {
        // Το C[i] είναι όσο το C[i-1] συν
        // το επιπλέον κομμάτι που περιέχει M[i]
        C[i] = C[i-1] + M[i];
    }
// ...

Μετά από αυτόν τον υπολογισμό, ο υπολογισμός του αθροίσματος γίνεται

// ...

	for (long i = 1; i <= N; ++i) {
        for (long j = i; j <= N; ++j) {
            // Υπολογισμός αθροίσματος
            long sum = C[j] - C[i-1];

            // ...
        }
    }

// ...

Αυτό μειώνει την πολυπλοκότητα της επανάληψης από \(\mathcal{O}(N^3)\) σε \(\mathcal{O}(N^2)\) και προσθέτει ακόμα μία επανάληψη πολυπλοκότητας \(\mathcal{O}(N)\) και χώρο \(\mathcal{O}(N)\). Άρα συνολικά η πολυπλοκότητα είναι \(\mathcal{O}(N^2)\) και ο χώρος παραμένει \(\mathcal{O}(N)\).

Λύση πολυπλοκότητας \(\mathcal{O}(N\log N)\)

Παρατήρηση: Η συνάρτηση \(C(i)\) είναι αύξουσα, δηλαδή όσο μεγαλώνει το \(i\), μεγαλώνει και το \(C(i)\). Αυτό σημαίνει ότι το \(S(i, j) = C(j) - C(i-1)\), είναι αύξουσα ως προς \(j\) και φθίνουσα ως προς \(i\).

Μπορούμε να δείξουμε αυτή τη σχέση στον επόμενο πίνακα \(S(i, j)\), για το παράδειγμα της εκφώνησης:

\(N = 6\), \(K = 33\), \(M_i = [1, 4, 20, 3, 10, 5]\)

Οι τιμές για \(j < i\) δεν υπάρχουν αφού υποθέσαμε ότι το \(j\) είναι το τέλος και το \(i\) η αρχή. Παρατηρούμε ότι:

• για σταθερό \(i\), οι τιμές \(S(i, j)\) αυξάνονται όσο αυξάνεται το \(j\) (γραμμές του πίνακα)
• για σταθερό \(j\), οι τιμές \(S(i, j)\) μειώνονται όσο μειώνεται το \(i\) (στήλες του πίνακα)

Αυτή η ιδιότητα μας δείχνει ότι μόνο μια φορά μπορεί να εμφανίζεται η τιμή \(K\) σε κάθε γραμμή ή στήλη. Επομένως μπορούμε για κάθε γραμμή¹ να εφαρμόσουμε μια δυαδική αναζήτηση (binary search) και να βρούμε την μοναδική εμφάνιση του \(K\), αν αυτό υπάρχει στη συγκεκριμένη γραμμή.

Η δυαδική αναζήτηση μπορεί να γραφτεί ως συνάρτηση:

// H συνάρτηση που επιστρέφει τιμές από τον πίνακα S(i, j)
long S(long i, long j) {
    return C[j] - C[i - 1];
}

long binSearch(long line, long lo, long hi, long val) {
    while (lo < hi) {
        // Σπάμε το διάστημα (lo, hi) σε 2 ίσα υποδιαστήματα
        long mid = (lo + hi) / 2;
        // Παίρνουμε την τιμή στο μέσο του διαστήματος
        long midVal = S(line, mid);
        
        if (midVal == val) {
            // Βρήκαμε την θέση της τιμής οπότε επιστρέφουμε
            return mid;
        }
        if (midVal < val) {
            // Οι γραμμές είναι άυξουσες οπότε για όλα
            // τα i < mid, arr[i] < arr[mid] < val άρα
            // απορρίπτονται
            // Αν χρησιμοποιούσαμε τις στήλες τότε 
            // θα απορρίπταμε τα i > mid
            lo = mid + 1;
        } else { hi = mid - 1; }
    }
    // Το lo είναι το τελευταίο στοιχείο που μένει και ελέγχουμε 
    // αν έχει την τιμή val
    if (S(line, lo) == val) { return lo; }
    return -1; // -1 σημαίνει ότι η τιμή δεν βρέθηκε
}

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

Επομένως, αντικαθιστώντας την επανάληψη για κάθε \(j\), με την δυαδική αναζήτηση:

// ...

	for (long i = 1; i <= N; ++i) {
        // Το εύρος της αναζήτησης, όπως μπορούμε να δούμε και από
        // τον πίνακα των S(i, j) ξεκινάει από το i και καταλήγει στο N
        long j = binSearch(i, i, N, K);
        if (j != -1) {
            // Άμα βρέθηκε τιμή Κ σε αυτήν τη γραμμή
            if (j - i + 1 < minPieces) { minPieces = j - i + 1; }
        }
    }

// ...

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

Σημέιωση: Η λύση αυτή είναι αρκετή για να περάσει το πρόγραμμα όλα τα testcases.

Λύση πολυπλοκότητας \(\mathcal{O}(N)\)

Ας υποθέσουμε ότι με κάποιο τρόπο γνωρίζουμε ότι δεν υπάρχει λύση που να ξεκινάει για κάποιο \(i < I\), ή να τελειώνει σε κάποιο \(j < J\) (με λίγα λόγια υποθέτουμε ότι έχουμε ελέγξει αυτές τις περιπτώσεις).

Τότε αν το \(S(I, J) > K\), τότε συμπεραίνουμε ότι ούτε για \(i = I\) υπάρχει λύση, καθώς αυτό θα προϋπέθετε ότι \(j < J\). Άρα \(i \ge I + 1\). Επομένως αφού μόλις απορρίψαμε το \(i = I\), η αρχική υπόθεση θα ισχύει για το ζεύγος \((I + 1, J)\).

Ομοίως, αν \(S(I, J) < K\), τότε συμπεραίνουμε ότι δεν υπάρχει λύση για \(j = J\), καθώς αυτό θα σήμαινε ότι \(i < I\). Άρα \(j \ge J + 1\). Επομένως η αρχική υπόθεση ισχύει για το ζεύγος \((I, J + 1)\).

Επομένως, αν έχουμε το ζεύγος \((I, J)\):

• Αν \(S(I, J) > K\), τότε αυξάνουμε το \(I\) κατά \(1\).
• Αν \(S(I, J) < K​\), τότε αυξάνουμε το \(J​\) κατά \(1​\).
• Αν \(S(I, J) = K\), τότε αυξάνουμε και το \(I\) και το \(J\) κατά \(1\), και ελέγχουμε αν το διάστημα \((I, J)\) έχει το έως τώρα ελάχιστο μήκος.

Αρχικές τιμές των \(I\) και \(J\), θα είναι \(I = J = 1\), αφού στην αρχή δεν έχουμε ελέγξει κανένα ζευγάρι τιμών.

Σημείωση: Δεν χρειάζεται να κρατάμε τον πίνακα με τα μήκη των σχοινιών, αφού δεν χρειάζεται πουθενά πέρα από τον υπολογισμό των αθροισμάτων \(C\).

#include <cstdio>

const size_t MAXN = 2000000;

long N, K;
long C[MAXN + 1];

long S(long i, long j) {
    return C[j] - C[i - 1];
}

int main () {
    freopen("kite.in", "r", stdin);
    scanf("%ld %ld", &N, &K);
    C[0] = 0;
    
    for (long i = 1; i <= N; ++i) { 
        long piece;
        scanf("%ld", &piece);
        C[i] = C[i - 1] + piece;
    }
    
    long minPieces = N + 1;
    long i = 1, j = 1;
    // Αυξάνουμε το j ένα-ένα τη φορά
    while(j <= N) {
        // Όσο το S(i, j) > K, αυξάνουμε το i κατά 1
        while (S(i, j) > K) { ++i; }
        // Ελέγχουμε αν το S(i, j) = Κ
        if (S(i, j) == K) {
            // Βρήκαμε μία πιθανή λύση οπότε την ελέγχουμε
            if (j - i + 1 < minPieces) { minPieces = j - i + 1; }
            // Αυξάνουμε το i, αφού δεν πρόκειται να μας δώσει πάνω
            // από μία λύση
            ++i;
        }
        // Τελειώνει η επανάληψη γνωρίζοντας ότι S(i, j) < K
        // και άρα το j θα αυξηθεί
        ++j;
    }
    freopen("kite.out", "w", stdout);
    if (minPieces == N + 1) {
        // Δεν βρέθηκε κομμάτι με μήκος Κ
        printf("0\n");
        return 0;
    }
    // Αλλιώς έχουμε βρει κομμάτι
    printf("%ld\n", minPieces);
    return 0;
}

Αρχικά μπορεί να φανεί σαν να χειροτέρεψε η πολυπλοκότητα έχοντας μια while μέσα σε μία άλλη while. Παρ’ όλ’ αυτά, οι δείκτες \(i\), \(j\), μόνο αυξάνονται άρα στη χειρότερη των περιπτώσεων ο αριθμός των επαναλήψεων θα είναι \(N\) φορές για το \(i\) από \(1\) έως \(N\), και άλλες \(N\) για το \(j\). Άρα συνολικά έχουμε \(\mathcal{O}(N + N) = \mathcal{O}(N)\) πολυπλοκότητα και χώρο \(\mathcal{O}(N)\) για τον πίνακα των αθροισμάτων.