35ος ΠΔΠ B' Φάση: Η σκυταλοδρομία (fairdiv) - Λύση

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

Μας δίνονται \(N\) μη-αρνητικοί ακέραιοι \(A_0, \ldots, A_{N-1}\). Θέλουμε να τους χωρίσουμε σε τρία μέρη \(S_A = A_0 + \ldots + A_{i_A}\), \(S_B = A_{i_A + 1} + \ldots + A_{i_B}\) και \(S_C = A_{i_B + 1} + \ldots + A_{N - 1}\) έτσι ώστε \(S_A \geq S_B \geq S_C\) και το \(S_C\) είναι όσο πιο μεγάλο γίνεται. Από όλες τις λύσεις που μεγιστοποιούν το \(S_C\), διαλέγουμε αυτήν που μεγιστοποιεί το \(S_B\).

Brute force λύση

Υπάρχουν συνολικά \(N-1\) θέσεις για το \(i_A\) και το πολύ \(N-2\) θέσεις για το \(i_B\). Το \(i_A\) και το \(i_B\) καθορίζουν τα \(S_A\), \(S_B\) και \(S_C\). Μπορούμε, επομένως να δοκιμάσουμε όλες τις πιθανές μοιρασιές και να υπολογίσουμε τα \(S_A, S_B, S_C\) (διατρέχοντας μία φορά τον πίνακα) κρατώντας την καλύτερη από αυτές.

#include <cstdio>
#include <vector>

long N;
std::vector<int> A;

// Υπολογίζουμε το άθροισμα a_i + ... + a_j.
long compute_sum(long i, long j) {
   long sum = 0;
   for (long k = i; k <= j; ++k) {
      sum += A[k];
   }
   return sum;
}

int main() {
   FILE *fi = fopen("fairdiv.in", "r");
   fscanf(fi, "%ld", &N);
   A = std::vector<int>(N);
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%d", &A[i]);
   }
   fclose(fi);
   
   // Δοκιμάζουμε όλες τις δυνατές μοιρασιές.
   long opt_A = 0, opt_B = 0, opt_C = 0;
   for (long iA = 0; iA < N; ++iA) {
      for (long iB = iA; iB < N; ++iB) {
         long sum_A = compute_sum(0, iA); 
         long sum_B = compute_sum(iA + 1, iB);
         long sum_C = compute_sum(iB + 1, N - 1);
         if (sum_A >= sum_B && sum_B >= sum_C) {
            if (sum_C > opt_C || (sum_C == opt_C && sum_B >= opt_B)) {
               opt_A = sum_A;
               opt_B = sum_B;
               opt_C = sum_C;
            }
         }
      }
   }
   
   FILE *fo = fopen("fairdiv.out", "w");
   fprintf(fo, "%ld %ld %ld\n", opt_A, opt_B, opt_C);
   fclose(fo);
   return 0;
}

Υπάρχουν συνολικά \((N-1) \cdot (N-2) = \mathcal{O}(N^2)\) δυνατές μοιρασιές και η συνάρτηση \(\texttt{compute\_sum}\) χρειάζεται \(\mathcal{O}(N)\) χρόνο. Επομένως, ο αλγόριθμος χρειάζεται συνολικά \(\mathcal{O}(N^3)\) χρόνο για να τρέξει.

Λύση με prefix sums

Μπορούμε να επιταχύνουμε τον παραπάνω αλγόριθμο, επιταχύνοντας τη συνάρτηση \(\texttt{compute\_sum}\). Πιο συγκεκριμένα μπορούμε να υπολογίσουμε τα prefix sums (προθεματικά αθροίσματα) \(S[\cdot]\), όπου \(S[i+1] = A_0 + \ldots + A_i\) και \(S[0] = 0\).

Συνεπώς το άθροισμα \(A_i + \ldots + A_j\) για οποιαδήποτε \(i\) και \(j\) (με \(j \geq i\)) δίνεται από τον τύπο \(S[j+1] - S[i]\) (μπορείτε να δείτε γιατί;¹).

Το μόνο που χρειάζεται να αλλάξουμε είναι η υλοποίηση αυτής της συνάρτησης

// Υπολογίζουμε το άθροισμα a_i + ... + a_j.
long compute_sum(long i, long j) {
   if (j < i) return 0;
   return S[j+1] - S[i];
}

και να προϋπολογίσουμε τις τιμές του \(S[\cdot]\)

   S[0] = 0;
   for (long i = 0; i < N; ++i) {
      fscanf(fi, "%d", &A[i]);
      S[i+1] = S[i] + A[i];
   }

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

Λύση με δυαδική αναζήτηση

Ξεκινάμε με την εξής παρατήρηση:

