27ος ΠΔΠ B' Φάση: Η μοιρασιά (share) - Λύση

Συγγραφέας: Γιώργος Βιδαλάκης

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

Πρέπει να διαμερίσουμε την ακολουθία των προβλεπόμενων κερδών σε τρία διαδοχικά τμήματα που το καθένα από αυτά θα αντιστοιχεί σε έναν αδέρφό, ώστε το μέγιστο άθροισμα των προβλεπόμενων κερδών σε κάποιο τμήμα να είναι το ελάχιστο δυνατό, δηλαδή ο πιο ευνοημένος αδερφός να έχει το ελάχιστο δυνατό κέρδος.

Brute force λύση

Μία brute force λύση είναι να δοκιμάσουμε όλες τις διαφορετικές διαμερίσεις για τις ημέρες. Για κάθε δυνατή διαμέριση, υπολογίζουμε το προβλεπόμενο κέρδος για κάθε αδερφό, διατρέχοντας γραμμικά το αντίστοιχο τμήμα. Έπειτα, υπολογίζουμε το κέρδος του πιο ευνοημένου αδερφού και το συγκρίνουμε με το ελάχιστο μέγιστο κέρδος που θα έχουμε συναντήσει μέχρι στιγμής.

Το τρέχον ελάχιστο μέγιστο κέρδος το διατηρούμε με την μεταβλητή \(\mathrm{ans}\), και το ενημερώνουμε όπως αναφέραμε. Αρχικοποιούμε \(\mathrm{ans} = 10^9\) (τη μεγαλύτερη δυνατή τιμή σύμφωνα με την εκφώνηση). Μετά από την εξέταση όλων των διαμερίσεων, η μεταβλητή \(\mathrm{ans}\) θα περιέχει την τελική απάντηση την οποία και θα εκτυπώνουμε.

Η εξέταση όλων των διαμερίσεων γίνεται με χρήση δύο εμφωλευμένων for loops, έστω με μεταβλητές \(i\) και \(j\). Ο πρώτος αδερφός θα λάβει τα κέρδη από τη μέρα 1 (αρίθμηση από 1) μέχρι και τη μέρα \(i\), ο δεύτερος από τη μέρα \(i + 1\) μέχρι και τη μέρα \(j\) και ο τρίτος από τη μέρα \(j + 1\) μέχρι και τη μέρα \(N\). Επειδή τα προβλεπόμενα κέρδη είναι ακέραιοι αριθμοί και οι μέρες τουλάχιστον τρεις (\(N \geq 3\)), κάθε τμήμα θα περιέχει τουλάχιστον μία ημέρα. Επομένως, ισχύει ότι \(1 \leq i < j \leq N - 1\).

Επειδή συνολικά υπάρχουν \(\mathcal{O}(N^2)\) διαμερίσεις των ημερών σε διαδοχικά τμήματα και ο υπολογισμός του κέρδους κάθε αδερφού γίνεται σε χρόνο \(\mathcal{O}(N)\), η χρονική πολυπλοκότητα του αλγορίθμου θα είναι \(\mathcal{O}(N^3)\). Σύμφωνα με τους περιορισμούς \(N \leq 10^6\), επομένως το πρόγραμμα θα υπερβεί το χρονικό όριο του ενός δευτερολέπτου για τα περισσότερα testcases. Η χωρική πολυπλοκότητα του αλγορίθμου είναι \(\mathcal{O}(N)\) καθώς πρέπει να αποθηκεύσουμε τα προβλεπόμενα κέρδη σε έναν πίνακα.

#include <cstdio>
#include <algorithm>

#define MAXN 1000005

using namespace std;

long A[MAXN];
// Επιστρέφει το άθροισμα των κερδών στο διάστημα [a, b]
long sum(long a, long b)
{
    long res = 0;
    for (long k = a; k <= b; k++) {
        res += A[k];
    }
    return(res);
}
int main() {
    freopen("share.in", "r", stdin);
    freopen("share.out", "w", stdout);
    long N;
    scanf("%ld", &N);
    for (long i = 1; i <= N; i++) {
        scanf("%ld", &A[i]);
    }
    long ans = 1000 * 1000 * 1000;  // Αρχικοποίηση ελάχιστου μεγίστου στο μέγιστο δυνατό
    for (long i = 1; i < N - 1; i++) {
        for (long j = i + 1; j <= N - 1; j++) {
            // Υπολογισμός προβλεπόμενων κερδών
            long v1 = sum(1, i), v2 = sum(i + 1, j), v3 = sum(j + 1, N);
            // Υπολογισμός μέγιστου κέρδους
            long mx = max(v1, v2);
            mx = max(mx, v3);
            // Έλεγχος αν το τρέχον μέγιστο κέρδος είναι ελάχιστο μέγιστο μέχρι στιγμής
            if (mx < ans)
                ans = mx;
        }
    }
    printf("%ld\n", ans);
    return(0);
}

