34ος ΠΔΠ Γ' Φάση: Οι ορχήστρες (orchestras) - Λύση

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

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

Λύση για Κ = 2

Θα ξεκινήσουμε με την περίπτωση που έχουμε \(K = 2\) όργανα. Σύμφωνα με την εκφώνηση, το 50% των testcases έχουν \(K = 2\).

Έστω ότι οι οργανοπαίχτες για το πρώτο όργανο έχουν αμοιβές \(a_1, \ldots , a_N\) και \(b_1, \ldots , b_N\) για το δεύτερο. Τότε κάνουμε την εξής βασική παρατήρηση:

Παρατήρηση: Στην βέλτιστη λύση για κάθε δύο ορχήστρες \((a_{i_1}, b_{j_1})\) και \((a_{i_2}, b_{j_2})\), αν \(a_{i_1} < a_{i_2}\) τότε \(b_{i_1} \leq b_{i_2}\).

(Αιτιολόγηση) Ας υποθέσουμε ότι \(a_{i_1} < a_{i_2}\) και \(b_{i_1} > b_{i_2}\). Τότε υπάρχουν οι εξής περιπτώσεις (εστιάζουμε σε αυτές με \(a_{i_1} < b_{i_2}\) γιατί οι άλλες είναι συμμετρικές):

Σε κάθε μία από αυτές, αν αλλάξουμε τα ζεύγη σε \((a_{i_1}, b_{j_2})\) και \((a_{i_2}, b_{j_1})\), τότε η μέγιστη απόκλιση μικραίνει ή παραμένει η ίδια:

Στις πρώτες δύο περιπτώσεις η απόκλιση ήταν η μέγιστη δυνατή, άρα γίνεται μικρότερη με την αλλαγή. Στην τρίτη περίπτωση και η κόκκινη και η πράσινη απόκλιση μικραίνουν, άρα η συνολική απόκλιση μικραίνει. \(\quad\square\)

Χρησιμοποιώντας αυτή την παρατήρηση, έχουμε την εξής λύση:

1. Ταξινομούμε τις αμοιβές \(a\) και \(b\).
2. Δημιουργούμε τις ορχήστρες \((a_i, b_i)\) για \(i = 1, \ldots, N\).
3. Βρίσκουμε την μέγιστη διαφορά \(b_i - a_i\).

Ο παρακάτω κώδικας υλοποιεί αυτόν τον αλγόριθμο:

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

int main() {
   long N, K, tmp;
   FILE *fi = fopen("orchestras.in", "r");
   fscanf(fi, "%ld %ld\n", &N, &K);
   std::vector<long> a, b;
   for (long j = 0; j < N; ++j) {
      fscanf(fi, "%ld", &tmp);
      a.push_back(tmp);
   }
   for (long j = 0; j < N; ++j) {
      fscanf(fi, "%ld", &tmp);
      b.push_back(tmp);
   }
   fclose(fi);
   
   // Ταξινομούμε τους παίχτες κάθε οργάνου.
   std::sort(a.begin(), a.end());
   std::sort(b.begin(), b.end());
   
   // Βρίσκουμε τη μέγιστη απόκλιση από τις ορχήστρες
   // που δημιουργήσαμε.
   long ans = std::abs(a[0] - b[0]);
   for (long j = 0; j < N; ++j) {
      ans = std::max(ans, std::abs(a[j] - b[j]));
   }
   
   FILE *fo = fopen("orchestras.out", "w");
   fprintf(fo, "%ld\n", ans);
   fclose(fo);
   return 0;
}

Η πολυπλοκότητα για την ταξινόμηση είναι \(\mathcal{O}(N \log N)\), άρα συνολικά χρειαζόμαστε \(\mathcal{O}(N \log N)\) χρόνο¹.

Γενική λύση

Επεκτείνοντας την παραπάνω λύση για \(K > 2\):

