28ος ΠΔΠ Γ' Φάση: Εκδρομή για σκι (skitrip) - Λύση

Επεξήγηση εκφώνησης

Μας δίνεται μία ακολουθία \(Y_1, \ldots , Y_N\) και πρέπει να βρούμε δύο δείκτες \(i\) και \(j\) (με \(j > i\)) ώστε \(Y_j \ge Y_i\) και η διαφορά \(j - i\) να είναι μέγιστη.

Brute force λύση (\(40\%\))

Η πιο απλή λύση είναι να δοκιμάσουμε όλα τα δυνατά ζεύγη \((i, j)\) και να βρούμε ποιο (από αυτά που ικανοποιούν την συνθήκη \(Y_i \le Y_j\)) έχει τη μέγιστη διαφορά \(j - i\).

#include <algorithm>
#include <cstdio>

typedef long long ll;

const size_t MAXN = 1000000;

ll a[MAXN];

int main () {
   long N;
   FILE *fi = fopen("skitrip.in", "r");
   fscanf(fi, "%ld", &N);
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%lld", &a[i]);
   }
   fclose(fi);
   
   long mx = 0;
   for (long i = 0; i < N; ++i) {
      for (long j = i + 1; j < N; ++j) {
         if (a[i] <= a[j]) {
            mx = std::max(mx, j - i);
         }
      }
   }
   
   FILE *fo = fopen("skitrip.out", "w");
   fprintf(fo, "%ld\n", mx);
   fclose(fo);
   
   return 0;
}

Αφού υπάρχουν \(N(N-1)/2\) δυνατοί τρόποι να διαλέξουμε τα \(i\) και τα \(j\), ο αλγόριθμος αυτός χρειάζεται \(\mathcal{O}(N^2)\) χρόνο.

Λύση με ταξινόμηση (\(80\%\))

Παρατήρηση 1: Το μεγαλύτερο διάστημα που τελειώνει στο \(Y_j\) έχει ως αρχή το μικρότερο \(i^*\) με \(Y_{i^*} \le Y_j\).

(Απόδειξη) Έστω \(Y_{i} \le Y_j\) και \(Y_{i^*} \le Y_j\). Τότε οι διαφορές τους είναι \(j - i\) και \(j - i^*\), αντίστοιχα. Επειδή \(i^* < i\) (ως το μικρότερο), έχουμε ότι \(j - i^* > j - i\) άρα δημιουργεί το μεγαλύτερο διάστημα.

Επομένως, άμα ταξινομήσουμε τα ύψη κατά \(Y_i\) (και αν τα ύψη είναι ίσα τότε διαλέγουμε πρώτα αυτό με το μικρότερο \(i\)), τότε το μεγαλύτερο διάστημα για το \(k\)-οστό ύψος \(Y_i\), υπολογίζεται ως η διαφορά του \(i\) και του μικρότερου index που έχουμε συναντήσει στα πρώτα \(k\) ταξινομημένα ύψη (καθώς αυτό αντιστοιχεί στο \(i^*\)).

Στο παράδειγμα, τα ταξινομημένα ύψη μαζί με τον δείκτη τους είναι:

(13, 11), (15, 14), (15, 16), (17, 5), (17, 12), (20, 15), (35, 13), (38, 9), (57, 7), (62, 10), (64, 3), (69, 8), (78, 1), (88, 2), (91, 6), (94, 4)

Για παράδειγμα.

το μεγαλύτερο διάστημα που τελειώνει στο \((20, 15)\) είναι αυτό με τον μικρότερο δείκτη αριστερά του \((20, 15)\) στην ταξινομημένη λίστα, άρα το \((17, 5)\) (και δίνει το διάστημα \(15 - 5 = 10\))
το μεγαλύτερο διάστημα που τελειώνει στο \((62, 10)\) είναι αυτό που ξεκινάει στο \((17, 5)\)
το μεγαλύτερο διάστημα που τελειώνει στο \((17, 12)\) είναι αυτό που ξεκινάει στο \((17, 5)\), που εξηγεί γιατί πρέπει να βάλουμε πρώτα το στοιχείο με τον μικρότερο δείκτη αν τα ύψη είναι τα ίδια.

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

#include <algorithm>
#include <cstdio>

typedef long long ll;

const size_t MAXN = 1000000;

// Οι κορυφές των βουνών, το ύψος και η θέση στον πίνακα.
struct Peak {
   long idx;
   ll v;

