35ος ΠΔΠ Γ' Φάση: Χημικές Ενώσεις (chemicals) - Λύση

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

Μας δίνεται ένας πίνακας \(A\) από \(N\) ακεραίους αριθμούς και ένας ακέραιος αριθμός \(K\). Μας ζητείται να βρούμε το μήκος του μεγαλύτερου διαστήματος \([i, j]\) ώστε να μην υπαρχει ζεύγος \(s, t\) στο \([i, j]\) με άθροισμα \(A[s] + A[t]\) που να είναι πολλαπλάσιο του \(K\).

Brute force \(\mathcal{O}(N^4)\)

Υπάρχουν συνολικά \(\mathcal{O}(N^2)\) διαστήματα \([i, j]\) και κάθε διάστημα έχει το πολύ \(\mathcal{O}(N^2)\) ζευγάρια. Επομένως, μπορούμε να ελέγξουμε ένα ένα τα διαστήματα συνολικά σε \(\mathcal{O}(N^4)\) χρόνο.

#include <algorithm>
#include <cstdio>

const size_t MAXN = 1'000'000;
long A[MAXN];

int main() {
   FILE *fi = fopen("chemicals.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_range = 0;
   // Δοκιμάζουμε όλα τα δυνατά διαστήματα [i, j].
   for (long i = 0; i < N; ++i) {
      for (long j = i; j < N; ++j) {
         // Δοκιμάζουμε όλα τα δυνατά ζεύγη (s, t) στο [i, j].
         bool found_pair = false;
         for (long s = i; s <= j && !found_pair; ++s) {
            for (long t = s + 1; t <= j && !found_pair; ++t) {
               if ((A[s] + A[t]) % K == 0) {
                  found_pair = true;
               }
            }
         }
         if (!found_pair) {
            max_range = std::max(max_range, j - i + 1);
         }
      }
   }
   
   FILE *fo = fopen("chemicals.out", "w");
   fprintf(fo, "%ld\n", max_range);
   fclose(fo);
   
   return 0;
}

Brute force \(\mathcal{O}(N^3)\)

Μπορούμε να επιταγχύνουμε την παραπάνω λύση ως εξής: ξέροντας ότι το διάστημα \([i, j-1]\) δεν έχει κάποιο ζευγάρι που να είναι πολλαπλάσιο του \(K\), τότε για το διάστημα \([i, j]\) αρκεί να ελέγξουμε ότι τα ζευγάρια \((i, j), (i+1, j), \ldots, (j-2, j), (j-1, j)\) έχουν ζευγάρια που δεν είναι πολλαπλάσια του \(K\). Επειδή υπάρχουν το πολύ \(\mathcal{O}(N)\) ζευγάρια με το \(j\), ο αλγόριθμος παίρνει συνολικά \(\mathcal{O}(N^3)\) χρόνο.

   for (long i = 0; i < N; ++i) {
      for (long j = i; j < N; ++j) {
         // Δοκιμάζουμε όλα τα δυνατά ζεύγη (k, j) στο [i, j].
         bool found_pair = false;
         for (long k = i; k < j && !found_pair; ++k) {
            if ((A[k] + A[j]) % K == 0) found_pair = true;
         }
         if (!found_pair) {
            max_range = std::max(max_range, j - i + 1);
         } else {
            // Αν βρούμε ζευγάρι που δεν είναι καλό, τότε βγαίνουμε από το loop.
            break;
         }
      }
   }

Ολόκληρος ο κώδικας είναι εδώ.

Brute force με hash set \(\mathcal{O}(N^2)\)

Mπορούμε να επιταγχύνουμε περαιτέρω την παραπάνω λύση, κάνοντας την εξής παρατήρηση:

Παρατήρηση: Δύο στοιχεία \(A[s]\) και \(A[t]\) έχουν άθροισμα πολλαπλάσιο του \(K\) αν και μόνο αν \(A[s] \equiv (K - A[t]) \pmod{K}\).

(Αιτιολόγηση) Μπορούμε να ελέγξουμε ότι \(A[s] + A[t]\) είναι πολλαπλάσιο του \(K\), καθότι \((A[s] + A[t]) \equiv ((K - A[t]) + A[t]) \equiv 0 \pmod{K}\).

Επομένως, διατηρώντας σε ένα hash set \(S\) τα στοιχεία \(A[i], \ldots, A[j-1]\), μπορούμε να ελέγξουμε γρήγορα αν το στοιχείο \(A[j]\) συμμετέχει σε κάποια δυάδα με άθροιμα \(A[\ell] + A[j]\) που είναι πολλαπλάσιο του \(K\), κοιτώντας αν υπάρχει το στοιχείο \((K - (A[j] \% K) ) \% K\) στο \(S\).¹

   // Δοκιμάζουμε όλα τα δυνατά διαστήματα [i, j].
   for (long i = 0; i < N; ++i) {
      std::unordered_set<long> rems;
      bool found_pair = false;
      long j;
      for (j = i; j < N; ++j) {
         if (rems.find( (K - (A[j] % K) ) % K ) != rems.end()) {
            found_pair = true;
            break;
         }
         rems.insert(A[j] % K);
      }
      max_range = std::max(max_range, k - i);
   }

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

Δύο δείκτες \(\mathcal{O}(N)\)

Γενικεύοντας την προηγούμενη λύση, μπορούμε να υπολογίσουμε για κάθε δείκτη \(j\) το μεγαλύτερο διάστημα \([\ell, j]\) για το οποίο δεν υπάρχει ζεύγος \(t, s \in [\ell, j]\) με άθροισμα \(A[s] + A[t]\) που δεν είναι πολλαπλάσιο του \(K\). Έχοντας την βέλτιση λύση για το \(j-1\) έστω \([\ell, j-1]\), μπορούμε να υπολογίσουμε την βέλτιση λύση για το \(j\) μετακινώντας το \(\ell\) έως ότου προσπεράσουμε όλα τα στοιχεία ίσα με \((K - (A[j] \% K) ) \% K\).

   // Δοκιμάζουμε όλα τα δυνατά διαστήματα [i, j].
   std::unordered_map<long, long> rems;
   long left = 0;
   for (long i = 0; i < N; ++i) {
      long target = (K - (A[i] % K) ) % K;
      while (rems[target] > 0) {
         --rems[A[left] % K];
         ++left;
      }
      ++rems[A[i] % K];
      max_range = std::max(max_range, i - left + 1);
   }

Για το δεύτερο παράδειγμα, οι δύο δείκτες αλλάζουν ως εξής, δίνοντας το μέγιστο στο 5ο βήμα:

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