30ος ΠΔΠ Γ' Φάση: Rafting (rafting) - Λύση

Brute force

Η brute force λύση είναι να διατρέχουμε τον πίνακα με τις κατατάξεις, διατηρώντας μία λίστα με την τωρινή κατάταξη. Για το τρίτο παράδειγμα, η λίστα θα ήταν η εξής:

Για να εισαγάγουμε ένα στοιχείο σε μία λίστα πρέπει να βρούμε το αμέσως προηγούμενο του στοιχείο. Αυτό χρειάζεται \(\mathcal{O}(N)\) επειδή στην χειρότερη περίπτωση πρέπει να διατρέξουμε ολόκληρη τη λίστα. Άρα αφού υπάρχουν \(\mathcal{O}(N)\) εισαγωγές ο αλγόριθμος θέλει \(\mathcal{O}(N^2)\) χρόνο και \(\mathcal{O}(N)\) μνήμη.

#include <cstdio>
#include <iterator>
#include <list>

int main() {
   long N;
   FILE *fi = fopen("rafting.in", "r");
   std::list<long> people;
   fscanf(fi, "%ld", &N);
   for (long i = 0; i < N; ++i) {
      long rank;
      fscanf(fi, "%ld", &rank);
      std::list<long>::iterator it = people.begin();
      std::advance(it, rank - 1);
      people.insert(it, i + 1);
   }
   fclose(fi);
   
   FILE *fo = fopen("rafting.out", "w");
   
   std::list<long>::iterator it = people.begin();
   for (long i = 0; i < N; ++i, ++it) {
      fprintf(fo, "%ld", *it);
      if (i < N - 1) fprintf(fo, " ");
   }
   fprintf(fo, "\n");
   fclose(fo);
   return 0;
}

Σημείωση: Αντί για λίστα μπορούμε να χρησιμοποιήσουμε έναν πίνακα και για εισαγωγή στην θέση \(i\) μεταφέρουμε όλα τα στοιχεία από το \(i\) και μετά, μία θέση προς τα δεξιά.

Βέλτιση λύση

Η λύση αυτή προϋποθέτει γνώσεις segment tree.

Ας δούμε τι θα γινόταν αν προσπαθούσαμε να βρούμε τις κατατάξεις για το παράδειγμα 3, ξεκινώντας από την τελευταία σχεδία.

1. Η τελευταία σχεδία θα τοποθετηθεί στην κατάταξη εκείνης της στιγμής, καθώς όλες οι σχεδίες έρχονται πριν από αυτή.

   1	2	3	4	5	6	7
   				7

2. Η \(6\)η σχεδία θα τοποθετηθεί στην \(1\)η θέση αφού η \(7\)η σχεδία δεν την προσπέρασε.

   1	2	3	4	5	6	7
   6				7

3. Η \(5\)η σχεδία θα τοποθετηθεί στην \(4\)η θέση αφού η \(6\)η σχεδία μόνο την προσπέρασε.

   1	2	3	4	5	6	7
   6			5	7

Με βάση τα παραπάνω βήματα, κάνουμε την εξής παρατήρηση:

Παρατήρηση: Έχοντας τοποθετήσει τις σχεδίες \(i+1\) έως \(N\) στην σωστή κατάταξη, η σχεδία \(i\) (με προσωρινή κατάταξη \(j\)) βρίσκεται στην \(j\)-οστή κενή θέση του πίνακα κατάταξης.

Απόδειξη. Οι κενές θέσεις αντιστοιχούν στις σχεδίες που ήρθαν πριν από την \(i\)-οστή. Από την υπόθεση όλες οι επόμενες σχεδίες είναι σωστά τοποθετημένες, επομένως η μόνη θέση ώστε που δίνει προσωρινή κατάταξη \(j\) είναι η \(j\)-οστή κενή θέση.

Ας ολοκληρώσουμε τα βήματα, ώστε να επιβεβαιώσουμε την παρατήρηση:

1. Η \(2\)η κενή θέση είναι η \(3\)η

   1	2	3	4	5	6	7
   6		4	5	7

2. Η \(3\)η κενή θέση είναι η \(7\)η

   1	2	3	4	5	6	7
   6		4	5	7		3

3. Η \(1\)η κενή θέση είναι η \(2\)η

   1	2	3	4	5	6	7
   6	2	4	5	7		3

4. Η \(1\)η κενή θέση είναι η \(6\)η

   1	2	3	4	5	6	7
   6	2	4	5	7	1	3