   // Υλοποίηση της σύγκρισης κατά ύψος και αν είναι ίσα τα ύψη, 
   // τότε κατά index. (Αυτή η συνάρτηση χρησιμοποιείται από την
   // sort)
   bool operator<(const Peak& other) const {
      if (v == other.v) return idx < other.idx;
      return v < other.v;
   }

} a[MAXN];

int main () {
   long N;
   FILE *fi = fopen("skitrip.in", "r");
   fscanf(fi, "%ld", &N);
   ll val;
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%lld", &val);
      a[i] = {i, val};
   }
   fclose(fi);
   
   std::sort(a, a + N);
   
   long min_idx = a[0].idx;
   long max_length = 0;
   for (long i = 1; i < N; ++i) {
      max_length = std::max(max_length, a[i].idx - min_idx);
      min_idx = std::min(min_idx, a[i].idx);
   }
   
   FILE *fo = fopen("skitrip.out", "w");
   fprintf(fo, "%ld\n", max_length);
   return 0;
}

Γραμμική λύση (\(100\%\))

Παρατήρηση 2: Αν \(Y_i \le Y_j\) και \(i < j\), δεν υπάρχει περίπτωση το \(Y_i\) να είναι το δεξί τέλος του μέγιστου διαστήματος.

(Απόδειξη) Έστω ότι το μέγιστο διάστημα είναι \((k, i)\) με \(Y_k \le Y_i\) και \(k < i\). Τότε \(Y_k \le Y_j\) και \(k < i < j\). Άρα και το \((k, j)\) είναι έγκυρο, αλλά \(j - k > i - k\) (καθότι \(j > i\)). Επομένως, το \((k, i)\) δεν μπορεί να είναι μέγιστο.

Αντίστοιχα, αν το \(Y_i\) δεν είναι μικρότερο από τα \(\lbrace Y_1, \ldots, Y_{i-1} \rbrace\) τότε δεν μπορεί να είναι το αριστερό τέλος του μέγιστου διαστήματος.

Χρησιμοποιώντας αυτές τις δύο παρατηρήσεις, έχουμε ότι:

τα πιθανά δεξιά τέλη φτιάχνουν μία φθίνουσα ακολουθία
τα πιθανά αριστερά τέλη φτιάχνουν μία φθίνουσα ακολουθία.

Στο παράδειγμα, αυτά είναι

Πιθανά δεξιά τέλη (\(\mathrm{right}\)):	78 88 64 94 17 91 57 69 38 62 13 17 35 15 20 15
Πιθανά αριστερά τέλη (\(\mathrm{left}\)):	78 88 64 94 17 91 57 69 38 62 13 17 35 15 20 15

Για κάθε ένα πιθανό αριστερό τέλος \(\ell\), πρέπει να βρούμε το πιο δεξί τέλος που να είναι μεγαλύτερό του (Παρατήρηση 1). Άρα το μικρότερο πιθανό δεξί τέλος που είναι μεγαλύτερό του \(\ell\). Για παράδειγμα, για \(\ell = 78\), η απάντηση είναι \(91\) και για \(\ell = 17\) η απάντηση είναι \(20\) (που μας δίνει και την τελική απάντηση).

Αφού ο πίνακας είναι ταξινομημένος, θα μπορούσαμε να κάνουμε δυαδική αναζήτηση και σε \(\mathcal{O}(N \log{N})\) να βρούμε το μέγιστο διάστημα για κάθε πιθανό αριστερό τέλος. Εδώ όμως μπορούμε να το κάνουμε γραμμικά με την εξής παρατήρηση:

Παρατήρηση 3: Αν \(\mathrm{right}_{i} > \mathrm{left}_j\), τότε το μέγιστο διάστημα δεν μπορεί να σχηματίζεται από \(\mathrm{right}_{k}\) (για \(k < i\)) και \(\mathrm{left}_{m}\) (για \(m > j\)). (Δηλαδή αν κοιτώντας τα πιθανά αριστερά τέλη με φθίνουσα σειρά βρούμε ένα δεξί τέλος που είναι μεγαλύτερο του υπό εξέταση αριστερού, τότε δεν χρειαζόμαστε τα προηγούμενα δεξιά τέλη για τα επόμενα υποψήφια αριστερά τέλη)

(Απόδειξη) Ισχύει λόγω της παρατήρησης 2.

Άρα αυτό μας επιτρέπει να αφαιρούμε τα \(\mathrm{right}\) που δεν χρειαζόμαστε. Στο παράδειγμα, τα βήματα είναι ως εξής:

Βρίσκουμε το μικρότερο δεξί τέλος μεγαλύτερο από \(78\). Αυτό μας δίνει την απόσταση \(6 - 1 = 5\).

