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

Επεξήγηση

Μας δίνονται οι συντεταγμένες \(X_i\) (με \(10.000 \leq X_i \leq 10.000\)) από \(N\) ψαρόβαρκες πάνω σε έναν άξονα, η κάθε μία από τις οποίες έχει \(M\) ψάρια. Ο ταβερνιάρης αρχικά βρίσκεται στην θέση \(0\) και σε κάθε μονάδα του χρόνου μπορεί να κινηθεί δεξιά ή αριστερά μία θέση. Σε κάθε μονάδα του χρόνου τα ψάρια κάθε ψαρόβαρκας μειώνονται κατά ένα. Σας ζητείται να βρείτε το μέγιστο πλήθος ψαριών που μπορεί να πάρει ο ταβερνιάρης.

Λύση με brute force

Η brute force λύση είναι να δοκιμάσουμε κάθε δυνατή σειρά με την οποία μπορεί ο ταβερνιάρης να επισκεφτεί τις ψαρόβαρκες. Σε κάθε βήμα έχει το πολύ δύο επιλογές: να πάει στην πιο κοντινή αριστερή ψαρόβαρκα που δεν έχει επισκεφτεί ή να πάει στην πιο κοντινή δεξιά ψαρόβαρκα που δεν έχει επισκεφτεί.

Ο αλγόριθμος παρακάτω κρατάει σε κάθε βήμα:

1. την αριστερότερη ψαρόβαρκα \(i\) που έχουμε επισκεφτεί,
2. την δεξιότερη ψαρόβαρκα \(j\) που έχουμε επισκεφτεί,
3. την απόσταση \(\mathit{dist}\) που έχει διανύσει το ταβερνιάρης από την αρχική του θέση,
4. τα ψάρια \(\mathit{total\_fish}\) που έχει μαζέψει ο ταβερνιάρης μέχρι στιγμής.

Κάθε φορά που παίρνουμε μία καινούργια ψαρόβαρκα αυξάνουμε το \(\mathit{dist}\) ανάλογα και προσθέτουμε \(M - \mathit{dist}\) στο \(\mathit{total\_fish}\).

#include <algorithm>
#include <cstdio>
#include <vector>

typedef long long ll;

std::vector<int> left, right;

ll M; 
ll cur_best = 0; // Η καλύτερη λύση μέχρι στιγμής.

/* Ψάχνουμε για την καλύτερη λύση όταν έχουμε ήδη επισκεφθεί τις i αριστερές βάρκες
   και τις j δεξιές. 
   Αν is_left==true, τότε είμαστε στην i διαφορετικά είμαστε στην j. 
   Η dist είναι ο χρόνος που έχει περάσει μέχρι τώρα και total_fish είναι τα ψάρια που 
   έχουμε μαζέψει μέχρι στιγμής.*/
void explore(int i, int j, bool is_left, ll dist, ll total_fish) {
   cur_best = std::max(cur_best, total_fish);
   // Περίπτωση 1η: Πηγαίνουμε στην αριστερή βάρκα i+1.
   if (i+1 < left.size()) {
      ll new_dist = dist + (is_left ? (left[i+1]-left[i]) : (left[i+1]+right[j]));
      explore(i + 1, j, true, new_dist, total_fish + (M - new_dist));
   }
   // Περίπτωση 2η: Πηγαίνουμε στη δεξιά βάρκα j+1.
   if (j+1 < right.size()) {
      ll new_dist = dist + (!is_left ? (right[j+1]-right[j]) : (right[j+1]+left[i]));
      explore(i, j + 1, false, new_dist, total_fish + (M - new_dist));
   }
}
 

