23ος ΠΔΠ B' Φάση: Χιονοδρομίες στα «Τρία-Πέντε Πηγάδια» (snow_run) - Λύση
Σημείωση: Το πρόβλημα είχε πολύ χαλαρά όρια οπότε περνούσαν ακόμα και οι brute force προσεγγίσεις. Παρόλα αυτά, θα παρουσιάσουμε και καλύτερες λύσεις που θα δούλευαν για μεγαλύτερα input.
1η λύση με Brute force
Πρέπει δοθείσας της κατάταξης του κάθε χιονοδρόμου τη στιγμή που τερμάτισε να συμπεράνουμε την τελική του κατάταξη.
Μπορούμε να λύσουμε αυτό το πρόβλημα προσομοιώνοντας τη διαδικασία τερματισμών. Συγκεκριμένα η κατάταξη κάθε δρομέα θα θεωρείται αρχικά ίση με αυτήν της στιγμής που τερμάτισε. Στη συνέχεια, όποτε θα συναντάμε κάποιο που όταν τερμάτισε είχε μικρότερη ή ίση κατάταξη από αυτή του υπό εξέταση δρομέα θα αυξάνουμε κατά \(1\) την τελική κατάταξή του υπό εξέταση δρομέα.
Για να το κάνουμε αυτό μπορούμε να χρησιμοποιήσουμε δύο εμφωλευμένα for loops, έστω με μεταβλητές \(i\) και \(j\). Επίσης θα χρειαστούμε έναν πίνακα, έστω \(A\), στον οποίο θα διατηρούμε την τελική κατάταξη του κάθε δρομέα με βάση τα μέχρι στιγμής δεδομένα. Αρχικά για κάθε δρομέα \(i\) η τελική του κατάταξη θα αρχικοποιείται στην κατάταξή του τη στιγμή που τερμάτισε και θα αυξάνεται κατά \(1\) η κατάταξη κάθε προηγούμενου δρομέα (\(j < i\)) που μέχρι τώρα θεωρούνταν ότι είχε την ίδια ή χειρότερη τελική κατάταξη (\(A[j] \geq A[i]\)).
Λόγω των δύο εμφωλευμένων for loops που διατρέχουν τον πίνακα \(A\), η χρονική πολυπλοκότητα αυτού του αλγορίθμου είναι \(\mathcal{O}(N^2)\). Η πολυπλοκότητα αυτή είναι επαρκής για τα testcases (\(N \leq 40.000\)), αλλά θα προτείνουμε και καλύτερες λύσεις. Η χωρική πολυπλοκότητα είναι \(\mathcal{O}(N)\) καθώς πρέπει να αποθηκεύσουμε τις εκτιμώμενες τελικές κατατάξεις (πίνακας \(A\)).
#include <cstdio>
using namespace std;
const long MAXN = 100005;
long A[MAXN];
int main() {
freopen("snow_run.in", "r", stdin);
freopen("snow_run.out", "w", stdout);
long N;
scanf("%ld", &N);
for (long i = 0; i < N; i++) {
scanf("%ld", &A[i]);
// Αύξηση τελικής κατάταξης προηγούμενων δρομέων που τερμάτισαν αργότερα
for (long j = 0; j < i; j++) {
if (A[j] >= A[i])
A[j]++;
}
}
// Εκτύπωση τελικών κατατάξεων
for (long i = 0; i < N; i++) {
printf("%ld\n", A[i]);
}
return(0);
}
2η λύση με Brute force
Αυτή η λύση έχει την ίδια πολυπλοκότητα με την προηγούμενη, ωστόσο χρησιμοποιεί μία λίγο διαφορετική προσέγγιση που θα μας βοηθήσει να κατασκευάσουμε στη συνέχεια τη βέλτιστη λύση. Όπως φάνηκε από τον προηγούμενο αλγόριθμο, η τελική κατάταξη ενός παίκτη εξαρτάται μόνο από τις κατατάξεις των παικτών μετά από αυτόν και από την κατάταξή του τη στιγμή που τερμάτισε. Μπορούμε να κάνουμε μία παρατήρηση που προκύπτει από τον τρόπο που γίνονταν οι αυξήσεις των κατατάξεων στον προηγούμενο αλγόριθμο.
Παρατήρηση: Θέλουμε να υπολογίσουμε την τελική κατάταξη ενός παίκτη \(i\) που, όταν τερμάτισε, βρισκόταν στη θέση \(a\). Έστω ότι γνωρίζαμε την τελική κατάταξη όλων των επόμενων παικτών. Αν ο παίκτης \(i\) τερματίσει στη θέση \(a+1\), αυτό συνέβη διότι ακριβώς ένας από τους επόμενους παίκτες τερμάτισε σε καλύτερη θέση από την \(a+1\). Με το ίδιο σκεπτικό, αν η τελική θέση του \(i\) είναι η \(a+X\), αυτό συμβαίνει διότι υπάρχουν ακριβώς \(X\) από τους επόμενους παίκτες που τερμάτισαν σε καλύτερη θέση από την \(a+X\).
Συνεπώς, αν γνωρίζουμε την τελική κατάταξη των επόμενων παικτών, ψάχνουμε να βρούμε τον αριθμό \(X\) για τον οποίο ακριβώς \(X\) από αυτούς τερμάτισαν πριν τη θέση \(a+X\) στην τελική τους κατάταξη. Προφανώς πρέπει επίσης η θέση \(a+X\) να μην έχει καταληφθεί από κάποιον από αυτούς. Προσέξτε ότι αυτό είναι ισοδύναμο με το να ψάχνουμε την \(a\)-οστή μη-κατειλημμένη θέση.
Σημείωση: Μπορεί κανείς να δείξει ότι αυτός ο αριθμός \(X\) είναι μοναδικός. Ο τρόπος να το κάνουμε αυτό είναι με εις άτοπον απαγωγή. Φανταζόμαστε ότι υπήρχαν δύο τέτοιοι αριθμοί \(X_1\) και \(X_2\), με \(X_1 < X_2\). Αυτό σημαίνει ότι κανείς δεν τερμάτισε στις θέσεις \(a+X_1\) και \(a+X_2\). Αφού ο \(X_1\) είναι υποψήφιος, σημαίνει ότι υπάρχουν \(X_1\) παίκτες που τερμάτισαν πριν τη θέση \(a+X_1\). Όμως ανάμεσα στην \(a+X_1\) και την \(a+X_2\) υπάρχουν μόνο \(X_2-X_1-1\) θέσεις όπου μπορεί να τερμάτισε κάποιος, αφού ούτε η \(a+X_1\) ούτε η \(a+X_2\) είναι κατειλημμένες. Επομένως οι παίκτες που τερμάτισαν πριν τη θέση \(a+X_2\) είναι το πολύ όσοι οι παίκτες που τερμάτισαν πριν την θέση \(a+X_1\) (δηλαδή \(X_1\)), όσοι τερμάτισαν ακριβώς στην \(a+X_1\) (δηλαδή 0), και \(X_2-X_1-1\) που είναι οι θέσεις ανάμεσα στην \(a+X_1\) και \(a+X_2\). Επομένως είναι το πολύ \(X_1 + 0 + (X_2-X_1-1) = X_2-1\), ενώ εμείς θέλαμε να είναι \(X_2\). Επομένως η \(X_2\) δεν είναι υποψήφια θέση.
Μπορούμε λοιπόν να έχουμε έναν boolean πίνακα, έστω \(B\), αρχικοποιημένο σε \(\mathit{false}\). Καθώς διατρέχουμε τους παίκτες από το τέλος προς την αρχή θα υπολογίζουμε την τελική τους κατάταξή. Αν ο \(i\)-οστός παίκτης έχει κατάταξη ίση με \(a\) τη στιγμή τερματισμού του, τότε θα ψάχνουμε γραμμικά το \(a\)-οστό \(\mathit{false}\) του πίνακα \(B\). Αν αυτό βρίσκεται στη θέση \(b\) τότε αυτή θα είναι η τελική κατάταξη του \(i\)-οστού παίκτη, οπότε θα κάνουμε το \(B[b]\) ίσο με \(\mathit{true}\) και το \(A[i]\) ίσο με \(b\). Τελικά ο πίνακας \(A\) θα περιέχει τα αποτελέσματα.
Επειδή για κάθε παίκτη κάνουμε γραμμική διάσχιση του πίνακα \(B\), η χρονική πολυπλοκότητα θα είναι \(\mathcal{O}(N^2)\). Η χωρική πολυπλοκότητα είναι και πάλι \(\mathcal{O}(N)\). Αν και αυτός ο αλγόριθμος έχει την ίδια χρονική πολυπλοκότητα με τον προηγούμενο, πρακτικά συχνά θα πετυχαίνει μικρότερους χρόνους καθώς για πολλούς παίκτες δε θα χρειάζεται να διασχίζουμε όλον τον πίνακα \(B\). Βέβαια και πάλι για απαιτητικά testcases αυτή η λύση υπερβαίνει τα χρονικά όρια.
#include <cstdio>
using namespace std;
const long MAXN = 100005;
long A[MAXN];
bool B[MAXN];
int main() {
freopen("snow_run.in", "r", stdin);
freopen("snow_run.out", "w", stdout);
long N;
scanf("%ld", &N);
// Διάβασμα κατατάξεων τη στιγμή τερματισμού κάθε δρομέα
for (long i = 0; i < N; i++) {
scanf("%ld", &A[i]);
}
for (long i = N - 1; i >= 0; i--) {
long a = A[i];
long b = 0;
// Εύρεση a-οστού κενού στη θέση b
while (a) {
if (!B[++b])
a--;
}
// Το b είναι η τελική κατάταξη του τρέχοντος παίκτη
B[b] = true;
A[i] = b;
}
// Εκτύπωση τελικών κατατάξεων
for (long i = 0; i < N; i++) {
printf("%ld\n", A[i]);
}
return(0);
}
Βέλτιστη λύση με Segment tree
Αυτό το πρόβλημα μπορεί να λυθεί πιο γρήγορα εάν επιταχύνουμε τη διαδικασία εύρεσης του \(a\)-οστού κενού στον πίνακα κατατάξεων. Ένας τρόπος να το κάνουμε αυτό είναι με τη βοήθεια μίας δομής δεδομένων που ονομάζεται segment tree. Καλή πηγή διαβάσματος για τα segment trees με θεωρία, παραδείγματα χρήσης και προβλήματα είναι ένα άρθρο του Καλλίνικου που μπορείτε να βρείτε εδώ.
Μπορούμε να θεωρήσουμε έναν πίνακα \(C\) που θα έχει \(1\) στις θέσεις που αντιστοιχούν σε μη κατειλημμένες θέσεις της κατάταξης και \(0\) στις κατειλημμένες. Αν εφαρμόσουμε ένα αθροιστικό segment tree πάνω στον πίνακα \(C\) μπορούμε να το χρησιμοποιούμε για να βρίσκουμε τα επιθυμητά κενά (query) και να κάνουμε κατάληψη τους (update). Επειδή κάνουμε update τους κόμβους που προκύπτουν από τα query μπορούμε να συνενώσουμε αυτές τις δύο λειτουργίες.
Ο τρόπος που θα εντοπίζουμε το \(k\)-οστό κενό του πίνακα κατάταξης, δηλαδή το \(k\)-οστό \(1\) του πίνακα \(C\), είναι ο εξής: Είτε στο αριστερό μισό υπάρχουν τουλάχιστον \(k\) άσσοι, και συνεχίζουμε την αναζήτησή μας εκεί, είτε λιγότεροι (έστω \(x\)). Στη δεύτερη περίπτωση, συνεχίζουμε την αναζήτησή μας στο δεξί μισό, αλλά ψάχνουμε πλέον τον \((k-x)\)-οστό άσσο. Τις πληροφορίες ακριβώς αυτές μας παρέχει ένα segment tree.
Αφού κάθε φορά η αναζήτησή μας περιορίζεται στο μισό, χρειαζόμαστε χρόνο \(\mathcal{O}(\log{N})\), όπως σε μία δυαδική αναζήτηση (πιο αναλυτικά στο άρθρο του Καλλίνικου). Άρα η συνολική χρονική πολυπλοκότητα αυτού του αλγορίθμου είναι \(\mathcal{O}(N\log{N})\). Η χωρική πολυπλοκότητα είναι \(\mathcal{O}(N)\). Πλέον ο αλγόριθμος περνάει όλα τα testcases.
#include <cstdio>
using namespace std;
const long MAXN = 100005;
long A[MAXN];
// Δηλώσεις για segment tree
long C[MAXN], tree[4 * MAXN];
void build(long node, long start, long end) {
if(start == end)
tree[node] = C[start];
else {
long mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
}
// Εντοποπισμός επιθυμητού 1 και ενημέρωση segment tree
long query(long node, long start, long end, long k) {
tree[node]--;
if(start == end) {
C[start] = 0;
return(start);
}
long mid = (start + end) / 2;
long c = tree[2 * node];
// Επιλογή κατάλληλου υποδέντρου
if (c >= k)
return(query(2 * node, start, mid, k));
return(query(2 * node + 1, mid + 1, end, k - c));
}
int main() {
freopen("snow_run.in", "r", stdin);
freopen("snow_run.out", "w", stdout);
long N;
scanf("%ld", &N);
// Διάβασμα κατατάξεων τη στιγμή τερματισμού κάθε δρομέα
// και αρχικοποίηση πίνακα C
for (long i = 1; i <= N; i++) {
scanf("%ld", &A[i]);
C[i] = 1;
}
// Κατασκευή segment tree
build(1, 1, N);
// Υπολογισμός τελικών κατατάξεων με εντοπισμό 1
for (long i = N; i; i--) {
A[i] = query(1, 1, N, A[i]);
}
// Εκτύπωση τελικών κατατάξεων
for (long i = 1; i <= N; i++) {
printf("%ld\n", A[i]);
}
return(0);
}