24ος ΠΔΠ B' Φάση: Τελεστικοί ενισχυτές (operators) - Λύση
Brute force λύση
Πρέπει να βρούμε ένα ζεύγος ακεραίων της ακολουθίας ώστε το άθροισμά τους να έχει την ελάχιστη δυνατή απόλυτη τιμή. Πρέπει στη συνέχεια να τυπώσουμε στην έξοδο τους δύο αυτούς αριθμούς σε αύξουσα σειρά.
Ένας τρόπος να λύσουμε αυτό το πρόβλημα είναι δοκιμάζοντας όλα τα πιθανά ζεύγη θέσεων της ακολουθίας, την οποία μπορούμε να έχουμε αποθηκεύσει σε έναν πίνακα, έστω \(A\). Αυτό μπορεί να γίνει με δύο εμφωλευμένα for loops, έστω με μεταβλητές \(i\) και \(j\). Αρκεί να εξετάσουμε μόνο τις περιπτώσεις όπου \(i < j\), αφού οι υπόλοιπες αποτελούν επαναλήψεις τους. Μπορούμε στη μεταβλητή \(\mathrm{mn}\) να διατηρούμε το ελάχιστο μέτρο αθροίσματος που έχουμε συναντήσει μέχρι στιγμής, ενώ στις μεταβλητές \(\mathrm{mn\_i}\) και \(\mathrm{mn\_j}\) μπορούμε να αποθηκεύουμε τις θέσεις των ακεραίων που παρήγαγαν το ελάχιστο αυτό μέτρο αθροίσματος. Η μεταβλητή \(\mathrm{mn}\) μπορεί να αρχικοποιηθεί σε \(2 \cdot 10^9 + 1\) ώστε σύμφωνα με τους περιορισμούς εισόδου να ενημερωθεί στην πρώτη κιόλας επανάληψη. Γενικά η μεταβλητή θα ενημερώνεται όταν βρίσκουμε μικρότερο μέτρο αθροίσματος, δηλαδή όταν \(\lvert A_{i} + A_{j} \rvert < \mathrm{mn}\), οπότε θα θέτουμε και \(\mathrm{mn\_i} = i\) και \(\mathrm{mn\_j} = j\). Το αποτέλεσμα που θα εκτυπώσουμε θα είναι οι ακέραιοι της ακολουθίας \(A_{\mathrm{mn\_i}}\) και \(A_{\mathrm{mn\_j}}\) με τη σειρά αυτή.
Επειδή εξετάζουμε \(\mathcal{O}(N^2)\) ζεύγη ακεραίων η χρονική πολυπλοκότητα του αλγορίθμου είναι \(\mathcal{O}(N^2)\). Η πολυπλοκότητα αυτή δε μας επιτρέπει να περάσουμε όλα τα testcases, ωστόσο θα περάσει τουλάχιστον τα μισά σύμφωνα με τη σημείωση της εκφώνησης. Λόγω της αποθήκευσης της ακολουθίας ακεραίων στον πίνακα \(A\) η χωρική πολυπλοκότητα είναι \(\mathcal{O}(N)\).
#include <cstdio>
#include <algorithm>
using namespace std;
const long MAXN = 1000005;
long A[MAXN];
int main() {
freopen("operators.in", "r", stdin);
freopen("operators.out", "w", stdout);
long N;
scanf("%ld", &N);
// Διάβασμα ακολουθίας ακεραίων
for (long i = 0; i < N; i++) {
scanf("%ld", &A[i]);
}
// Δήλωση βοηθητικών μεταβλητών
long mn = 2 * 1000 * 1000 * 1000 + 1, mn_i, mn_j;
// Έλεγχος όλων των ζευγών ακεραίων της ακολουθίας
for (long i = 0; i < N; i++) {
for (long j = i + 1; j < N; j++) {
// Υπολογισμός μέτρου αθροίσματος τρέχοντος ζεύγους
long cur_abs_sum = abs(A[i] + A[j]);
// Έλεγχος για ελάχιστο
if (cur_abs_sum < mn) {
// Ενημέρωση αποτελεσμάτων σε περίπτωση ελαχίστου
mn = cur_abs_sum;
mn_i = i;
mn_j = j;
}
}
}
printf("%ld %ld\n", A[mn_i], A[mn_j]);
return(0);
}
Καλύτερη λύση με δυαδική αναζήτηση
Μπορούμε να βελτιώσουμε την ταχύτητα του αλγορίθμου μας εάν κάνουμε μία απλή παρατήρηση.
Παρατήρηση: Αν όλοι οι αριθμοί είναι μόνο θετικοί ή μόνο αρνητικοί το αποτέλεσμα είναι οι δύο πρώτοι ή οι δύο τελευταίοι αντίστοιχα. Διαφορετικά για κάθε ακέραιο της ακολουθίας δε χρειάζεται να ελέγξουμε όλους τους υπόλοιπους, αλλά αρκεί να ελέγχουμε αν υπάρχει ο αντίθετός του στην ακολουθία (οπότε αυτοί αποτελούν την απάντηση) και αν δεν υπάρχει να εξατάζουμε τους ακεραίους που θα περιέβαλλαν τον αντίθετό του εάν υπήρχε στην ακολουθία.
Ο εντοπισμός του αντιθέτου ή των γειτόνων του για κάθε μη μηδενικό ακέραιο, έστω \(K\), μπορεί να γίνει με δυαδική αναζήτηση πάνω στη συνθήκη \(A_{i} \geq -K\) με το \(i\) να είναι η μεταβλητή της δυαδικής αναζήτησης και να παίρνει τιμές στο διάστημα ακεραίων \([0, N - 1]\). Αυτή μπορεί να γίνει εύκολα με χρήση της συνάρτησης lower_bound από τη βιβλιοθήκη algorithm. Βέβαια απαιτείται και ο έλεγχος για το εάν έχουμε \(1\) ή \(2\) γείτονες. Να σημειώσουμε ότι οι δυαδικές αναζητήσεις δεν απαιτούν ταξινόμηση της ακολουθίας, αφού αυτή δίνεται ήδη ταξινομημένη σε αύξουσα σειρά.
Ο αλγόριθμος αυτός πραγματοποιεί \(\mathcal{O}(N)\) δυαδικές αναζητήσεις κάθε μία από τις οποίες απαιτεί χρόνο \(\mathcal{O}(\log{N})\), επομένως η πολυπλοκότητα του αλγρίθμου είναι \(\mathcal{O}(N\log{N})\). Η λύση αυτή είναι αρκετά γρήγορη για να περάσει όλα τα testcases. Η χωρική πολυπλοκότητα είναι \(\mathcal{O}(N)\).
#include <cstdio>
#include <algorithm>
using namespace std;
const long MAXN = 1000005;
long A[MAXN];
int main() {
freopen("operators.in", "r", stdin);
freopen("operators.out", "w", stdout);
long N;
scanf("%ld", &N);
// Διάβασμα ακολουθίας ακεραίων
for (long i = 0; i < N; i++) {
scanf("%ld", &A[i]);
}
// Έλεγχος για το αν έχουμε μόνο θετικούς ή μόνο αρνητικούς ακεραίους
if (A[0] > 0) {
printf("%ld %ld\n", A[0], A[1]);
return(0);
}
else if (A[N - 1] < 0) {
printf("%ld %ld\n", A[N - 2], A[N - 1]);
return(0);
}
// Δήλωση βοηθητικών μεταβλητών
long mn = 2 * 1000 * 1000 * 1000 + 1, mn_1, mn_2;
for (long i = 0; i < N; i++) {
long K = A[i];
long a, b;
if (K) {
// Εντοπισμός γειτόνων αντιθέτου με δυαδική αναζήτηση
long pos = lower_bound(A, A + N - 1, -K) - A;
if (pos < N && A[pos] == -K) {
printf("%ld %ld\n", min(K, -K), max(K, -K));
return(0);
}
a = pos - 1;
b = pos;
}
else {
// ’μεσος προσδιορισμός γειτόνων
a = i - 1;
b = i + 1;
}
// Προσαρμογή γειτόνων
if (a == i || a == -1)
a++;
if (b == i || b == N)
b--;
// Ενημέρωση αποτελεσμάτων σε περίπτωση ελαχίστου
if (abs(K + A[a]) < mn) {
mn = abs(K + A[a]);
mn_1 = i;
mn_2 = a;
}
if (abs(K + A[b]) < mn) {
mn = abs(K + A[b]);
mn_1 = i;
mn_2 = b;
}
}
printf("%ld %ld\n", min(A[mn_1], A[mn_2]), max(A[mn_1], A[mn_2]));
return(0);
}
Βέλτιστη λύση με two pointers
Από τη στιγμή που η ακολουθία είναι ήδη ταξιμομημένη, η επίλυση του προβλήματος κάνοντας χρήση της μεθόδου των two pointers μπορεί να επιτύχει ακόμα μικρότερη πολυπλοκότητα. Θα δείξουμε τώρα πώς μπορούμε να εφαρμόσουμε τη μέθοδο αυτή. Θεωρούμε δύο μεταβλητές-δείκτες, έστω \(i\) και \(j\), με την πρώτη να είναι αρχικοποιημένη σε \(0\) και τη δεύτερη σε \(N - 1\). Μπορούμε να κάνουμε την ακόλουθη παρατήρηση.
Παρατήρηση: Αν σε μία φάση της εκτέλεσης η μεταβλητή \(j\) έχει επιλεγεί κατάλληλα ώστε η τιμή \(\lvert A_{i} + A_{j}\rvert\) να είναι ελάχιστη για δεδομένο \(i\), τότε αν αυξήσουμε το \(i\) το αποτέλεσμα δε θα μπορεί να βελτιωθεί με αύξηση και του \(j\). Με άλλα λόγια \(\lvert A_{i'}+A_{j} \rvert \le \lvert A_{i'}+A_{j'} \rvert\) για οποιαδήποτε \(i'>i\) και \(j'>j\).
(Απόδειξη): Παρατηρούμε ότι \(A_{i}+A_{j'}\ge 0\). Αυτό διότι είτε \(A_{i}+A_{j}\ge 0\) (οπότε προκύπτει άμεσα), είτε \(A_{i}+A_{j} < 0\). Στη δεύτερη περίπτωση όμως, αν ήταν και \(A_{i}+A_{j'}<0\), το \(j'\) θα ήταν καλύτερο επιλογή από το \(j\) για το δεδομένο \(i\). Επομένως έχουμε:
\(\lvert A_{i'}+A_{j} \rvert = \lvert A_{i} + (A_{i'}-A_{i}) + A_{j} \rvert \leq \lvert A_{i'}-A_{i} \rvert + \lvert A_{i}+A_{j} \rvert\) (λόγω τριγωνικής ανισότητας)
\(= A_{i'} - A_{i} + \lvert A_{i}+A_{j} \rvert\) (αφού \(i'>i\) και ο πίνακας είναι σε αύξουσα σειρά)
\(\le A_{i'} - A_{i} + \lvert A_{i}+A_{j'} \rvert\) (λόγω υπόθεσης περί βέλτιστου \(j\) για το δεδομένο \(i\))
\(= A_{i'} - A_{i} + A_{i} + A_{j'}\) (λόγω παρατήρησης)
\(= A_{i'} + A_{j'} \le \lvert A_{i'} + A_{j'} \rvert\) \(\\)
Μπορούμε λοιπόν καθώς αυξάνουμε το \(i\) να μειώνουμε το \(j\) όποτε απαιτείται για να διατηρούμε το μέτρο ελάχιστο για κάθε \(i\), όσο \(i < j\).
Επειδή η τιμή του \(i\) μπορεί να αυξηθεί \(\mathcal{O}(N)\) φορές και του \(j\) να μειωθεί \(\mathcal{O}(N)\) φορές, η χρονική πολυπλοκότητα του αλγορίθμου two pointers είναι \(\mathcal{O}(N)\). Η πολυπλοκότητα αυτή είναι η βέλτιστη δυνατή και η λύση μας περνάει όλα τα testcases. Η χωρική πολυπλοκότητα είναι \(\mathcal{O}(N)\).
#include <cstdio>
#include <algorithm>
using namespace std;
const long MAXN = 1000005;
long A[MAXN];
int main() {
freopen("operators.in", "r", stdin);
freopen("operators.out", "w", stdout);
long N;
scanf("%ld", &N);
// Διάβασμα ακολουθίας ακεραίων
for (long i = 0; i < N; i++) {
scanf("%ld", &A[i]);
}
// Δήλωση βοηθητικών μεταβλητών
long mn = 2 * 1000 * 1000 * 1000 + 1, mn_i, mn_j;
// Αρχικοποίηση μεταβλητής-δείκτη
long j = N - 1;
for (long i = 0; i < j; i++) {
// Υπολογισμός βέλτιστου j με i < j
while (j > i + 1 && abs(A[i] + A[j - 1]) < abs(A[i] + A[j])) {
j--;
}
// Έλεγχος για ελάχιστο
if (abs(A[i] + A[j]) < mn) {
mn = abs(A[i] + A[j]);
mn_i = i;
mn_j = j;
}
}
printf("%ld %ld\n", A[mn_i], A[mn_j]);
return(0);
}