30ος ΠΔΠ B' Φάση: Τα κάλαντα (kalanta) - Λύση
Επεξήγηση εκφώνησης
Μας δίνεται μία κυκλική λίστα από θετικούς ακέραιους. Πρέπει να χωρίσουμε αυτή την λίστα σε δύο συνεχή τμήματα ώστε η διαφορά των αθροισμάτων των στοιχείων των δύο τμημάτων να είναι ελάχιστη.
Παρατήρηση 1: Αν διαλέξουμε το συνεχές τμήμα για την Πράσινη, τότε αυτομάτως διαλέγουμε το συνεχές τμήμα για τον Κόκκινο.
Όλα τα στοιχεία που δεν είναι πράσινα, θα είναι κόκκινα. Επίσης, αν \(\mathit{sum\_green}\) είναι το άθροισμα όλων των στοιχείων της Πράσινης και \(\mathit{total}\) είναι το άθροισμα όλων των στοιχείων, τότε το άθροισμα των στοιχείων του Κόκκινου είναι \(\mathit{sum\_red} = \mathit{total} - \mathit{sum\_green}\).
Brute force
Θα προσπαθήσουμε να βρούμε το άθροισμα για όλα τα δυνατά τμήματα για την Πράσινη. Θα αναδιατυπώσουμε το πρόβλημα ώστε να δουλεύουμε σε έναν πίνακα αντί σε μία κυκλική λίστα. Δημιουργούμε τον πίνακα \(A\) με \(2N\) στοιχεία, όπου \(A[i + N] = A[i] = x[i]\) (για \(i < N\)). Για παράδειγμα, στο πρώτο αρχείο ειδόσου \(A = \lbrace 7, 5, 1, 3, 8, 9, 11, 8, 7, 5, 1, 3, 8, 9, 11, 8\rbrace\).
Παρατήρηση 2: Όλα τα τμήματα με μήκος μικρότερο ή ίσο από \(N\) αντιστοιχούν σε όλα τα δυνατά τμήματα στην κυκλική λίστα.
Επομένως μπορούμε να δοκιμάσουμε για κάθε δυνατή αρχή \(i < N\), όλα τα δυνατά τέλη \(j\) (όπου \(j < i + N\)), και να υπολογίσουμε το άθροισμα των στοιχείων μεταξύ \(i\) και \(j\). Αυτό θα μας δώσει όλα τα δυνατά αθροίσματα για την Πράσινη. Χρησιμοποιώντας την Παρατήρηση 1, μπορούμε να βρούμε το άθροισμα των στοιχείων του Κόκκινου σε κάθε περίπτωση, άρα και την διαφορά τους.
Υπάρχουν \(N\) δυνατές αρχές, \(\mathcal{O}(N)\) δυνατά τέλη και χρειάζεται \(\mathcal{O}(N)\) χρόνος να βρούμε το άθροισμα των στοιχείων. Άρα ο αλγόριθμος θέλει \(\mathcal{O}(N^3)\) χρόνο και \(\mathcal{O}(N)\) μνήμη.
#include <algorithm>
#include <stdio.h>
const size_t MAXN = 1'000'000;
long A[MAXN * 2];
int main() {
long N;
FILE *fi = fopen("kalanta.in", "r");
fscanf(fi, "%ld", &N);
long total = 0;
for (long i = 0; i < N; ++i) {
fscanf(fi, "%ld", &A[i]);
A[i+N] = A[i];
total += A[i];
}
fclose(fi);
long min_diff = total;
for (long i = 0; i < N; ++i) {
for (long j = i; j < N; ++j) {
long sum = 0;
for (long k = i; k <= j; ++k) {
sum += A[k];
}
long other_sum = total - sum;
min_diff = std::min(min_diff, std::abs(sum - other_sum));
}
}
FILE *fo = fopen("kalanta.out", "w");
fprintf(fo, "%ld\n", min_diff);
fclose(fo);
return 0;
}
Brute force με γρήγορο υπολογισμό αθροισμάτων
Μπορούμε να επιταχύνουμε τον παραπάνω αλγόριθμο με τον ακόλουθο τρόπο. Αν ξέρουμε το άθροισμα \(\mathit{sum}(i, j)\) από \(A[i]\) έως \(A[j]\), τότε το \(\mathit{sum}(i, j + 1) = \mathit{sum}(i, j) + A[j+1]\). Άρα μπορούμε να υπολογίσουμε όλα τα αθροίσματα για τα τμήματα που ξεκινάνε στο \(i\) σε χρόνο \(\mathcal{O}(N)\). Συνεπώς, ο αλγόριθμος χρειάζεται συνολικό χρόνο \(\mathcal{O}(N^2)\).
long min_diff = total;
for (long i = 0; i < N; ++i) {
long sum = 0;
for (long j = i; j < N; ++j) {
sum += A[j];
long other_sum = total - sum;
min_diff = std::min(min_diff, std::abs(sum - other_sum));
}
}
Δυαδική αναζήτηση με prefix sums
Παρατήρηση 3: Ένας από τους δύο (ας υποθέσουμε η Πράσινη), θα έχει άθροισμα μικρότερο ή ίσο με τα μισό συνολικό άθροισμα.
Παρατήρηση 4: Όσο μεγαλύτερο άθροισμα έχει η Πράσινη (πάντα μικρότερο ή ίσο με το μισό συνολικό άθροισμα) τόσο μικρότερη είναι η διαφορά μεταξύ των δύο.
Αυτές οι δύο παρατηρήσεις είναι απλές, αλλά βεβαιωθείτε ότι καταλαβαίνετε γιατί ισχύουν. Χρησιμοποιώντας την Παρατήρηση 4, θα προσπαθήσουμε για κάθε δυνατή αρχή του τμήματος της Πράσινης \(i\) να βρούμε το \(j\) που θα μεγιστοποιήσει το άθροισμά της.
Παρατήρηση 5: Όσο μεγαλύτερο είναι το \(j\) τόσο μεγαλύτερο είναι το άθροισμα (αφού οι αριθμοί είναι θετικοί).
Χρησιμοποιώντας την Παρατήρηση 5, μπορούμε να κάνουμε δυαδική αναζήτηση στην απάντηση. Δηλαδή για κάθε \(i\) ψάχνουμε το μεγαλύτερο \(j\) ώστε \(\mathit{sum}(i, j) \leq \mathit{total} / 2\). Μένει να βρούμε έναν αποδοτικό τρόπο να υπολογίζουμε το \(\mathit{sum}(i, j)\). Μπορούμε να το κάνουμε αυτό με prefix sums. Δηλαδή, κρατάμε έναν πίνακα \(\mathit{prefix\_sum}[i] = \sum_{k = 0}^i A[i]\). Αυτός μπορεί να υπολογιστεί αποδοτικά χρησιμοποιώντας ότι \(\mathit{prefix\_sum}[i] = \mathit{prefix\_sum}[i - 1] + A[i]\). Τέλος, το \(\mathit{sum}(i, j) = \mathit{prefix\_sum}[i] - \mathit{prefix\_sum}[j - 1]\) (στον κώδικα παρακάτω οι δείκτες ξεκινάνε από \(1\), και \(\mathit{prefix\_sum}[0] = 0\)).
Ο αλγόριθμος χρειάζεται μία δυαδική αναζήτηση για κάθε δυνατή αρχή, άρα χρειάζεται συνολικά \(\mathcal{O}(N\log{N})\) χρόνο και \(\mathcal{O}(N)\) μνήμη.
#include <algorithm>
#include <stdio.h>
const size_t MAXN = 1'000'000;
long A[MAXN * 2 + 2];
long prefix_sum[MAXN * 2 + 2];
int main() {
long N;
FILE *fi = fopen("kalanta.in", "r");
fscanf(fi, "%ld", &N);
for (long i = 1; i <= N; ++i) {
fscanf(fi, "%ld", &A[i]);
A[i+N] = A[i];
}
fclose(fi);
// Υπολογισμός των prefix sums.
for (long i = 1; i <= 2 * N; ++i) {
prefix_sum[i] = A[i] + prefix_sum[i - 1];
}
long total = prefix_sum[N];
long min_diff = total;
long target = total / 2;
// Βρίσκουμε το μεγαλύτερο άθροισμα (μικρότερο ή ίσο από total/2)
// για κάθε δυνατή αρχή i.
for (long i = 1; i <= N; ++i) {
// Δυαδική αναζήτηση στην απάντηση.
long st = i, en = i + N -1;
while (st < en) {
long md = (st + en + 1) / 2;
long sum = prefix_sum[md] - prefix_sum[i - 1];
if (sum > target) en = md - 1;
else st = md;
}
// Υπολογίζουμε τη διαφορά.
long sum = prefix_sum[st] - prefix_sum[i - 1];
long other_sum = total - sum;
min_diff = std::min(min_diff, std::abs(sum - other_sum));
}
FILE *fo = fopen("kalanta.out", "w");
fprintf(fo, "%ld\n", min_diff);
fclose(fo);
return 0;
}
Βέλτιστη λύση
Μπορούμε να επιταχύνουμε ακόμα παραπάνω τη λύση, χρησιμοποιώντας την τεχνική των δύο δεικτών.
Παρατήρηση 6: Αν το τμήμα που ξεκινάει στο \(i\) έχει το \(j\) ως το μεγαλύτερο τέλος διαστήματος με \(\mathit{sum}(i, j) \leq \mathit{total} / 2\), τότε το \(i+1\), θα έχει ένα \(j' \geq j\).
Για κάθε \(i\) κρατάμε την μεγαλύτερη θέση \(j\) και στη μεταβλητή \(\mathit{sum} = \mathit{sum}(i, j)\). Έπειτα αυξάνουμε την θέση \(j\) ώσπου να βρούμε την μεγαλύτερη θέση \(j'\) για το \(i+1\). Μπορούμε να βρούμε το άθροισμα \(\mathit{sum}(i + 1, j')\), αφαιρώντας το στοιχείο \(A[i]\) και προσθέτοντας τα στοιχεία \(A[j+1], \ldots , A[j']\).
Αφού το \(j\) μπορεί να αυξηθεί το πολύ \(2N\) φορές ο αλγόριθμος χρειάζεται \(\mathcal{O}(N)\) χρόνο και \(\mathcal{O}(N)\) μνήμη.
#include <algorithm>
#include <stdio.h>
const size_t MAXN = 1000000;
long A[MAXN * 2 + 2];
int main() {
long N;
FILE *fi = fopen("kalanta.in", "r");
fscanf(fi, "%ld", &N);
long total = 0;
for (long i = 1; i <= N; ++i) {
fscanf(fi, "%ld", &A[i]);
A[i+N] = A[i];
total += A[i];
}
fclose(fi);
long min_diff = total;
long target = total / 2;
long j = 1;
long sum = 0;
// Βρίσκουμε το μεγαλύτερο άθροισμα (μικρότερο ή ίσο από total/2)
// για κάθε δυνατή αρχή i.
for (long i = 1; i <= N; ++i) {
sum -= A[i - 1];
// Το j μπορεί να αυξηθεί το πολύ 2N φορές.
while (j < i + N && sum + A[j] <= target) {
sum += A[j];
++j;
}
long other_sum = total - sum;
min_diff = std::min(min_diff, std::abs(sum - other_sum));
}
FILE *fo = fopen("kalanta.out", "w");
fprintf(fo, "%ld\n", min_diff);
fclose(fo);
return 0;
}
Σημείωση 1: Δεν χρειάζεται να έχουμε το κάθε στοιχείο δύο φορές στη μνήμη. Μπορούμε να ορίσουμε την παρακάτω συνάρτηση,
long a[MAXN + 1];
long N;
long A(long i) {
if (i <= N) return a[i];
return a[i - N];
}
και να αντικαταστήσουμε όλες τις χρήσεις A[xx] με A(xx). Θα βρείτε ολόκληρο τον κώδικα εδώ.
Σημείωση 2: Αν θέλουμε να διαβάσουμε το αρχείο εισόδου παραπάνω από μία φορές (που στην πράξη δεν είναι πολύ αποδοτικό), τότε μπορούμε να λύσουμε το πρόβλημα σε \(\mathcal{O}(N)\) χρόνο και \(\mathcal{O}(1)\) μνήμη (δείτε εδώ για παράδειγμα).