Παρατήρηση: Έστω ότι έχουμε αποφασίσει ότι θα δώσουμε τα στοιχεία \(A_0, \ldots, A_{i_A}\) στον \(A\). Τότε, αυξάνοντας το \(i_B\) το άθροισμα \(S_B\) αυξάνει (ή μένει το ίδιο). Επομένως, θέλουμε να βρούμε το μικρότερο \(i_B\) ώστε \(S_B \geq S_C\), καθώς αυτό μεγιστοποιεί το \(S_C\).

Επειδή έχουμε ότι το \(S_B\) αυξάνει μονότονα, μπορούμε να χρησιμοποιήσουμε δυαδική αναζήτηση για να βρούμε το βέλτιστο \(i_B\) για κάθε \(i_A\), δηλαδή το μικρότερο \(i_B > i_A\) τέτοιο ώστε \(A_{i_A+1} + \ldots + A_{i_B} > A_{i_B + 1} + \ldots + A_{N-1}\). Ο παρακάτω κώδικας υλοποιεί το μέρος της δυαδικής αναζήτητης.

   long opt_A = 0, opt_B = 0, opt_C = 0;
   for (long iA = 0; iA < N; ++iA) {
      long st = iA;
      long en = N - 1;
      while (st < en) {
         long md = (st + en) / 2;
         long sum_B = compute_sum(iA + 1, md);
         long sum_C = compute_sum(md + 1, N - 1);
         if (sum_B < sum_C) st = md + 1;
         else en = md;
      }
      long iB = st;
      
      // Ελέγχουμε αν η τωρινή λύση είναι η καλύτερη.

Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ. Κάθε δυαδική αναζήτηση θέλει \(\mathcal{O}(\log N)\) χρόνο, συνεπώς ο αλγόριθμος χρειάζεται συνολικά \(\mathcal{O}(N \log N)\) χρόνο.

Λύση με δύο δείκτες

Για να λύσουμε το πρόβλημα σε \(\mathcal{O}(N)\) χρόνο, κάνουμε την εξής παρατήρηση:

Παρατήρηση: Έστω ότι έχουμε αποφασίσει ότι θα δώσουμε τα στοιχεία \(A_0, \ldots, A_{i_A}\) στον \(A\) και η βέλτιστη μοιρασιά για τα υπόλοιπα στοιχεία χρησιμοποιούν το \(i_B\). Τότε, η βέλτιστη λύση για το \(i_A' = i_A - 1\) θα έχει \(i_B' \leq i_B\), δηλαδή ο δείκτης μετακινείτε προς τα αριστερά (ή μένει στο ίδιο σημείο).

Για παράδειγμα, αλλάζοντας το \(i_A = 2\) σε \(i_A' = 1\), οδηγεί στο βέλτιστο \(i_B\) από \(8\) σε \(i_B' = 4\).

Ο λόγος που το \(i_B\) μετακινείται προς τα αριστερά είναι ότι το \(S_B\) μεγαλώνει, επομένως δίνεται η δυνατότητα στο \(S_C\) να μεγαλώσει.

Συνεπώς, ξεκινώντας από \(i_A = N - 1\) και \(i_B = N\), μετακινούμε το \(i_A\) προς τα αριστερά κατά μία θέση, και μετά το \(i_B\) όσο χρειάζεται προς τα αριστερά. Ως τελική απάντηση δίνουμε το βέλτιστο από όλα τα \(i_A\).

   long iB = N, sum_A = sum, sum_B = 0, sum_C = 0;
   long opt_A = sum, opt_B = 0, opt_C = 0;
   
   // Βρίσκουμε την καλύτερη μοιρασιά αν έχουμε δώσει 
   // τα στοχεία a_0, ... , a_{iA} στον A. 
   for (long iA = N - 2; iA >= 0; --iA) {
      sum_A -= A[iA + 1];
      sum_B += A[iA + 1];
      while (iB > iA + 1 && sum_B - A[iB]  >= sum_C + A[iB]) {
         sum_B -= A[iB];
         sum_C += A[iB];
         --iB;
      }
      
      // Ελέγχουμε αν η τωρινή λύση είναι η καλύτερη.

Επειδή το \(i_B\) μπορεί να μετακινηθεί το πολύ \(N\) θέσεις, η εσωτερική επανάληψη μπορεί να εκτελεστεί το πολύ \(N\) φορές καθ’όλη την εκτέλεση του αλγορίθμου. Έτσι, παρότι με μια πρόχειρη ματιά θα νομίζαμε ότι ο αλγόριθμος τρέχει σε \(\mathcal{O}(N^2)\) χρόνο, στην πραγματικότητα τρέχει μόνο σε \(\mathcal{O}(N)\) χρόνο. Για παρόμοια παραδείγματα, μπορείτε να ψάξετε “amortized analysis”.