22ος ΠΔΠ Γ' Φάση: Servers (servers) - Λύση

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

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

Και οι τρεις παρακάτω λύσεις χωρίζουν το πρόβλημα: (1) στη μέτρηση των συνολικών αριθμών εμανίσεων σελίδας για κάθε σελίδα και (2) στην εύρεση των \(K\) πιο συχνών.

Λύση με διπλή ταξινόμηση

Για να μετρήσουμε το συνολικό αριθμό εμφανίσεων για κάθε σελίδα, ταξινομούμε τα ζευγάρια με βάση το ID τους. Έτσι τα ζευγάρια με το ίδιο ID γίνονται γειτονικά μετά την ταξινόμηση. Στο παράδειγμα της εκφώνησης, τα πρώτα ταξινομημένα ζευγάρια θα είναι τα εξής:

Επομένως, αρκεί να διατρέξουμε αυτόν τον πίνακα και να αθροίσουμε τα ζευγάρια με τα ίδια ID. Αυτά τα βάζουμε σε έναν καινούργιο πίνακα:

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

Η πρώτη ταξινόμηση χρειάζεται \(\mathcal{O}(NM \log (NM))\) και η δεύτερη \(\mathcal{O}(M \log M)\) χρόνο. Επίσης, χρειάζεται \(\mathcal{O}(NM)\) χρόνο για να αθροίσουμε τα ζευγάρια. Επομένως, συνολικά αυτή η λυση χρειάζεται \(\mathcal{O}(NM \log (NM))\) χρόνο και \(\mathcal{O}(NM)\) μνήμη.

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


int main() {
   int M, N, K;
   FILE *fi = fopen("servers.in", "r");
   fscanf(fi, "%d%d%d", &M, &N, &K);
   std::vector<std::pair<int, int>> pairs;
   for (int i = 0; i < N; ++i) {
      for (int j = 0; j < M; ++j) {
         int x, y;
         fscanf(fi, "%d%d", &x, &y);
         pairs.push_back({ x, y });
      }
   }
   fclose(fi);
   
   // Ταξινομούμε τα ζευγάρια, ώστε αυτά που αναφέρονται στην
   // ίδια σελίδα να είναι το ένα δίπλα στο άλλο.
   std::sort(pairs.begin(), pairs.end());
   
   std::vector<std::pair<long, int>> vec;
   // Ενώμουμε τους μετρητές που αφορούν την ίδια σελίδα.
   int prev_id = -1;
   long cur_sum = 0;
   for (auto [cur_id, cur_count] : pairs) {
      if (cur_id == prev_id) { 
         cur_sum += cur_count;
      } else {
         // Τελειώσαμε με το μέτρημα του prev_id και ξεκινάμε
         // να μετράμε για το cur_sum.
         if (prev_id != -1) {
            vec.push_back({ cur_sum, prev_id });
         }
         cur_sum = cur_count;
         prev_id = cur_id;
      }
   }
   vec.push_back({ cur_sum, prev_id });
   
   // Ταξινομούμε τα ζευγάρια κατά το count τους και τυπώνουμε
   // τα Κ μεγαλύτερα.
   std::sort(vec.begin(), vec.end(), std::greater<std::pair<long, int>>());
   
   FILE *fo = fopen("servers.out", "w");
   for (int i = 0; i < K; ++i) {
      fprintf(fo, "%d %ld\n", vec[i].second, vec[i].first);
   }
   fclose(fo);
   
   return 0;
}

Λύση με μέτρηση με πίνακα

Παρατηρώντας ότι τα ID των σελίδων είναι \(\{ 0, \ldots M-1 \}\), μπορούμε να υλοποιήσουμε την μέτρηση χρησιμοποιώντας έναν πίνακα \(\textit{count}[x]\) που κρατάει το άθροισμα των εμφανίσεων σελίδας μέχρι εκείνη τη στιγμή.

Επομένως, το πρώτο μέρος γίνεται:

   for (int i = 0; i < N; ++i) {
      for (int j = 0; j < M; ++j) {
         int x, y;
         fscanf(fi, "%d%d", &x, &y);
         count[x] += y;
      }
   }
   std::vector<std::pair<long, int>> vec;
   for (int i = 0; i < M; ++i) {
      vec.push_back({ count[i], i });
   }
   // Ταξινομούμε τα ζευγάρια κατά το count τους και τυπώνουμε
   // τα Κ μεγαλύτερα.
   std::sort(vec.begin(), vec.end(), std::greater<std::pair<long, int>>());

Με αυτόν τον τρόπο, αντικαθιστούμε την \(\mathcal{O}(NM \log(NM))\) ταξινόμηση με \(\mathcal{O}(NM)\) καταμέτρηση, που επίσης χρειάζεται \(\mathcal{O}(M)\) χώρο, αντί για \(\mathcal{O}(NM)\). Συνολικά, ο αλγόριθμος χρειάζεται \(\mathcal{O}(NM + M \log M)\) χρόνο και \(\mathcal{O}(M)\) μνήμη.

Λύση με μέτρηση με πίνακα και partial sort

Μία (μικρή) βελτίωση στην προηγούμενη λύση, είναι αντί για την πλήρη ταξινόμηση των \(M\) στοιχείων στο τελευταίο βήμα, να χρησιμοποιήσουμε την partial_sort, που ταξινομεί σε \(\mathcal{O}(M \log K)\) χρόνο. Επομένως, συνολικά, ο αλγόριθμος χρειάζεται \(\mathcal{O}(NM + M \log K)\) χρόνο.

Η μόνη διαφορά από τον κώδικα της προηγούμενης λύσης είναι η αλλαγή της

   std::sort(vec.begin(), vec.end(), std::greater<std::pair<long, int>>());

σε

   std::partial_sort(vec.begin(), vec.begin() + K, vec.end(), std::greater<std::pair<long, int>>());