37ος ΠΔΠ Α' Φάση: Όμοιες πίτσες (samepizzas) - Λύση

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

Μας δίνονται \(N\) υλικά και οι ποσότητες \(A_1, \ldots, A_N\) του κάθε υλικού. Θέλουμε να φτιάξουμε το μέγιστο δυνατό αριθμό από πίτσες με τα ίδια υλικά, με τον περιορισμό αυτές να έχουν τουλάχιστον \(K\) διαφορετικά υλικά.

Θα ξεκινήσουμε με δύο βασικές παρατηρήσεις. Ας υποθέσουμε ότι \(K = 3\) και επιπλέον ότι έχουμε διαλέξει τα υλικά με ποσότητες \(3, 5, 8\). Τότε, το πλήθος από πίτσες που μπορούμε να φτιάξουμε είναι \(3\), δηλαδή το ελάχιστο από αυτές τις ποσότητες.

Επιπλέον αν υπήρχε ένα στοιχείο που είναι μεγαλύτερο από το \(3\), π.χ. το \(6\), τότε αλλάζοντάς το με το \(3\), μπορούμε να φτιάξουμε \(5\) πίτσες (που είναι περισσότερες από τις \(3\) που μπορούσαμε προηγουμένως).

Συνδυάζοντας αυτές τις δύο παρατηρήσεις, αν οι ποσότητες είναι \(3, 8, 5, 10, 12, 6\) και \(K = 3\) μας συμφέρει να πάρουμε τα τρία υλικά με τις μεγαλύτερες ποσότητες, δηλαδή τα \(12, 10, 8\) και οι πίτσες που μπορούμε να φτιάξουμε είναι \(8\), η μικρότερη από αυτές τις τιμές. Ισοδύναμα, αν ταξινομήσουμε τις ποσότητες σε φθίνουσα σειρά \(12, 10, 8, 6, 5, 3\), τότε η απάντηση είναι η τρίτη (δηλαδή η \(K\)-οστή) τιμή.

Λύση με ταξινόμηση (100%)

Ένας τρόπος να βρούμε την \(K\)-οστή μεγαλύτερη τιμή είναι να ταξινομήσουμε τον πίνακα και μετά να βρούμε ποια τιμή είναι στην θέση A[K-1]. Στις περισσότερες γλώσσες προγραμματισμού υπάρχει μία συνάρτηση sort που υλοποιεί την ταξινόμηση σε χρόνο \(O(N \log N)\). Για παράδειγμα, στην C++ αυτό γίνεται ως εξής:

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

int main(){
   FILE *in = fopen("samepizzas.in", "r");
   long P, N, K;
   fscanf(in, "%ld", &P);
   fscanf(in, "%ld%ld", &N, &K);
   
   std::vector<long> A(N);
   for(long i = 0; i < N; i++) fscanf(in, "%ld", &A[i]);
   fclose(in);
   
   // Το std::greater<long>() χρειάζεται ώστε η ταξινόμηση 
   // να γίνει σε φθίνουσα σειρά.
   std::sort(A.begin(), A.end(), std::greater<long>());
    
   FILE *out= fopen("samepizzas.out", "w");
   fprintf(out, "%ld\n", A[K-1]);
   fclose(out);
   
   return 0;
}

Επίσης, μπορείτε να υλοποιήσετε κάποιον από τους γρήγορους αλγορίθμους ταξινόμησης όπως η mergesort, η quicksort ή η heapsort. Αν υλοποιήσετε κάποιους από τους πιο αργούς όπως η insertion sort ή η bubble sort, τότε η λύση σας θα έχει πολυπλοκότητα \(O(N^2)\) και θα περάσει μόνο τα υποπροβλήματα 1 και 4.

Λύση με select (100%)

Η λύση με την ταξινόμηση χρειάζεται χρόνο \(N \log N\) στην χειρότερη περίπτωση. Υπάρχει όμως ένας αλγόριθμος που βρίσκει ακριβώς το \(K\)-οστό στοιχείο σε \(O(N)\) βήματα. Στην C++ ο αλγόριθμος αυτός καλείται με την συνάρτηση std::nth_element, ως εξής

   std::nth_element(
      A.begin(),              // Αρχή του πίνακα.
      A.begin() + (K-1),      // Θέση του στοιχείου που θέλουμε (δηλαδή το Κ-οστό).
      A.end(),                // Τέλος του πίνακα.
      std::greater<long>());  // Ταξινόμηση σε φθίνουσα σειρά.

Δείτε ολόκληρο τον κώδικα εδώ.

Το \(k\)-οστό μεγαλύτερο στοιχείο μπορούμε επίσης να το βρούμε με:

Δυαδική αναζήτηση σε χρόνο \(O(N \log N)\) (Δείτε ολόκληρο τον κώδικα εδώ)

   long st = mn, en = mx;
   while (st < en) {
      long md = (st + en + 1) / 2;
      long cnt = 0;
      for (auto v : A) cnt += (v >= md);
      if (cnt >= K) st = md;
      else en = md - 1;
   }

Ουρά προτεραιότητας, όπου κρατάμε τα \(K\) μεγαλύτερα στοιχεία που έχουμε συναντήσει μέχρι στιγμής, σε χρόνο \(O(N \log K)\). (Δείτε ολόκληρο τον κώδικα εδώ)

   // Ορίζουμε μία ουρά προτεραιότητας που κρατάει τα Κ μεγαλύτερα στοιχεία, 
   // και το top() επιστρέφει το μικρότερο από αυτά.
   std::priority_queue<long, std::vector<long>, std::greater<long>> pq;
   for (long i = 0; i < K; ++i) pq.push(A[i]);
   for (long i = K; i < N; ++i) {
      if (A[i] > pq.top()) {
         pq.pop();
         pq.push(A[i]);
      }
   }

Λύσεις για συγκεκριμένα υποπροβλήματα

Τα υποπροβλήματα μπορούν να λυθούν ως εξής:

Υποπρόβλημα 1 \(N = 2\): Όταν \(K = 1\), τότε η απάντηση είναι \(\max(A_1, A_2)\), διαφορετικά είναι \(\min(A_1, A_2)\) (κώδικας).
Υποπρόβλημα 2 \(K = N\): Η απάντηση είναι \(\min(A_1, \ldots, A_n)\) (κώδικας).
Υποπρόβλημα 3 \(K = 1\): Η απάντηση είναι \(\max(A_1, \ldots, A_n)\) (κώδικας).
Υποπρόβλημα 4 \(N \leq 10.000\): Σε αυτή την περίπτωση περνάνε και οι λιγότερο αποδοτικοί αλγόριθμοι ταξινόμησης (όπως η insertion sort) (κώδικας)