Καλύτερη brute force λύση με μερικά αθροίσματα

Ο προηγούμενος αλγόριθμος χρειαζόταν \(\mathcal{O}(N)\) χρόνο για τον υπολογισμό του κέρδους κάθε αδερφού. Μπορούμε να κάνουμε τον υπολογισμό αυτό σε σταθερό χρόνο χρησιμοποιώντας τη μέθοδο των μερικών αθροισμάτων.

Συγκεκριμένα, ισχύει ότι \(\sum_{k = a}^b A[k]= \sum_{k = 1}^b A[k] - \sum_{k = 1}^{a - 1} A[k]\). Κρατάμε έναν πίνακα \(S\), μεγέθους \(N + 1\), για να αποθηκεύσουμε τις τιμές των μερικών αθροισμάτων \(S[i] = \sum_{k = 1}^i A[k]\). Υπολογίζουμε όλα τα \(S[i]\) σε γραμμικό χρόνο χρησιμοποιώντας τον τύπο \(S[k] = S[k - 1] + A[k]\), με αρχική συνθήκη \(S[0] = 0\). Επομένως, δεδομένης μίας διαμέρισης, μπορούμε να υπολογίζουμε το προβλεπόμενο κέρδος κάθε αδερφού σε σταθερό χρόνο, καθώς \(\sum_{k = a}^b A[k] = S[b] - S[a - 1]\).

Άρα, η χρονική πολυπλοκότητα του αλγορίθμου μειώνεται κατά \(\mathcal{O}(N)\) και πλέον είναι \(\mathcal{O}(N^2)\) λόγω των δύο εμφωλευμένων for loops για τον υπολογισμό των δυνατών διαμερήσεων των ημερών σε τρία διαδοχικά τμήματα. Ούτε αυτή η πολυπλοκότητα δεν είναι αρκετά καλή για να περάσει όλα τα testcases, ωστόσο είναι σαφώς καλύτερη από την προηγούμενη. Η χωρική πολυπλοκότητα του αλγορίθμου μένει η ίδια.

#include <cstdio>
#include <algorithm>

#define MAXN 1000005

using namespace std;

long A[MAXN], S[MAXN];
int main() {
    freopen("share.in", "r", stdin);
    freopen("share.out", "w", stdout);
    long N;
    scanf("%ld", &N);
    // Διάβασμα προβλεπόμενων κερδών και υπολογισμός μερικών αθροισμάτων
    S[0] = 0;
    for (long i = 1; i <= N; i++) {
        scanf("%ld", &A[i]);
        S[i] = S[i - 1] + A[i];
    }
    long ans = 1000 * 1000 * 1000;  // Αρχικοποίηση ελάχιστου μεγίστου στο μέγιστο δυνατό
    for (long i = 1; i < N - 1; i++) {
        for (long j = i + 1; j <= N - 1; j++) {
            // Υπολογισμός προβλεπόμενων κερδών
            long v1 = S[i], v2 = S[j] - S[i], v3 = S[N] - S[j];
            // Υπολογισμός μέγιστου κέρδους
            long mx = max(v1, v2);
            mx = max(mx, v3);
            // Έλεγχος αν το τρέχον μέγιστο κέρδος είναι ελάχιστο μέγιστο μέχρι στιγμής
            if (mx < ans)
                ans = mx;
        }
    }
    printf("%ld\n", ans);
    return(0);
}

Καλύτερη λύση με δυαδική αναζήτηση

Υπάρχει η δυνατότητα να κατασκευάσουμε έναν ακόμη πιο γρήγορο αλγόριθμο με την εξής απλή παρατήρηση.

Παρατήρηση 1: Εάν δε γίνεται το πιο ευνοημένο από τα αδέρφια να έχει προβλεπόμενο κέρδος μικρότερο ή ίσο με \(K\), τότε δε γίνεται να έχει κέρδος μικρότερο ή ίσο με \(K'\) για κανένα \(K' \leq K\).

