23ος ΠΔΠ Γ' Φάση: Prevdiv (prevdiv) - Λύση

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

Μας δίνεται ένας πίνακας και μας ζητείται να βρούμε τον μεγαλύτερο ακέραιο που διαιρείται από όλους τους προηγούμενούς του.

Brute force λύση

Μπορούμε για κάθε αριθμό στον πίνακα να κοιτάξουμε αν διαιρείται από όλους τους προηγούμενους του. Ελέγχουμε αν ο Α διαιρεί τον Β με την εντολή Β % Α == 0 (δηλαδή αν το υπόλοιπο της διαίρεσης του Β με τον Α είναι \(0\)). Μία μικρή βελτιστοποίηση είναι να ελέγχουμε έναν αριθμό μόνο αν είναι μεγαλύτερος από τον τωρινό μεγαλύτερο.

#include <cstdio>

const size_t MAXN = 3'000'000;

long A[MAXN];

int main() {
   long n;
   FILE *fi = fopen("prevdiv.in", "r");
   fscanf(fi, "%ld", &n);
   for (long i = 0; i < n; ++i) {
      fscanf(fi, "%ld", &A[i]);
   }
   fclose(fi);
   long cur_max = A[0];
   for (long i = 1; i < n; ++i) {
      if (A[i] > cur_max) {
         bool found_counterexample = false;
         for (long j = 0; j <= i - 1; ++j){
            if (A[i] % A[j] != 0) {
               found_counterexample = true;
               break;
            }
         }
         if (!found_counterexample) {
            cur_max = A[i];
         }
      }
   }
   FILE *fo = fopen("prevdiv.out", "w");
   fprintf(fo, "%ld\n", cur_max);
   fclose(fo);
   return 0;
}

Σημείωση: Αυτή η λύση έχει πολυπλοκότητα \(\mathcal{O}(N^2)\), αλλά πιάνει όλα εκτός από \(4\) testcases.

Βέλτιστη λύση

Θα χρησιμοποιήσουμε μία από τις βασικές ιδιότητες της διαίρεσης:

Ιδιότητα 1: Αν ο ακέραιος \(A\) διαιρεί τον ακέραιο \(B\) και ο \(B\) διαιρεί τον \(C\), τότε ο \(A\) διαιρεί τον \(C\).

Αυτό μας δίνει κατευθείαν την εξής παρατήρηση:

Παρατήρηση 1: Αν έχουμε ελέγξει ότι \(A_1, \ldots A_{i-1}\) διαιρούνε τον \(A_i\), τότε όταν ελέγχουμε τον \(A_j\) για \(j > i\), δεν χρειάζεται να εξετάσουμε τους \(A_1, \ldots A_{i-1}\). Αρκεί να ελέγξουμε ότι ο \(A_i\) (και οι μετέπειτα) διαιρούν τον \(A_j\).

Αυτό από μόνο του δεν μας γλιτώνει πολλούς από τους ελέγχους γιατί μπορεί να έχουμε τον πίνακα \(2, 3, 3, 3, 3, 3, 3, 5, 6, 6, 6, 6\). Άρα για τα \(6\), ο πιο πρόσφατος αριθμός που διαιρείται από όλους τους προηγούμενούς του είναι ο \(2\), άρα πρέπει να ελέγξουμε όλα τα \(3\) για κάθε \(6\) (μέχρι που να δούμε ότι το \(5\) δεν διαιρεί το \(6\)).

Αλλά για τα \(A_i = 3\) έχουμε βρει έναν ακέραιο \(A_j = 6\) (και \(A_j = 3\)) με \(j > i\) ώστε \(A_i\) διαιρεί τον \(A_j\). Άρα για τους επόμενους ακεραίους, αρκεί να κοιτάξουμε ότι ο \(A_j\) τους διαιρεί (και αυτό συνεπάγεται ότι και ο \(A_i\) τους διαιρεί). Πιο συγκεκριμένα, επεκτείνουμε την Παρατήρηση 1 ως εξής:

Παρατήρηση 2: Αν για κάποιο \(A_i\) βρούμε \(A_j\) (για \(j > i\)) ώστε \(A_i\) διαιρεί το \(A_j\), τότε για κάθε \(A_k\) (για \(k > j\)) αρκεί να ελέγξουμε ότι \(A_j\) διαιρεί το \(A_k\) (και αυτό συνεπάγεται ότι \(A_i\) διαιρεί το \(A_k\)).

Αυτή η παρατήρηση μας οδηγεί στον παρακάτω αλγόριθμο:

