38ος ΠΔΠ : Σύστημα επικοινωνίας (commsystem) - Λύση

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

Μας δίνονται κάποιες πυραμίδες δηλαδή ακολουθίες θετικών ακεραίων \(1 \leq p_i \leq 12\) που είναι αύξουσες στην αρχή και μετά φθίνουσες και μας ζητείται να γράψουμε μία μέθοδο για την κωδικοποίηση τους σε δυαδικές συμβολοσειρές καθώς και για την αποκωδικοποίησή τους. Σκοπός είναι οι δυαδικές συμβολοσειρές να χρησιμοποιούν το πολύ \(22\) χαρακτήρες, αλλά χρειάζεται προσοχή ώστε οι δύο μέθοδοι να είναι αποδοτικοί (από άποψη χώρου και χρόνου – το όριο είναι 16MB).

Για να δουλεύει πάντοτε η κωδικοποίηση δεν θα πρέπει να υπάρχουν δύο πυραμίδες που να αντιστοιχούνται στην ίδια δυαδική συμβολοσειρά (δηλαδή η συνάρτηση κωδικοποίησης πρέπει να είναι ένα προς ένα).

Βέλτιση λύση

Η ιδέα για την βέλτιστη λύση είναι να δημιουργήσουμε όλες τις έγκυρες πυραμμίδες και να τις αντιστοιχήσουμε σε έναν μοναδικό αριθμό. Για την κωδικοποίηση, χρειαζόμαστε τον πίνακα αντιστοίχησης και για την αποκωδικοποίηση χρειαζόμαστε τον αντίστροφό του.

Για να το κάνουμε αυτό αποδοτικά (και να χωρέσει στα όρια της μνήμης) θα πρέπει να φτιάξουμε μία απλή κωδικοποίηση για τις πυραμίδες (δείτε παρακάτω). Ο κώδικας για την δημιουργία όλων των έγκυρων πυραμίδων είναι ο εξής:

std::vector<std::pair<uint64_t,int>> forwards; // Ταξινομημένος πίνακας.
std::vector<uint64_t> backwards; // Ανίστροφος πίνακας.

int counter = 0;

// Δημιουργούμε όλες τις δυνατές ακολουθίες που ικανοποιούν την ιδιότητα της
// πυραμίδας και τις αντιστούμε σε έναν αριθμό.
void explore(std::vector<int>& cur_seq, bool is_increasing, bool is_forwards) {
  if (!cur_seq.empty()) {
    auto encoding = simple_encode(cur_seq);
    if (is_forwards) forwards.push_back({encoding, counter});
    else backwards.push_back(encoding);
    ++counter;
  }
  
  int prev = cur_seq.empty() ? 0 : cur_seq.back();
  cur_seq.push_back(-1);
  // Προσθέτουμε ένα μικρότερο στοιχείο.
  for (int nxt = 1; nxt < prev; ++nxt) {
    cur_seq.back() = nxt;
    explore(cur_seq, false, is_forwards);
  }
  // Προσθέτουμε ένα μεγαλύτερο στοιχείο.
  if (is_increasing) {
    for (int nxt = prev + 1; nxt <= 12; ++nxt) {
      cur_seq.back() = nxt;
      explore(cur_seq, true, is_forwards);
    } 
  }
  cur_seq.pop_back();
}

Η κωδικοποίηση γίνεται με την εξής υλοποίηση

      std::pair<uint64_t, int> key{simple_encode(seq), 0 };
      auto it = std::lower_bound(forwards.begin(), forwards.end(), key);
      print_binary_seq(it->second);

και η αποκωδικοποίηση

      print_seq(simple_decode(backwards[val]));

Για την κωδικοποίηση χρησιμοποιούμε ταξινομημένο πίνακα και δυαδική αναζήτηση, καθότι χρησιμοποιεί λιγότερη μνήμη και είναι (στην συγκεκριμένη περίπτωση) πιο γρήγορο από το std::map και std::unordered_map.

Ακολουθούν οι λεπτομέρειες για την απλή κωδικοποίηση και μία μικρή βελτιστοποίηση για να μικρύνουν οι κώδικες από \(23\) σε \(22\) bit. Ολόκληρος ο κώδικας βρίσκεται εδώ.

Μία απλή κωδικοποίηση

Θα χρησιμοποιήσουμε τον εξής τρόπο για να κωδικοποιήσουμε μία πυραμίδα:

Χωρίζουμε στο αύξον και στο φθίνον μέρος.
π.χ. [2, 6, 9, 10, 7, 3] -> [2, 6, 9, 10] [10, 7, 3]
Υπολογίζουμε την ακολουθία των διαφορών
π.χ.
[2, 6, 9, 10] -> [4, 3, 1]
[10, 7, 3] -> [3, 4]
Κωδικοποιούμε την κάθε διαφορά \(d\) ως εξής
\(\qquad {\texttt{1}\underbrace{\texttt{00}\ldots \texttt{00}}_d}\)
και ενώνουμε τις διαφορές σε έναν ακέραιο
π.χ.
[4, 3, 1] -> 0b10000100010
[3, 4] -> 0b100010000
Τέλος ενώνουμε τις δύο ακολουθίες σε έναν ακέραιο.