\(\mathrm{right}\): 94 91 69 62 35 20 15

\(\mathrm{left}\): 78 64 17 13
Αφαιρούμε όλα τα μεγαλύτερα από \(91\) στο \(\mathrm{right}\) (αφού λόγω της παρατήρησης 3, δεν θα χρειαστούν για τα επόμενα \(\mathrm{left}\)).

\(\mathrm{right}\): 94 91 69 62 35 20 15

\(\mathrm{left}\): 78 64 17 13
Βρίσκουμε το μικρότερο δεξί τέλος μεγαλύτερο από \(64\). Αυτό μας δίνει την απόσταση \(8 - 3 = 5\).

\(\mathrm{right}\): 94 91 69 62 35 20 15

\(\mathrm{left}\): 78 64 17 13
Αφαιρούμε όλα τα μεγαλύτερα από \(69\) στο \(\mathrm{right}\) (αφού λόγω της παρατήρησης 3, δεν θα χρειαστούν για τα επόμενα \(\mathrm{left}\)).

\(\mathrm{right}\): 94 91 69 62 35 20 15

\(\mathrm{left}\): 78 64 17 13
Βρίσκουμε το μικρότερο δεξί τέλος μεγαλύτερο από \(17\). Αυτό μας δίνει την απόσταση \(15 - 5 = 10\).

\(\mathrm{right}\): 94 91 69 62 35 20 15

\(\mathrm{left}\): 78 64 17 13
Αφαιρούμε όλα τα μεγαλύτερα από \(20\) στο \(\mathrm{right}\) (αφού λόγω της παρατήρησης 3, δεν θα χρειαστούν για τα επόμενα \(\mathrm{left}\)).

\(\mathrm{right}\): 94 91 69 62 35 20 15

\(\mathrm{left}\): 78 64 17 13
Βρίσκουμε το μικρότερο δεξί τέλος μεγαλύτερο από \(13\). Αυτό μας δίνει την απόσταση \(16 - 11 = 5\).

\(\mathrm{right}\): 94 91 69 62 35 20 15

\(\mathrm{left}\): 78 64 17 13
Αφαιρούμε όλα τα μεγαλύτερα από \(15\) στο \(\mathrm{right}\) (αφού λόγω της παρατήρησης 3, δεν θα χρειαστούν για τα επόμενα \(\mathrm{left}\)).

\(\mathrm{right}\): 94 91 69 62 35 20 15

\(\mathrm{left}\): 78 64 17 13

Το μέγιστο από αυτά τα διαστήματα έχει μήκος \(10\), επομένως αυτή είναι η απάντηση. Κάθε στοιχείο του \(\mathrm{right}\) μπορεί να αφαιρεθεί μία φορά και ελέγχουμε κάθε στοιχείου του \(\mathrm{left}\) μία φορά, επομένως ο αλγόριθμος χρειάζεται \(\mathrm{O}(N)\) χρόνο (και χώρο).

#include <algorithm>
#include <cstdio>
#include <vector>

typedef long long ll;

const size_t MAXN = 2 * 1000000;

struct Peak {
   long idx;
   ll v;
};

ll a[MAXN];

int main () {
   long N;
   FILE *fi = fopen("skitrip.in", "r");
   fscanf(fi, "%ld", &N);
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%ld", &a[i]);
   }
   fclose(fi);
   
   // Βρίσκουμε όλα τα πιθανά δεξιά τέλη του μέγιστου
   // διαστήματος.
   std::vector<Peak> right;
   right.push_back({ N-1, a[N-1] });
   for (long i = N-2; i >= 0; --i) {
      if (right.back().v < a[i]) {
         right.push_back({ i, a[i] });
      }
   }
   
   ll min_value = a[0] + 1;
   long max_length = 0;
   long right_idx = right.size() - 1;
   for (long i = 0; i < N; ++i) {
      // Για κάθε πιθανό αριστερό τέλος, βρίσκουμε το μικρότερο
      // δεξί τέλος που είναι μεγαλύτερο.
      if (min_value > a[i]) {
         while (right_idx > 0 && right[right_idx - 1].v >= a[i]) --right_idx;
         max_length = std::max(max_length, right[right_idx].idx - i);
         min_value = a[i];
      }
   }
   FILE *fo = fopen("skitrip.out", "w");
   fprintf(fo, "%ld\n",max_length);
   fclose(fo);
   
   return 0;
}

\(\mathrm{right}\):	94 91 69 62 35 20 15
\(\mathrm{left}\):	78 64 17 13