κρατάμε τον δείκτη i στο στοιχείο που θέλουμε να ελέγξουμε αν διαιρείται από όλους τους προηγούμενους του
κρατάμε τον δείκτη tested_up_to στο τελευταίο στοιχείο που βρήκαμε κάποιο δεξιότερά του που να το διαιρεί (δλδ Α[tested_up_to] διαιρεί κάποιο A[j] για i >= j > tested_up_to και αυτό δεν ισχύει για το tested_up_to+1).
Για να ελέγξουμε το στοιχείο i προχωράμε τον δείκτη tested_up_to έως ότου είτε φτάσουμε το i είτε βρούμε ένα στοιχείο που δεν διαιρεί το A[i].
Κρατάμε το μεγαλύτερο τα A[i] που διαιρούνται από όλα τους τα προηγούμενα (δηλαδή tested_up_to = i).

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

#include <cstdio>

const size_t MAXN = 3'000'000;

long A[MAXN];

int main() {
   long n;
   FILE *fi = fopen("prevdiv.in", "r");
   fscanf(fi, "%ld", &n);
   for (long i = 0; i < n; ++i) {
      fscanf(fi, "%ld", &A[i]);
   }
   fclose(fi);
   long cur_max = A[0];
   long tested_up_to = 0;
   for (long i = 1; i < n; ++i) {
      if (A[i] > cur_max) {
         while (tested_up_to < i) {
            if (A[i] % A[tested_up_to] != 0) break;
            ++tested_up_to;
         }
         if (tested_up_to == i) cur_max = A[i];
      }
   }
   FILE *fo = fopen("prevdiv.out", "w");
   fprintf(fo, "%ld\n", cur_max);
   fclose(fo);
   return 0;
}

Βέλτιστη λύση με \(\mathcal{O}(1)\) μνήμη

Αφού υπάρχουν δύο δείκτες στον πίνακα και οι δύο πηγαίνουν από τα αριστερά προς τα δεξιά, μπορούμε να ανοίξουμε δύο φορές το αρχείο εισόδου και όταν κάνουμε i++ τότε προχωράμε διαβάζουμε το επόμενο στοιχείο A_i από το fi1 (πρώτο αρχείο), ενώ όταν κάνουμε tested_up_to διαβάζουμε το A_tested_up_to από το fi2 (δεύτερο αρχείο). Με αυτόν τον τρόπο, λύνουμε το πρόβλημα με \(\mathcal{O}(1)\) (έξτρα) μνήμη.

Ο κώδικας χρειάζεται ελάχιστες αλλαγές:

#include <cstdio>

typedef long long ll;

int main() {
   long n;
   FILE *fi1 = fopen("prevdiv.in", "r");
   FILE *fi2 = fopen("prevdiv.in", "r");
   fscanf(fi1, "%ld", &n);
   fscanf(fi2, "%ld", &n);
   long cur_max;
   fscanf(fi1, "%ld", &cur_max);
   long A_tested_up_to;
   fscanf(fi2, "%ld", &A_tested_up_to);
   long tested_up_to = 0;
   for (long i = 1; i < n; ++i) {
      long A_i;
      fscanf(fi1, "%ld", &A_i);
      if (A_i > cur_max) {
         while (tested_up_to < i) {
            if (A_i % A_tested_up_to != 0) break;
            fscanf(fi2, "%ld", &A_tested_up_to);
            ++tested_up_to;
         }
         if (tested_up_to == i) cur_max = A_i;
      }
   }
   fclose(fi1);
   fclose(fi2);
   FILE *fo = fopen("prevdiv.out", "w");
   fprintf(fo, "%ld\n", cur_max);
   fclose(fo);
   return 0;
}

Σημείωση: Στην πράξη, σε κάποια συστήματα το να υπάρχουν δύο ανοικτά αρχεία είναι αργό και μπορεί ο κώδικας να μην περάσει τα τελευταία δύο testcases.

Λύση με ΕΚΠ

Τώρα θα δούμε πώς μπορούμε να λύσουμε το πρόβλημα χρησιμοποιώντας τον αλγόριθμο του Ευκλείδη για το ΜΚΔ (για τον οποίο μπορείτε να διαβάσετε παραπάνω πράγματα εδώ). Θα χρησιμοποιήσουμε την εξής βασική ιδιότητα:

Ιδιότητα 2: Ο ακέραιος \(A_i\) διαιρείται από τους \(A_1, \ldots, A_{i - 1}\), αν και μόνο αν \(\mathrm{ΕΚΠ}(A_1, \ldots , A_{i - 1})\) διαιρεί τον \(A_i\).