Τώρα μένει να δούμε πώς μπορούμε να βρούμε το \(i\)-οστό κενό γρήγορα. Θα χρησιμοποιήσουμε τη δομή δεδομένων segment tree, πάνω από έναν πίνακα όπου η \(i\)-οστή θέση είναι \(0\) ή \(1\) ανάλογα με το αν η θέση δεν είναι ή είναι κενή. Για να αφαιρέσουμε ένα κενό, απλά αφαιρούμε \(1\) από την θέση του στοιχείου.

Για να βρούμε το \(i\)-οστό κενό ξεκινάμε από την ρίζα του segment tree και κρατάμε το πόσα κενά \(\mathit{rem}\) μένει να βρούμε (αρχικά ίσο με την κατάταξη της σχεδίας). Έπειτα:

1. Αν ο κόμβος δεν έχει παιδιά, βρήκαμε το \(j\)-οστό κενό.
2. Αν το αριστερό παιδί έχει τουλάχιστον \(\mathit{rem}\), τότε συνεχίζουμε την αναζήτηση εκεί.
3. Διαφορετικά, συνεχίζουμε την αναζήτηση στο δεξί παιδί με αναζητώντας \(\mathit{rem}\) μείον τα κενά στο αριστερό παιδί (αφού αυτά είναι στα αριστερά του).

Για παράδειγμα, στο τρίτο βήμα θα ψάξουμε το ακόλουθο μονοπάτι:

Η αναζήτηση αυτή εκφράζεται από τον παρακάτω κώδικα,

long find_first_position_where_sum_equals(long rem) {
   long n = 1, b = 1, e = N;
   while (b != e) {
      long mid = (b + e)/2;
      if (seg_tree[2*n] >= rem) {
         n = 2 * n;
         e = mid;
      } else {
         rem -= seg_tree[2*n];
         n = 2 * n + 1;
         b = mid + 1;
      }
   }
   return b;
}

Η αναζήτηση θέλει χρόνο γραμμικό στο ύψος του segment tree που είναι \(\mathcal{O}(\log{N})\), το ίδιο και η προσθήκη στο segment tree. Επομένως, συνολικά ο αλγόριθμος θέλει \(\mathcal{O}(N\log{N})\) χρόνο και \(\mathcal{O}(N)\) μνήμη.

#include <cstdio>

const size_t MAXN = 500000;

long A[MAXN + 1];
long rank[MAXN + 1];
long seg_tree[4*(MAXN + 1)];

long N;

/* Κλασσική αρχικοποίηση segment tree. */
void init(long n, long b, long e) {
   if (b == e) {
      seg_tree[n] = 1;
      return;
   }
   long mid = (b + e) / 2;
   init(2 * n, b, mid);
   init(2 * n + 1, mid + 1, e);
   seg_tree[n] = seg_tree[2*n] + seg_tree[2*n + 1];
}

/* Βρίσκουμε το rem-οστό κενό. */
long find_first_position_where_sum_equals(long rem) {
   long n = 1, b = 1, e = N;
   while (b != e) {
      long mid = (b + e)/2;
      if (seg_tree[2*n] >= rem) {
         n = 2 * n;
         e = mid;
      } else {
         rem -= seg_tree[2*n];
         n = 2 * n + 1;
         b = mid + 1;
      }
   }
   return b;
}

/* Αφαιρούμε ένα κενό στην θέση idx. */
void minus_one_at(long idx) {
   // Αφού κρατάμε το άθροισμα, αρκεί να μειώσουμε κατά ένα όλους τους
   // κόμβους από την κορυφή του segment tree, προς το φύλο που αντιστοιχεί
   // στο idx.
   long n = 1, b = 1, e = N;
   while (b != e) {
      long mid = (b + e)/2;
      --seg_tree[n];
      if (idx <= mid) {
         n = 2 * n;
         e = mid;
      } else {
         n = 2 * n + 1;
         b = mid + 1;
      }
   }
   --seg_tree[n];
}

int main() {
   FILE *fi = fopen("rafting.in", "r");
   fscanf(fi, "%ld", &N);
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%ld", &A[i]);
   }
   fclose(fi);
   
   init(1, 1, N);
   
   for (long i = N - 1; i >= 0; --i) {
      long final_rank = find_first_position_where_sum_equals(A[i]);
      rank[final_rank] = i + 1;
      minus_one_at(final_rank);
   }
   
   FILE *fo = fopen("rafting.out", "w");
   for (long i = 1; i <= N; ++i) {
      fprintf(fo, "%ld", rank[i]);
      if (i < N) fprintf(fo, " ");
   }
   fprintf(fo, "\n");
   fclose(fo);
   return 0;
}

Σημείωση: Υπάρχουν παρόμοιες λύσεις με την ίδια ή χειρότερη πολυπλοκότητα χρησιμοποιώντας δομές δεδομένων όπως το binary indexed tree, τα treaps και άλλα.