Κάθε ένα από τα δύο μέρη μπορεί να έχει το πολύ \(12\) μηδενικά και το πολύ \(12\) άσους. άρα ενώνοντας τα δύο μέρη χωράνε σε ένα uint64_t.

Παρακάτω δίνεται η υλοποίηση για την κωδικοποίηση:

// Κωδικοποιεί τις διαφορές μεταξύ διαδοχικών στοιχείων στην δοσμένη
// ακολουθία σε έναν ακέραιο 64-bit. 
// Παράδειγμα:
//   simple_encode({2, 6, 9, 10, 7, 3})
//   left = {2, 6, 9, 10}  right = {10, 7, 3}
//          {4, 3, 1}              {3, 4}
//          10000100010            100010000
//   ans = 00..0010000100010|00..00100010000
uint64_t simple_encode(const std::vector<int>& seq) {
  uint32_t left = 1;
  int prev = 0;
  int seq_idx = 0;
  for (;seq_idx < seq.size(); ++seq_idx) {
    int v = seq[seq_idx];
    if (v < prev) break;
    append(left, v - prev);
    prev = v;
  }
  uint32_t right = 1;
  for (;seq_idx < seq.size(); ++seq_idx) {
    int v = seq[seq_idx];
    append(right, prev - v);
    prev = v;
  }
  return (uint64_t(left) << 32) | right;
}

Παρακάτω δίνεται ο κώδικας για την αποκωδικοποίηση:

// Παράδειγμα:
//   simple_decode_half(10000100010) = {4, 3, 1}
std::vector<int> simple_decode_half(uint32_t seq) {
  std::vector<int> ans;
  while (seq != 0) {
    int val = 0;
    while (seq % 2 != 1) {
      ++val;
      seq /= 2;
    }
    seq /= 2;
    ans.push_back(val);
  }
  ans.pop_back();
  std::reverse(ans.begin(), ans.end());
  return ans;
}

// Παράδειγμα:
//   ans = 00..0010000100010|00..00100010000
//          10000100010            100010000
//          {4, 3, 1}              {3, 4}
//          {4, 3, 1, -3, -4}
//   ans =  {2, 6, 9, 10, 7, 3}
std::vector<int> simple_decode(uint64_t encoding) {
  auto inc = simple_decode_half(encoding >> 32);
  auto dec = simple_decode_half(encoding & 0xFFFFFFFFULL);
  std::vector<int> ans;
  int prev = 0;
  for (auto delta : inc) {
    prev += delta;
    ans.push_back(prev);
  }
  for (auto delta : dec) {
    prev -= delta;
    ans.push_back(prev);
  }
  return ans;
}

Μία ακόμα βελτιστοποίηση

Υπάρχουν περίπου \(5.5 \cdot 10^6\) πυραμίδες και κανονικά θα χρειαζόμασταν περίπου \(\log_2 (5.5 \cdot 10^6) \approx 22.39\) δηλαδή \(23\) bit. Για να τα χωρέσουμε σε 22 παρατηρούμε ότι στην έξοδο οι αριθμοί \(000110\) και \(110\) είναι διαφορετικές ακολουθίες. Επομένως, μπορούμε να αντιστοιχήσουμε τους αιρθμούς \(x\) που είναι μεγαλύτεροι από \(2^{22}\) στους αριθμούς \(x - 2^{22}\).

// Τυπώνουμε τον αριθμό:
// Αν cnt >  2^22 τότε βάζουμε κάποια μηδενικά στην αρχή.
// Αν cnt <= 2^22 τότε τυπώνουμε χωρίς μηδενικά.
void print_binary_seq(int cnt) {
  bool fill_with_zeros = false;
  if (cnt >= (1 << 22)) {
    fill_with_zeros = true;
    cnt -= (1 << 22);
  }
  int num_bits = 0;
  while (cnt) {
    if (cnt & 1) printf("1");
    else printf("0");
    cnt >>= 1;
    ++num_bits;
  }
  // Γεμίζουμε τον αριθμό με μηδενικά.
  if (fill_with_zeros) {
    while (num_bits < 22) {
      printf("0");
      ++num_bits;
    }
  } 
  printf("\n");
}

Η ανάγνωση μίας συμβολοσειράς γίνεται ως εξής:

      std::fgets(str, 100, stdin);
      int i = 0;
      int val = 0;
      for (; str[i] != '\n'; ++i) {
        if (str[i] == '1') val |= 1 << i;
      }
      if (i == 22 && val < (1 << 21) ) val |= (1 << 22); 
      print_seq(simple_decode(backwards[val]));