Εάν αρχίσουμε λοιπόν να δοκιμάζουμε με τη σειρά τα διαφορετικά \(K\) στο διάστημα ακεραίων \([0, 10^9]\) (επαρκές διάστημα λόγω των περιορισμών της εκφώνησης) ή ακόμη καλύτερα στο \([0, S[N]]\), ελέγχοντας με κάποιον τρόπο (θα τον δούμε στη συνέχεια) για το καθένα από αυτά αν γίνεται να διαμερίσουμε τις μέρες ώστε ο πιο ευνοημένος αδερφός να έχει προβλεπόμενο κέρδος μικρότερο ή ίσο από το εκάστοτε \(K\), τότε από την αρχή μέχρι κάποιο σημείο θα λαμβάνουμε αρνητικές απαντήσεις, ενώ από το σημείο αυτό και μετά θα λαμβάνουμε θετικές απαντήσεις. Το πρώτο \(K\) για το οποίο θα λάβουμε θετική απάντηση είναι το ελάχιστο μέγιστο κέρδος αδερφιού, δηλαδή η απάντηση που ψάχνουμε. Η μορφή λοιπόν που έχουν οι έλεγχοι στο διάστημα ακεραίων που αναφέραμε ως προς την ικανοποιησιμότητα (πρώτα μόνο αρνητικές απαντήσεις και μετά μόνο θετικές) μας επιτρέπει να κάνουμε δυαδική αναζήτηση για να υπολογίσουμε την απάντηση.

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

Παρατήρηση 2: Αν ο πιο ευνοημένος αδερφός έχει κέρδος μικρότερο ή ίσο από \(K\), τότε κάθε ένας από τους τρεις αδερφούς έχει κέρδος μικρότερο ή ίσο από \(K\).

Επομένως δεδομένου του \(K\),

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

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

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

#include <cstdio>

using namespace std;

#define MAXN 1000005

long N;
long A[MAXN], S[MAXN];

// Συνάρτηση άπληστου ελέγχου με γραμμική διάσχιση
bool check(long K) {
    long p = 0, sum = 0;
    // Αντιστοιχία ημερών στον πρώτο αδερφό
    while (p < N && sum + A[p + 1] <= K) {
        sum += A[++p];
    }
    sum = 0;
    // Αντιστοιχία ημερών στο δεύτερο αδερφό
    while (p < N && sum + A[p + 1] <= K) {
        sum += A[++p];
    }
    // Απάντηση ελέγχου ανάλογα με το κέρδος των υπόλοιπων ημερών
    return(S[N] - S[p] <= K);
}
int main() {
    freopen("share.in", "r", stdin);
    freopen("share.out", "w", stdout);
    scanf("%ld", &N);
    // Διάβασμα προβλεπόμενων κερδών και υπολογισμός μερικών αθροισμάτων
    S[0] = 0;
    for (long i = 1; i <= N; i++) {
        scanf("%ld", &A[i]);
        S[i] = S[i - 1] + A[i];
    }
    long lo = 0, hi = S[N];  // Αρχικοποίηση ορίων δυαδικής αναζήτησης
    // Δυαδική αναζήτηση
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;
        else lo = mid + 1;
    }
    long ans = lo;
    printf("%ld\n", ans);
    return(0);
}

Ουσιαστικά βέλτιστη λύση με δύο δυαδικές αναζητήσεις

Η προηγούμενη λύση μπορεί να βελτιωθεί ακόμα, επιταχύνοντας τον άπληστο έλεγχο με την εξής παρατήρηση:

Παρατήρηση: Δεδομένου ενός \(K\) ο άπληστος διαμερισμός των ημερών μπορεί να υπολογιστεί με δυαδική αναζήτηση στα όρια μεταξύ των τμημάτων.

(Απόδειξη) Όπως αναφέραμε, ο πρώτος αδερφός αναλάβει τις μέρες αρχίζοντας από την πρώτη και συνεχίζοντας όσο το προβλεπόμενο κέρδος του δεν υπερβαίνει το \(K\). Η αναζήτηση του σημείου αυτού, μπορεί να γίνει αλλά με δυαδική αναζήτηση στον πίνακα \(S\), βρίσκοντας το μέγιστο \(i\) για το οποίο \(S[i] \leq K\) (καθώς ο πίνακας \(S\) είναι γνησίως αύξων). Έστω ότι αυτό το μέγιστο \(i\) είναι το \(a\). Ομοίως για τον δεύτερο αδερφό η τελευταία ημέρα που θα αναλάβει, μπορεί να βρεθεί με δυαδική αναζήτηση, βρίσκοντας το μέγιστο \(i\) για το οποίο \(S[i] - S[a] \leq K\).

Επομένως, κάθε ένας από τους \(\mathcal{O}(\log S[N])\) άπληστους ελέγχους γίνεται σε \(\mathcal{O}(\log N)\) χρόνο. Έτσι η πολυπλοκότητα της δυαδικής αναζήτησης είναι πλέον \(\log{N} \cdot \log{S[N]}\) αντί για \(N \log{S[N]}\) και συνολικά ο αλγόριθμός θέλει \(\mathcal{O}(N + \log{N} \cdot \log{S[N]})\) χρόνο. Με βάση τους περιορισμούς της εκφώνησης, το \(\mathcal{O}(\log{N} \cdot \log{S[N]})\) είναι αμελητέο συγκριτικά με το \(\mathcal{O}(N)\) για αρκετά μεγάλες τιμές του \(N\), επομένως ο αλγόριθμος είναι γραμμικός (και περνάει όλα τα testcases). Η χωρική πολυπλοκότητα είναι \(\mathcal{O}(N)\).