int main() {
   FILE *fi = fopen("fishboats.in", "r");
   int N;
   fscanf(fi, "%d%lld", &N, &M);
   
   // Χωρίζουμε τις συντεταγμένες σε αρνητικές και θετικές.
   left.push_back(0);
   right.push_back(0);
   for (int i = 0; i < N; ++i) {
      int tmp;
      fscanf(fi, "%d", &tmp);
      if (tmp < 0) left.push_back(-tmp);
      else right.push_back(tmp);
   }
   fclose(fi);
   
   std::sort(left.begin(), left.end());
   std::sort(right.begin(), right.end());

   explore(0, 0, true, 0, 0);

   FILE *fo = fopen("fishboats.out", "w");
   fprintf(fo, "%lld\n", cur_best);
   fclose(fo);
   
   return 0;
}

Υπάρχουν το πολύ \(2\) επιλογές σε κάθε βήμα και κάθε βήμα παίρνει \(\mathcal{O}(1)\) χρόνο άρα συνολικά ο αλγόριθμος χρειάζεται \(\mathcal{O}(2^{N})\) χρόνο¹ και \(\mathcal{O}(N)\) μνήμη. Ο αλγόριθμος περνάει 26 από τα 39 testcases.

Σημείωση: Αν σταματήσουμε να ψάχνουμε μία δυνατή σειρά όταν η απόσταση \(\mathit{dist}\) είναι μεγαλύτερη από τα ψάρια \(M\), δηλαδή προσθέσουμε τον εξής έλεγχο

