27ος ΠΔΠ Α' Φάση: Το κυλικείο του σχολείου (xxx) - Λύση

Brute force λύση

Πρέπει να βρούμε πόσα παιδιά βλέπουν την είσοδο του κυλικείου. Γνωρίζουμε ότι ένα παιδί βλέπει την είσοδο αν και μόνο αν όλα τα παιδιά που στέκονται μπροστά του έχουν ύψος μικρότερο από το δικό του.

Επομένως, μία σκέψη θα ήταν για κάθε παιδί να ελέγχουμε αν είναι ψηλότερο από όλα τα παιδιά που βρίσκονται μπροστά του. Δηλαδή για κάθε παιδί, \(i\), να διατρέχουμε τον πίνακα \(A\), στον οποίο έχουμε αποθηκεύσει τα ύψη των παιδιών, από τη θέση \(j = i + 1\) μέχρι και την \(j = N - 1\) και να βλέπουμε αν όλα τα \(A[j]\) είναι μικρότερα από το \(A[i]\).

Η boolean μεταβλητή \(ok\) που χρησιμοποιούμε στον κώδικα που φαίνεται παρακάτω αρχικοποιείται σε \(\mathit{true}\) για κάθε παιδί \(i\) και γίνεται \(\mathit{false}\) αν βρεθεί κάποιο \(j > i: A[j] \geq A[i]\), δηλαδή αν υπάρχει κάποιο παιδί μπροστά από το \(i\)-οστό το οποίο έχει ύψος μεγαλύτερο ή ίσο από το δικό του, εμποδίζοντάς το να δει την είσοδο.

Η μεταβλητή \(K\) διατηρεί το πλήθος των παιδιών που βλέπουν το κυλικείο. Αρχικά είναι \(0\) και όποτε συναντάμε ένα παιδί που μπορεί να δει το κυλικείο, δηλαδή η μεταβλητή \(\mathit{ok}\) παραμένει \(\mathit{true}\) για αυτό, θα την αυξάνουμε κατά ένα.

Όταν ελέγξουμε όλα τα παιδιά, δηλαδή όλα τα \(i \in \{0, 1, \dots, N - 1\}\) η μεταβλητή \(K\) θα αποτελεί τη ζητούμενη απάντηση, οπότε αρκεί να την εκτυπώσουμε.

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

#include <cstdio>
using namespace std;

const size_t MAXN = 1000000;

long A[MAXN];

int main() {
   freopen("xxx.in", "r", stdin);
   freopen("xxx.out", "w", stdout);
   long N;
   scanf("%ld", &N);
   for (long i = 0; i < N; i++)
      scanf("%ld", &A[i]);
   long K = 0;
   for (long i = 0; i < N; i++) {
      bool ok = true;
      for (long j = i + 1; j < N; j++) {
         if (A[j] >= A[i]) {
            ok = false;
            break;
         }
      }
      if (ok)
         K++;
   }
   printf("%ld\n", K);
   return(0);
}

Βέλτιση Λύση

Η πολυπλοκότητα της λύσης μας μπορεί να βελτιωθεί σημαντικά αν παρατηρήσουμε ότι ένα παιδί βλέπει την είσοδο του κυλικείου αν και μόνο αν το ψηλότερο από τα παιδιά που βρίσκονται μπροστά του είναι πιο κοντό από αυτό. Ισοδύναμα το \(i\)-οστό παιδί βλέπει την είσοδο αν ισχύει ότι \(A[i] > \max_{i + 1 \leq j < N}(A[j])\). Επίσης πρέπει να παρατηρήσουμε ότι \(\max_{i \leq j < N}(A[j]) = \max(A[i], \max_{i + 1 \leq j < N}(A[j]))\).

Ορίζουμε τη μεταβλητή \(\mathit{mx}\) η οποία θα είναι ίση με \(\max_{i + 1 \leq j < N}(A[j])\) όταν ελέγχουμε αν το \(i\)-οστό παιδί βλέπει το κυλικείο, δηλαδή θα ισούται με το ύψος του ψηλότερου παιδιού που βρίσκεται μπροστά του. Σύμφωνα με τη δεύτερη παρατήρηση, βλέπουμε ότι η μεταβλητή \(\mathit{mx}\) πρέπει να αλλάζει τιμή μόνο όταν συναντάμε ένα παιδί ψηλότερο από όλα όσα βρίσκονται μπροστά του, δηλαδή ένα παιδί που βλέπει την είσοδο. Στην περίπτωση αυτή θέτουμε το \(\mathit{mx}\) ίσο με το ύψος του παιδιού αυτού, δηλαδή \(\mathit{mx} = A[i]\), ώστε η μεταβλητή αυτή να έχει τη σωστή τιμή στην επόμενη επανάληψη. Αυτή η μέθοδος υπολογισμού είναι που οδηγεί στη βελτιστοποίηση της πολυπλοκότητας του αλγορίθμου.

Έχοντας πλέον τη μεταβλητή \(\mathit{mx}\) να έχει την κατάλληλη τιμή σε κάθε επανάληψη (για κάθε \(i\)), μπορούμε να ελέγχουμε άμεσα αν το \(i\)-οστό παιδί βλέπει την είσοδο, ελέγχοντας αν \(A[i] > \mathit{mx}\). Αν ισχύει αυτή η ανισότητα, η είσοδος είναι ορατή από το παιδί που εξετάζουμε και πρέπει να αυξήσουμε το \(K\) κατά \(1\).

Όταν εξετάσουμε όλα τα παιδιά, η μεταβλητή \(K\) θα περιέχει την απάντηση, όπως και στην brute force λύση, οπότε αρκεί να την εκτυπώσουμε.

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

#include <cstdio>
using namespace std;

const size_t MAXN = 1000000;

long A[MAXN];

int main() {
   freopen("xxx.in", "r", stdin);
   freopen("xxx.out", "w", stdout);
   long N;
   scanf("%d", &N);
   for (long i = 0; i < N; i++)
      scanf("%ld", &A[i]);
   long K = 1, mx = A[N - 1];
   for (long i = N - 2; i >= 0; i--) {
      if (A[i] > mx) {
         K++;
         mx = A[i];
      }
   }
   printf("%ld\n", K);
   return(0);
}