25ος ΠΔΠ Γ' Φάση: Ήχοι και σιωπές (sound) - Λύση
Επεξήγηση εκφώνησης
Το πρόβλημα μας ζητάει να βρούμε σε πόσα διαστήματα μήκους \(M\) η διαφορά της μέγιστης και της ελάχιστης τιμής είναι μικρότερη ή ίση του \(C\).
Brute force λύση
Υπάρχουν \(N-M+1\) διαστήματα μεγέθους \(M\), κάθε ένα της μορφής \([i, i+M)\) για \(i=0, \ldots , N-M\). Για κάθε ένα από αυτά υπολογίζουμε την μέγιστη και την ελάχιστη τιμή διατρέχοντας όλα τα στοιχεία του διαστήματος σε χρόνο \(\mathcal{O}(M)\).
Συνεπώς ο αλγόριθμος χρειάζεται χρόνο \(\mathcal{O}(N\cdot M)\) και μνήμη \(\mathcal{O}(N)\).
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
const size_t MAXN = 1'000'000;
long a[MAXN];
long N, M, C;
long findMaxDiffInInterval(long st, long en) {
long max_val = a[st], min_val = a[st];
for (long i = st; i < en; ++i) {
max_val = std::max(max_val, a[i]);
min_val = std::min(min_val, a[i]);
}
return max_val - min_val;
}
int main() {
FILE *fi = fopen("sound.in", "r");
fscanf(fi, "%ld%ld%ld", &N, &M, &C);
for (long i = 0; i < N; ++i) {
fscanf(fi, "%ld", &a[i]);
}
fclose(fi);
FILE *fo = fopen("sound.out", "w");
bool found = false;
for (long i = 0; i + M <= N; ++i) {
long diff = findMaxDiffInInterval(i, i + M);
if (diff <= C) {
fprintf(fo, "%ld\n", i + 1);
found = true;
}
}
if (!found) {
fprintf(fo, "NULL\n");
}
fclose(fo);
return 0;
}
Λύση με set
Μπορούμε να επιταχύνουμε την παραπάνω λύση βρίσκοντας το ελάχιστο και το μέγιστο για τα διαστήματα \([0, M)\), \([1, M+1)\), \(\ldots\) με τη σειρά. Ας δούμε πώς βρίσκουμε γρήγορα το ελάχιστο και με παρόμοια λογική μπορούμε να βρούμε και το μέγιστο.
Κρατάμε ένα set \(\mathit{min\_set}\) με στοιχεία \((a[x], x)\). Όταν επεξεργαζόμαστε το διάστημα \([i, i+M)\), το \(\mathit{min\_set}\) μας δίνει το ελάχιστο στοιχείο, αλλά μπορεί αυτό να αντιστοιχεί σε στοιχείο \((a[j], j)\) με \(j < i\) (δηλαδή εκτός διαστήματος). Κάθε τέτοιο στοιχείο που συναντάμε μπορούμε να το αφαιρέσουμε αφού δεν μπορεί να είναι το ελάχιστο για τα επόμενα διαστήματα. Αφαιρώντας στοιχεία, κάποια στιγμή θα βρούμε ένα στοιχείο που ανήκει στο διάστημα \([i, i+M)\). Αφού βρούμε το ελάχιστο προσθέτουμε το στοιχείο \((a[i+M], i+M)\) και συνεχίζουμε με το επόμενο διάστημα (αν υπάρχει).
Κάθε στοιχείο θα προστεθεί μία φορά και θα αφαιρεθεί το πολύ μία φορά. Αφού κάθε πράξη στο set θέλει χρόνο \(\mathcal{O}(\log{N})\), ο αλγόριθμος θέλει συνολικό χρόνο \(\mathcal{O}(N\log{N})\) και μνήμη \(\mathcal{O}(N)\).
#include <algorithm>
#include <set>
#include <stdio.h>
#include <stdlib.h>
const size_t MAXN = 1'000'000;
long a[MAXN];
long N, M, C;
struct Item {
long idx;
long value;
Item(long idx, long value) : idx(idx), value(value) { }
bool operator<(const Item& other) const {
if (value == other.value) return idx < other.idx;
return value < other.value;
}
};
std::set<Item> min_set;
std::set<Item> max_set;
long extractMax(long idx) {
while (max_set.rbegin()->idx < idx - M + 1) max_set.erase(std::prev(max_set.end()));
return max_set.rbegin()->value;
}
long extractMin(long idx) {
while (min_set.begin()->idx < idx - M + 1) min_set.erase(min_set.begin());
return min_set.begin()->value;
}
int main() {
FILE *fi = fopen("sound.in", "r");
fscanf(fi, "%ld%ld%ld", &N, &M, &C);
for (long i = 0; i < N; ++i) {
fscanf(fi, "%ld", &a[i]);
}
fclose(fi);
// Αρχικοποιούμε τα sets για τα πρώτα M-1 στοιχεία.
for (long i = 0; i < M - 1; ++i) {
min_set.insert(Item(i, a[i]));
max_set.insert(Item(i, a[i]));
}
FILE *fo = fopen("sound.out", "w");
bool found = false;
for (long i = M - 1; i < N; ++i) {
min_set.insert(Item(i, a[i]));
max_set.insert(Item(i, a[i]));
if (extractMax(i) - extractMin(i) <= C) {
found = true;
fprintf(fo, "%ld\n", i - M + 2);
}
}
if (!found) {
fprintf(fo, "NULL\n");
}
fclose(fo);
return 0;
}
Λύση με μονότονη ουρά
Παρατήρηση: Αν βάλουμε μία τιμή \((a[i], i)\) στο \(min\_set\) τότε όλες οι \((a[j], j)\) με \(j<i\) και \(a[i] \leq a[j]\), δεν μπορούν ποτέ να είναι το ελάχιστο των επόμενων διαστημάτων.
Με αυτή την παρατήρηση, τροποποιούμε τον παραπάνω αλγόριθμο ώστε να κρατάμε deque1 αντί για set. Για το ελάχιστο κρατάμε τα στοιχεία με αύξον \(i\) και αύξον \(a[i]\). Όταν πηγαίνουμε από το διάστημα \([i, i+M)\) στο \([i+1, i+M+1)\), αφαιρούμε από το πίσω μέρος της deque όλα τα στοιχεία που έχουν λήξει (δηλαδή πιθανώς το \(a[i]\)) και προσθέτουμε το \(a[i+M]\). Όταν προσθέσουμε το \(a[i+M]\) πρέπει να διατηρήσουμε την μονοτονία επομένως αφαιρούμε από μπροστά όλα τα στοιχεία που είναι μεγαλύτερα από το \(a[i]\) (αφού από την παραπάνω παρατήρηση δεν θα είναι ποτέ ελάχιστα). Το πίσω πίσω στοιχείο είναι το ελάχιστο του διαστήματος.
Για το παράδειγμα, η deque για το ελάχιστο αλλάζει ως εξής:
| Deque | Σχόλια | Ελάχιστο |
|---|---|---|
| (0, 0) (1, 1) | Αρχική κατάσταση σε αύξουσα σειρά θέσης | 0 |
| Αφαιρούμε το (0, 0) επειδή είναι εκτός διαστήματος και το (1,1) επειδή δεν θα είναι ποτέ ελάχιστο | 1 | |
| (2, 1) (3, 2) | Απλά προσθέτουμε το καινούργιο | 1 |
| Αφαιρούμε το (2, 1) επειδή είναι εκτός διαστήματος | 2 | |
| Αφαιρούμε το (3, 2) επειδή είναι εκτός διαστήματος και το (4, 3) επειδή δεν θα είναι ποτέ ελάχιστο | 2 | |
| Αφαιρούμε το (5, 2) επειδή δεν θα είναι ποτέ ελάχιστο | 2 |
Αφού κάθε στοιχείο προστίθεται και αφαιρείται μία φορά, ο αλγόριθμος χρειάζεται συνολικά \(\mathcal{O}(N)\) χρόνο και \(\mathcal{O}(N)\) μνήμη.
#include <algorithm>
#include <deque>
#include <stdio.h>
#include <stdlib.h>
const size_t MAXN = 1'000'000;
long a[MAXN];
long N, M, C;
struct Item {
long idx;
long value;
Item(long idx, long value) : idx(idx), value(value) { }
};
std::deque<Item> min_deque;
std::deque<Item> max_deque;
void insertToDeques(long i, long value) {
Item item(i, value);
while (!min_deque.empty() && value <= min_deque.front().value) min_deque.pop_front();
min_deque.push_front(item);
while (!max_deque.empty() && value >= max_deque.front().value) max_deque.pop_front();
max_deque.push_front(item);
}
int main() {
FILE *fi = fopen("sound.in", "r");
fscanf(fi, "%ld%ld%ld", &N, &M, &C);
for (long i = 0; i < N; ++i) {
fscanf(fi, "%ld", &a[i]);
}
fclose(fi);
// Αρχικοποιούμε τις deques για τα πρώτα M-1 στοιχεία.
for (long i = 0; i < M - 1; ++i) {
insertToDeques(i, a[i]);
}
FILE *fo = fopen("sound.out", "w");
bool found = false;
for (long i = M - 1; i < N; ++i) {
// Αφαιρούμε όλα τα παλιά στοιχεία.
if (min_deque.back().idx < i - M + 1) min_deque.pop_back();
if (max_deque.back().idx < i - M + 1) max_deque.pop_back();
insertToDeques(i, a[i]);
if (max_deque.back().value - min_deque.back().value <= C) {
found = true;
fprintf(fo, "%ld\n", i - M + 2);
}
}
if (!found) {
fprintf(fo, "NULL\n");
}
fclose(fo);
return 0;
}
-
Δομή δεδομένων που υποστηρίζει
push_front,push_back,pop_frontκαιpop_backσε \(\mathcal{O}(1)\) χρόνο. ↩