Η παρακάτω παρατήρηση μας δίνει έναν τρόπο να υπολογίζουμε το ΕΚΠ πολλών αριθμών χρησιμοποιώντας μία συνάρτηση για τον υπολογισμό του ΕΚΠ δύο ακεραίων.

Ιδιότητα 3: \(\mathrm{ΕΚΠ}(A_1, \ldots , A_{i - 1}) = \mathrm{ΕΚΠ}(A_1, \mathrm{ΕΚΠ}(A_2, \mathrm{ΕΚΠ}(A_3, \ldots ) \ldots ))\)

Ο αλγόριθμος του Ευκλείδη μας δίνει έναν γρήγορο τρόπο να υπολογίζουμε τον ΜΚΔ δύο αριθμών \(Α\) και \(B\) σε χρόνο \(\mathcal{O}(\log(A) + \log(B))\). Η παρακάτω ιδιότητα μας επιτρέπει να υπολογίσουμε σε παρόμοιο χρόνο το ΕΚΠ δύο αριθμών:

Ιδιότητα 4: \(\mathrm{ΕΚΠ}(A, B) = \frac{A \cdot B}{\mathrm{ΜΚΔ}(A, B)}\).

Σημείωση 1: Στα Αγγλικά το ΕΚΠ λέγεται LCM (least common multiple) και το ΜΚΔ λέγεται GCD (greatest common divisor).

Συνδυάζοντας αυτές τις παρατηρήσεις, φτιάχνουμε τον εξής αλγόριθμο:

Διατηρούμε το ΕΚΠ cur_lcm των πρώτων \(i\) αριθμών, χρησιμοποιώντας cur_lcm = lcm(cur_lcm, A[i]).
Ελέγχουμε αν cur_lcm διαιρεί τον A[i]. Αν ναι, αποθηκεύουμε τον Α[ι]στο cur_max.
Τυπώνουμε το cur_max.

Για κάθε στοιχείο πρέπει να καλέσουμε μία φορά τη συνάρτηση lcm, άρα η πολυπλοκότητα είναι \(\mathcal{O}(N \cdot \log{(\mathrm{MAX\_LCM})}) = \mathcal{O}(N \cdot \log{(2 \cdot 10^9)})\). Παρατηρούμε ότι κάθε στιγμή χρειάζομαι μόνο τον A[i], cur_max και το cur_lcm, επομένως η μνήμη είναι \(\mathcal{O}(1)\).

Σημείωση 2: Η εκφώνηση μας δίνει ότι το ΕΚΠ όλων των αριθμών (άρα και το cur_lcm) είναι μικρότερο από \(2 \cdot 10^9\) (χωράει σε \(32\)-bit ακέραιο), άρα δεν υπάρχει περίπτωση overflow αν χρησιμοποιήσουμε long long (καθώς το γινόμενο \(A \cdot B\) στο \(\frac{A \cdot B}{\mathrm{ΜΚΔ}(A, B)}\) χωράει σε \(64\)-bit). Χρησιμοποιώντας την ιδιότητα ότι \(\mathrm{ΜΚΔ}(A, B)\) διαιρεί τον \(A\), μπορούμε να γράψουμε τον lcm ως εξής

long lcm(long a, long b) {
   return (a / gcd(a, b)) * b;
}

και μας επιτρέπει να χρημοποιήσουμε long αντί για long long. Ολόκληρος ο κώδικας δίνεται παρακάτω:

#include <algorithm>
#include <cstdio>

long gcd(long a, long b) {
   if (a == 0) return b;
   return gcd(b % a, a);
}

long lcm(long a, long b) {
   return (a / gcd(a, b)) * b;
}

int main() {
   long n;
   FILE *fi = fopen("prevdiv.in", "r");
   fscanf(fi, "%ld", &n);
   long A_0;
   fscanf(fi, "%ld", &A_0);
   long cur_max = A_0;
   long cur_lcm = A_0;
   long A_i;
   for (long i = 0; i < n; ++i) {
      fscanf(fi, "%ld", &A_i);
      if (A_i % cur_lcm == 0) cur_max = A_i;
      cur_lcm = lcm(cur_lcm, A_i);
   }
   fclose(fi);
   FILE *fo = fopen("prevdiv.out", "w");
   fprintf(fo, "%ld\n", cur_max);
   fclose(fo);
   return 0;
}

Σημείωση 3: Από την C++17 και μετά, υπάρχει η συνάρτηση std::gcd στην βιβλιοθήκη STL, επομένως δεν χρειάζεται να την υλοποιήσετε.