27ος ΠΔΠ Γ' Φάση: Εφημερίδες (efimerides) - Λύση

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

Μας δίνεται ένας κυκλικός πίνακας \(A\) με \(N\) ακεραίους και ένας ακέραιος \(K\). Διαλέγουμε μία αρχική θέση στον πίνακα και κάθε φορά βρίσκουμε τον \(K\)-οστό γείτονά του, μέχρι να επιστρέψουμε σε μία θέση που έχουμε ήδη επισκεφθεί. Μας ζητείται να βρούμε το μέγιστο άθροισμα των στοιχείων που μπορούμε να επισκεφτούμε, ξεκινώντας αυτή τη διαδικασία από κάποια αρχική θέση.

Ξεκινούμε με την βασική παρατήρηση ότι αυτή η διαδικασία τελειώνει μετά από το πολύ \(N\) βήματα, αφού υπάρχουν το πολύ \(N\) πιθανά στοιχεία που μπορούμε να επισκεφτούμε. Για τη γρήγορη λύση θα δούμε ότι κάθε διαδικασία τελειώνει εκεί που ξεκίνησε.

Προσομοίωση με set ή hash set

Σε αυτή τη λύση, ξεκινάμε τη διαδικασία από κάθε δυνατή θέση, βρίσκουμε τα στοιχεία που επισκεπτόμαστε και τα αθροίζουμε. Σε κάθε διαδρομή κρατάμε σε ένα set (ή σε hash set ώστε το find/insert να γίνονται σε \(\mathcal{O}(1)\) χρόνο) τις θέσεις τις οποίες επισκεπτόμαστε, ώστε όταν δούμε κάποια από αυτές ξανά, να ολοκληρώσουμε τη διαδικασία. Από όλες τις διαδρομές, κρατάμε αυτή με το μεγαλύτερο άθροισμα.

#include <algorithm>
#include <cstdio>
#include <unordered_set>

const long MAXN = 1'000'000;

long A[MAXN];

int main() {
   FILE *fi = fopen("efimerides.in", "r");
   long N, K;
   fscanf(fi, "%ld%ld", &N, &K);
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%ld", &A[i]);
   }
   fclose(fi);
   
   long max_sum = 0;
   for (long i = 0; i < N; ++i) {
      // Ξεκινάμε μία διαδρομή από το i.
      long sum = 0, j = i;
      std::unordered_set<long> st;
      while (st.find(j) == st.end()) {
         st.insert(j);
         sum += A[j];
         j = (j + K) % N;
      }
      max_sum = std::max(max_sum, sum);
   }
   
   FILE *fo = fopen("efimerides.out", "w");
   fprintf(fo, "%ld\n", max_sum);
   fclose(fo);
   return 0;
}

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

Προσομοίωση με πίνακα

Αντί για set (ή hash set), μπορούμε να χρησιμοποιήσουμε έναν boolean πίνακα \(\texttt{seen}\) με \(N\) θέσεις, όπου το \(\texttt{seen}[i]\) μας λέει αν είδαμε το \(i\) στην τελευταία διαδρομή. Για να μπορέσουμε να επαναχρησιμοποιήσουμε τον ίδιο πίνακα στην επόμενη διαδρομή, στο τέλος της κάθε διαδρομής ανατρέχουμε στα στοιχεία που επισκεφθήκαμε και θέτουμε την τιμή σε false. Ο κώδικας χρειάζεται τις εξής αλλαγές:

   long max_sum = 0;
   for (long i = 0; i < N; ++i) {
      long sum = 0, j = i;
      while (!seen[j]) { // Αντικαθιστά το seen[j].
         seen[j] = true;
         sum += A[j];
         j = (j + K) % N;
      }
      // Καθαρίζουμε τον πίνακα seen.
      j = i;
      while (seen[j]) {
         seen[j] = false;
         j = (j + K) % N;
      }
      max_sum = std::max(max_sum, sum);
   }

Ο αλγόριθμος ακόμα χρειάζεται \(\mathcal{O}(N^2)\) χρόνο, αλλά περνάει δύο παραπάνω testcases από την λύση με το hash set. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.

Σημείωση: Αν θέλουμε να αποφύγουμε το καθάρισμα του πίνακα \(\texttt{seen}\), μπορούμε να κρατάμε έναν ακέραιο \(\texttt{last\_visited\_with}[i]\), τη θέση από την οποία είδαμε τελευταία φορά τον \(i\). Οι αλλαγές είναι οι εξής:

   std::fill(last_seen_with, last_seen_with + N, -1);
   long max_sum = 0;
   for (long i = 0; i < N; ++i) {
      long sum = 0, j = i;
      while (last_seen_with[j] != i) {
         last_seen_with[j] = i;
         sum += A[j];
         j = (j + K) % N;
      }
      max_sum = std::max(max_sum, sum);
   }

Η λύση αυτή μπορεί να πιάσει ένα/δύο παραπάνω testcases. Ολόκληρος ο κώδικας υπάρχει εδώ.

Γρήγορη λύση

Για την γρήγορη λύση, κάνουμε την εξής παρατήρηση.

Παρατήρηση: Κάθε διαδικασία τελειώνει στο στοιχείο από το οποίο ξεκίνησε.

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

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

Άρα, σε έναν κύκλο από όποιο στοιχείο του και να ξεκινήσουμε, θα επισκεφτούμε τα ίδια στοιχεία και άρα θα οδηγήσουν στο ίδιο άθροισμα. Επομένως, αρκεί να επισκεφθούμε το κάθε στοιχείο μία φορά, δηλαδή ξεκινάμε την διαδρομή αν το \(\texttt{seen}[i] = \texttt{false}\). Ο παρακάτω κώδικας υλοποιεί αυτή τη λύση:

#include <algorithm>
#include <cstdio>

const long MAXN = 1'000'000;

long A[MAXN];
bool seen[MAXN];

int main() {
   FILE *fi = fopen("efimerides.in", "r");
   long N, K;
   fscanf(fi, "%ld%ld", &N, &K);
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%ld", &A[i]);
   }
   fclose(fi);
   
   long max_sum = 0;
   for (long i = 0; i < N; ++i) {
      // Ξεκινάμε μία διαδρομή από το i, αν δεν το έχουμε ξαναεπισκεφτεί.
      if (seen[i]) continue;
      long sum = 0, j = i;
      do {
         sum += A[j];
         j = (j + K) % N;
         seen[j] = true;
      } while(j != i);
      max_sum = std::max(max_sum, sum);
   }
   
   FILE *fo = fopen("efimerides.out", "w");
   fprintf(fo, "%ld\n", max_sum);
   fclose(fo);
   return 0;
}

Ο αλγόριθμος χρειάζεται \(\mathcal{O}(N)\) χρόνο και μνήμη, και περνάει όλα τα testcases.