void explore(int i, int j, bool is_left, ll dist, ll total_fish) {
   // Δεν χρειάζεται να συνεχίσουμε αν παίρνουμε αρνητικό αριθμό ψαριών.
   if (M < dist) return;
   cur_best = std::max(cur_best, total_fish);

τότε η λύση περνάει 29 από τα 39 testcases (ολόκληρη η λύση εδώ).

Λυση με δυναμικό προγραμματισμό

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

Παρατήρηση: Αν πρόκειται να επισκεφτούμε \(len\) ψαρόβαρκες, και η \(i\)-οστή που επισκεφτούμε είναι η \(x_{j}\) (και προηγουμένως ήμασταν στην \(x_{k}\)), τότε αυτή η μετακίνηση θα μας κοστίσει \((len - i + 1) \cdot \lvert x_{j} - x_{k}\rvert\) ψάρια (από την \(i\)-οστή και τις μετέπειτα \(len - i\) ψαρόβαρκες).

Για παράδειγμα στην παρακάτω διαδρομή επισκεφτόμαστε την πρώτη βάρκα την στιγμή \(t_1 = 2\), την δεύτερη την στιγμή \(t_2 = 2 + 5\), την τρίτη την στιγμή \(t_3 = 2 + 5 + 8\) και την τέταρτη την στιγμή \(t_4 = 2 + 5 + 8 + 14\). Επομένως τα ψάρια που παίρνουμε είναι \(4M - (t_1 + t_2 + t_3 + t_4)\) που μετά από μία αναδιάταξη είναι ίσο με \(4M - (4 \cdot 2 + 3 \cdot 5 + 2 \cdot 8 + 1 \cdot 14)\), που επιβεβαιώνει την παραπάνω παρατήρηση (η πρώτη απόσταση (\(2\)) χρησιμοποιείται \(4\) φορές, η δεύτερη (\(5\)) χρησιμοποιείται \(3\) φορές, κοκ).

Επειδή δεν γνωρίζουμε εξ’αρχής πόσες ψαρόβαρκες περιλαμβάνονται στην βέλτιστη λύση, θα δοκιμάσουμε όλα τα δυνατά πλήθη \(\mathit{len}\), δηλαδή \(\mathit{len} = 0, 1, 2, \ldots, n\). Γνωρίζοντας αυτή την πληροφορία, μπορούμε να υπολογίσουμε τον μέγιστο αριθμό ψαριών \(dp[len][i][k][is\_right]\) για να πάρουμε τις \(i\) αριστερές ψαρόβαρκες και τις \(j\) δεξιές ψαρόβαρκες, όταν είμαστε στην \(i\) (\(is\_right = 0\)), ως εξής:

και όταν είμαστε στην \(j\), ως εξής:

Και η απάντηση είναι η μέγιστη τιμή από τα \(\max( dp[\mathit{len}][i][j][0], dp[\mathit{len}][i][j][1])\) με \(i\) και \(j\) να ικανοποιούν \(i + j = len\).

Επειδή οι λύσεις για το \(len\) είναι ανεξάρτητες, μπορούμε να χρησιμοποιήσουμε \(N\) φορές τον ίδιο πίνακα \(dp\). Ο κυρίως κώδικας δίνεται παρακάτω (και ολόκληρος εδώ):

   ll cur_best = 0;
   // Δοκιμάζουμε όλα τα δυνατά πλήθη ψαρόβαρκων στη βέλτιση λύση.
   for (int total_boats = 1; total_boats <= N; ++total_boats) {
      for (int i = 0; i < left.size(); ++i) {
         int mx_j = std::min(total_boats - i + 1, (int) right.size());
         for (int j = 0; j < mx_j; ++j) {
            if (i == 0 && j == 0) continue;
            int remaining_boats = total_boats - (i + j) + 1;
            dp[i][j][0] = dp[i][j][1] = -INF;
            if (i >= 1) dp[i][j][0] = M + std::max(
               dp[i-1][j][0] - remaining_boats * (left[i] - left[i-1]),
               dp[i-1][j][1] - remaining_boats * (left[i] + right[j]));
            if (j >= 1) dp[i][j][1] = M + std::max(
               dp[i][j-1][1] - remaining_boats * (right[j] - right[j-1]),
               dp[i][j-1][0] - remaining_boats * (left[i] + right[j]));
            // Η λύση είναι πιθανή μόνο όταν i+j == total_boats.
            if (i + j == total_boats) cur_best = std::max(
               cur_best, 
               std::max(dp[i][j][0], dp[i][j][1]));
         }
      }
   }
   

Ο αλγόριθμος χρειάζεται \(\mathcal{O}(N^3)\) χρόνο και \(\mathcal{O}(N^2)\) μνήμη. Παρατηρώντας ότι σε κάθε επανάληψη του \(j\) χρησιμοποιούμε μόνο τιμές της μορφής \(dp[i-1][\cdot][\cdot]\) ή \(dp[i][\cdot][\cdot]\), μπορούμε να μειώσουμε την μνήμη σε \(\mathcal{O}(N)\) (δείτε τον κώδικα εδώ).

Άπληστη λύση

Μία άπληστη λύση είναι να πάμε πρώτα προς τα δεξιά και μετά προς τα αριστερά. Και αντίστοιχα μία φορά προς τα αριστερά και μετά προς τα δεξιά. Η λύση αυτή είναι εύκολο να υλοποιηθεί σε \(\mathcal{O}(N^2)\) χρόνο, πχ με τον εξής κώδικα (και ολόκληρος εδώ):

void find_best() {
   ll cur_dist = 0;
   ll cur_fish = 0;
   ll prev = 0;
   for (int i = 0; i < right.size(); ++i) {
      cur_dist += right[i] - prev;
      prev = right[i];
      cur_fish += i > 0 ? (M - cur_dist) : 0;
      cur_best = std::max(cur_best, cur_fish);
      
      // Δοκιμάζουμε να κάνουμε στροφή εδώ προς τα αριστερά.
      ll new_cur_dist = cur_dist, new_cur_fish = cur_fish, 
         new_prev = -right[i];
      for (int j = 1; j < left.size(); ++j) {
         new_cur_dist += left[j] - new_prev;
         new_prev = left[j];
         new_cur_fish += (M - new_cur_dist);
         cur_best = std::max(cur_best, new_cur_fish);
      }
   }
}

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

Στα δοσμένα testcases περνάει το 19 στα 29 testcases.

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

Στα δοσμένα testcases περνάει 29 από τα 39 testcases.