26ος ΠΔΠ Γ' Φάση: Άθροισμα ζευγών (sumpair) - Λύση
Brute force λύση \(\mathcal{O}(N^2Q)\)
Η πιο απλή λύση είναι για κάθε ερώτημα, να διατρέξουμε όλα τα δυνατά ζεύγη στοιχείων του πίνακα και να δούμε αν έχουν το ζητούμενο άθροισμα.
Κάθε ερώτημα παίρνει \(\mathcal{O}(N^2)\) χρόνο, άρα ο αλγόριθμος χρειάζεται \(\mathcal{O}(N^2Q)\) χρόνο και \(\mathcal{O}(N)\) μνήμη.
#include <cstdio>
const size_t MAXN = 1'000'000;
long A[MAXN];
long N, Q;
bool doesPairExist(long target) {
for (long i = 0; i < N; ++i) {
for (long j = i + 1; j < N; ++j) {
if (A[i] + A[j] == target) {
return true;
}
}
}
return false;
}
int main() {
FILE *fi = fopen("sumpair.in", "r");
fscanf(fi, "%ld %ld", &N, &Q);
for (long i = 0; i < N; ++i) {
fscanf(fi, "%ld", &A[i]);
}
FILE *fo = fopen("sumpair.out", "w");
for (long j = 0; j < Q; ++j) {
long target;
fscanf(fi, "%ld", &target);
fprintf(fo, "%s\n", doesPairExist(target) ? "true" : "false");
}
return 0;
}
Λύση με set \(\mathcal{O}(Q N \log N)\)
Στην παραπάνω λύση ψάχνουμε για κάθε \(A[i]\), αν υπάρχει \(A[j]\) ώστε \(A[i] + A[j] = \mathit{target}\). Άρα ψάχνουμε για κάθε \(A[i]\), αν υπάρχει στοιχείο \(A[j] = \mathit{target} - A[i]\).
Η δομή δεδομένων set μπορεί να μας βοηθήσει να απαντήσουμε τέτοιες ερωτήσεις σε χρόνο \(\mathcal{O}(\log N)\), αφού πρώτα βάλουμε προσθέσουμε όλα τα στοιχεία σε χρόνο \(\mathcal{O}(N \log N)\).
Ένα σημείο που θέλει προσοχή είναι ότι δεν πρέπει να χρησιμοποιήσουμε το ίδιο στοιχείο δύο φορές, πχ \(15 + 15 = 30\) στο παράδειγμα. Για να το αποφύγουμε αυτό κρατάμε ένα set από τα στοιχεία που εμφανίζονται τουλάχιστον δύο φορές.
Σημείωση: Αν χρησιμοποιήσουμε unordered_set τότε η μέση πολυπλοκότητα γίνεται \(\mathcal{O}(NQ)\).
#include <cstdio>
#include <set>
const size_t MAXN = 1'000'000;
std::set<long> s, has_duplicate;
long A[MAXN];
long N, Q;
bool doesPairExist(long target) {
for (long i = 0; i < N; ++i) {
if (2 * A[i] == target) {
if (has_duplicate.find(A[i]) != has_duplicate.end())
return true;
} else {
if (s.find(target - A[i]) != s.end()) {
return true;
}
}
}
return false;
}
int main() {
FILE *fi = fopen("sumpair.in", "r");
fscanf(fi, "%ld %ld", &N, &Q);
for (long i = 0; i < N; ++i) {
fscanf(fi, "%ld", &A[i]);
if (s.find(A[i]) != s.end()) {
has_duplicate.insert(A[i]);
}
s.insert(A[i]);
}
FILE *fo = fopen("sumpair.out", "w");
for (long j = 0; j < Q; ++j) {
long target;
fscanf(fi, "%ld", &target);
fprintf(fo, "%s\n", doesPairExist(target) ? "true" : "false");
}
return 0;
}
Λύση με δύο δείκτες \(\mathcal{O}(N \log N + Q N)\)
Η βέλτιστη λύση είναι να ταξινομήσουμε τον πίνακα και να διατηρούμε δύο δείκτες \(lo\) και \(hi\), ώστε \([lo, hi]\) να έχει όλα τα δυνατά ζεύγη που έχουν άθροισμα \(\mathit{target}\).
Παρατήρηση 1: Αν \(A[\mathit{lo}] + A[\mathit{hi}] > \mathit{target}\), τότε το στοιχείο \(A[\mathit{hi}]\) δεν μπορεί να είναι σε κανένα ζεύγος με άθροισμα \(\mathit{target}\).
Απόδειξη Από την υπόθεση, όλα τα ζεύγη με άθροισμα \(\mathit{target}\) είναι στο \([\mathit{lo}, \mathit{hi}]\). Άρα για \(i \in [\mathit{lo}, \mathit{hi}]\), \(A[i] + A[\mathit{hi}] \geq A[\mathit{lo}] + A[\mathit{hi}] > \mathit{target}\).
Παρατήρηση 2: Αντίστοιχα, αν \(A[\mathit{lo}] + A[\mathit{hi}] < \mathit{target}\), τότε το στοιχείο \(A[\mathit{lo}]\) δεν μπορεί να είναι σε κανένα ζεύγος με άθροισμα \(\mathit{target}\), γιατί \(A[\mathit{lo}] + A[i] \leq A[\mathit{lo}] + A[\mathit{hi}] < target\).
Αυτές οι παρατηρήσεις μας οδηγούν στον αλγόριθμο όπου αφαιρούμε είτε την αρχή είτε το τέλος από το διάστημα \([\mathit{lo}, \mathit{hi}]\) βάσει του \(Α[\mathit{lo}] + Α[\mathit{hi}]\), μέχρι να βρούμε ένα καλό ζεύγος ή να είναι άδειο το διάστημα. Αφού σε κάθε επανάληψη το μήκος του διαστήματος μικραίνει κατά \(1\), κάθε ερώτημα χρειάζεται \(\mathcal{O}(N)\) χρόνο. Άρα ο αλγόριθμος έχει πολυπλοκότητα \(\mathcal{O}(N \log N + Q N)\) και μνήμη \(\mathcal{O}(N)\).
#include <algorithm>
#include <cstdio>
const size_t MAXN = 1'000'000;
long A[MAXN];
long N, Q;
bool doesPairExist(long target) {
long lo = 0, hi = N - 1;
while (lo < hi) {
long sum = A[lo] + A[hi];
if (sum == target) return true;
else if (sum > target) --hi;
else ++lo;
}
return false;
}
int main() {
FILE *fi = fopen("sumpair.in", "r");
fscanf(fi, "%ld %ld", &N, &Q);
for (long i = 0; i < N; ++i) {
fscanf(fi, "%ld", &A[i]);
}
std::sort(A, A+N);
FILE *fo = fopen("sumpair.out", "w");
for (long j = 0; j < Q; ++j) {
long target;
fscanf(fi, "%ld", &target);
fprintf(fo, "%s\n", doesPairExist(target) ? "true" : "false");
}
return 0;
}