1. Ταξινομούμε τους οργανοπαίχτες του κάθε οργνάνου κατά μη-φθίνουσα αμοιβή.
2. Για κάθε \(i = 1, \ldots, N\), δημιουργούμε μία ορχήστρα με τον \(i\)-οστό πιο ακριβοπληρωμένο οργανοπαίχτη για κάθε όργανο.
3. Βρίσκουμε τη διαφορά του μέγιστου και ελάχιστου σε κάθε ορχήστρα.

Ο αλγόριθμος αυτός είναι σωστός, καθώς από την παραπάνω παρατήρηση κάθε ζευγάρι οργάνων \(a\) και \(b\) έχει ταιριασμένους τους οργανοπαίχτες που βρίσκονται σε μη φθίνουσα σειρά.

Ο παρακάτω κώδικας υλοποιεί αυτόν τον αλγόριθμο:

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

const size_t MAXA = 1'000'000;

int main() {
   long N, K;
   FILE *fi = fopen("orchestras.in", "r");
   fscanf(fi, "%ld %ld\n", &N, &K);
   std::vector<long> v[K];
   for (long i = 0; i < K; ++i) {
      for (long j = 0; j < N; ++j) {
         long tmp;
         fscanf(fi, "%ld", &tmp);
         v[i].push_back(tmp);
      }
      // Ταξινομούμε τους παίχτες του ίδιου οργάνου.
      std::sort(v[i].begin(), v[i].end());
   }
   fclose(fi);
   
   long ans = -1;
   for (long j = 0; j < N; ++j) {
      // Βρίσκουμε για κάθε ορχήστρα την απόκλιση.
      long cur_min = MAXA, cur_max = -1;
      for (long i = 0; i < K; ++i) {
         if (v[i][j] < cur_min) cur_min = v[i][j];
         if (v[i][j] > cur_max) cur_max = v[i][j];
      }
      long diff = cur_max - cur_min;
      if (ans < diff) ans = diff;
   }
   
   FILE *fo = fopen("orchestras.out", "w");
   fprintf(fo, "%ld\n", ans);
   fclose(fo);
   return 0;
}

Η πολυπλοκότητα αυτού του αλγορίθμου είναι \(\mathcal{O}(NK \log (N))\).

Σημείωση: Αφού το εύρος \(A\) των αμοιβών είναι περιορισμένο \(A \leq 10^6\)), μπορούμε να χρησιμοποιήσουμε την counting sort για ταξινόμηση. Πιο συγκεκριμένα η χρονική πολυπλοκότητα γίνεται \(\mathcal{O}(NK + A)\). Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.

Brute force

Η παρακάτω λύση δουλεύει μόνο για μικρά \(N\) και \(K\) και είναι σχετικά πιο πολύπλοκη στην υλοποίηση από την βέλτιστη λύση. Όμως μπορεί να σας φανεί χρήσιμη για να μάθετε τεχνικές για brute force.

Θα δημιουργήσουμε όλες τις δυνατές ορχήστρες και θα βρούμε αυτή που έχει την μικρότερη απόκλιση. Για κάθε όργανο, θα πρέπει να αναθέσουμε τους οργανοπαίχτες. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.

Για να κάνουμε τον κώδικα λίγο πιο αποδοτικό (και να περάσει το 6^ο testcase) θα κάνουμε τα εξής:

1. Θα σταματήσουμε την απαρίθμηση αν η μέγιστη απόκλιση στην τωρινή είναι μεγαλύτερη από την καλύτερη που έχουμε βρει μέχρι στιγμής².
2. Για το πρώτο όργανο δεν θα δημιουργήσουμε όλες τις δυνατές αναδιατάξεις.

Για \(N\) αντικείμενα υπάρχουν \(N!\) αναδιατάξεις, επομένως υπάρχουν \(\mathcal{O}( (N!)^{K N - 1})\) δυνατές ορχήστρες. Άρα ο αλγόριθμος χρειάζεται \(\mathcal{O}( N \cdot (N!)^{K N - 1})\) χρόνο, που είναι αρκετό για να περάσει 50% των testcases.