Σημείωση: Ο αλγόριθμος αυτός γενικεύεται εύκολα για \(M\) αδέρφια και η γενίκευση έχει χρονική πολυπλοκότητα \(\mathcal{O}(N + K \log{N} \cdot \log{S[N]})\). Ο παράγοντας \(K\) οφείλεται στο ότι κάθε άπληστος έλεγχος απαιτεί \(\mathcal{O}(K)\) δυαδικές αναζητήσεις.

#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 1000005
long N;
long A[MAXN], S[MAXN];
// Συνάρτηση άπληστου ελέγχου με δυαδικές αναζητήσεις
bool check(long K) {
    long lo = 0, hi = N;
    // Υπολογισμός πρώτου ορίου
    while (lo < hi) {
        long mid = lo + (hi - lo + 1) / 2;
        if (S[mid] <= K) lo = mid;
        else hi = mid - 1;
    }
    long a = lo;
    hi = N;
    // Υπολογισμός δεύτερου ορίου
    while (lo < hi) {
        long mid = lo + (hi - lo + 1) / 2;
        if (S[mid] - S[a] <= K) lo = mid;
        else hi = mid - 1;
    }
    long b = lo;
    // Απάντηση ελέγχου ανάλογα με το κέρδος των υπόλοιπων ημερών
    return(S[N] - S[b] <= K);
}
int main() {
    freopen("share.in", "r", stdin);
    freopen("share.out", "w", stdout);
    scanf("%ld", &N);
    // Διάβασμα προβλεπόμενων κερδών και υπολογισμός μερικών αθροισμάτων
    S[0] = 0;
    for (long i = 1; i <= N; i++) {
        scanf("%ld", &A[i]);
        S[i] = S[i - 1] + A[i];
    }
    long lo = 0, hi = S[N];  // Αρχικοποίηση ορίων δυαδικής αναζήτησης
    // Δυαδική αναζήτηση
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;
        else lo = mid + 1;
    }
    long ans = lo;
    printf("%ld\n", ans);
    return(0);
}

Βέλτιστη λύση με two pointers

Μία διαφορετική προσέγγιση αυτού του προβλήματος η οποία δίνει βέλτιστη πολυπλοκότητα είναι με τη μέθοδο των two pointers.

Συγκεκριμένα,

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

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

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

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

#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 1000005

long A[MAXN];

int main() {
    freopen("share.in", "r", stdin);
    freopen("share.out", "w", stdout);
    long N, sum = 0;
    scanf("%ld", &N);
    // Διάβασμα προβλεπόμενων κερδών και υπολογισμός αθροίσματός τους
    for (long i = 1; i <= N; i++) {
        scanf("%ld", &A[i]);
        sum += A[i];
    }
    // Υπολογισμός αρχικών προβλεπόμενων κερδών για τα τρία αδέρφια
    long sum1 = A[1], sum3 = A[N], sum2 = sum - sum1 - sum3;
    // Αρχικοποίηση ορίων τμημάτων ημερών
    long a = 1, b = N - 1;
    while (sum2 > sum1 && sum2 > sum3) {
        // Υπολογισμός νέων προβλεπόμενων κερδών μετά από μεταφορά ημέρας
        long inc_sum1 = sum1 + A[a + 1], inc_sum3 = sum3 + A[b];
        if (inc_sum1 < sum2 && inc_sum1 <= inc_sum3) {
            // Μεταφορά ημέρας προς τον πρώτο αδερφό
            sum1 = inc_sum1;
            sum2 -= A[++a];
        }
        else if (inc_sum3 < sum2 && inc_sum3 <= inc_sum1) {
            // Μεταφορά ημέρας προς τον τρίτο αδερφό
            sum3 = inc_sum3;
            sum2 -= A[b--];
        }
        else
            break;
    }
    // Υπολογισμός μέγιστου κέρδους
    long ans = max(sum1, sum2);
    ans = max(ans, sum3);
    printf("%ld\n", ans);
    return(0);
}

Η ορθότητα της διαδικασίας αυτής μπορεί να αποδειχθεί εύκολα και τυπικά με χρήση του επιχειρήματος ανταλλαγής, μίας κλασικής αποδεικτικής μεθόδου για την ορθότητα άπληστων αλγορίθμων. ↩