38ος ΠΔΠ Α' Φάση: Δυαδικά ερωτήματα (bqueries) - Λύση

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

To \(\texttt{AND}\) δύο αριθμών (δείτε και εδώ) είναι μια δυαδική πράξη στα bits των δύο αριθμών. Για κάθε bit, αν αυτό είναι \(1\) και στους δύο αριθμούς, θα είναι \(1\) (\(1\texttt{ AND }1 = 1\)) και στο αποτέλεσμα, αλλιώς θα είναι \(0\) (\(1\texttt{ AND }0 = 0, 0\texttt{ AND }0 = 0\)).

Για παράδειγμα οι αριθμοί \(4\) και \(5\) (\(100_2\) και \(101_2\) στο δυαδικό αντίστοιχα) έχουν:

Προγραμματιστικά στη C++ το \(\texttt{ AND }\) δύο αριθμών x και y μπορεί να υπολογιστεί γράφωντας
int z = x & y.

Στην ακόλουθη λύση θα χρησιμοποιήσουμε τον συμβολισμό \(x_i\) για να αναφερθούμε στο \(i\)-οστό μικρότερο bit του αριθμού \(x\), με το \(i\) να ξεκινά από το \(0\). Π.χ. για \(x = 4\) (\(100_2\) στο δυαδικό), \(x_2 = 1, x_1 = 0, x_0 = 0\). Γενικότερα ο αριθμός \(x\) στο δυαδικό μπορεί να γραφτεί ώς \(\overline{x_{k-1} x_{k-2} \ldots x_1 x_0}\), όπου \(k\) τα ψηφία του αριθμού στην δυαδική του αναπαράσταση.

Μια παρατήρηση που μπορούμε να κάνουμε που θα χρησιμοποιήσουμε αρκετά αργότερα είναι ότι o \(y\) πρέπει να έχει τουλάχιστον τα bit που έχει ο \(x\) αναμμένα ώστε το \(\texttt{AND}\) να δώσει \(x\). Μπορεί να έχει περισσότερα, αλλά όχι λιγότερα bit αναμμένα. Άρα είναι μεγαλύτερος ή ίσος του \(x\).

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

Αν, ωστόσο, προτιμάτε να δείτε απευθείας τη γενική λύση για όλους τους βαθμούς, μπορείτε να μεταβείτε εδώ.

Λύση για το 1ο υποπρόβλημα

Στο πρώτο υποπρόβλημα (\(R \leq 5.000\)), το εύρος τιμών είναι αρκετά μικρό για να δοκιμάσουμε όλα τα ζεύγη και να δούμε πόσα ικανοποιούν την συνθήκη μας.

  ll count = 0;
  for (ll x = L; x <= R; x++) {
    for (ll y = x; y <= R; y++) {
      // Ελέγχουμε αν το ζεύγος (x, y) είναι έγκυρο
      if ((x & y) == x) {
        count++;
      }
    }
  }

Ολόκληρος ο κώδικας εδώ.

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

typedef long long ll;

και να χρησιμοποιούμε το ll σαν τύπο, π.χ. ll x, y;.

Λύση για το 2ο υποπρόβλημα

Σε αυτό το υποπρόβλημα εξακολουθούμε να έχουμε ένα άνω όριο στο \(R\), παρ’ όλα αυτά δεν είναι αρκετό για να δοκιμάσουμε όλα τα ζεύγη επομένως θα χρειαστούμε μια γρηγορότερη λύση.

Ας λύσουμε το πιο απλό πρόβλημα, όπου γνωρίζουμε το \(x\) και ψάχνουμε να βρούμε πόσες τιμές \(y\), \(x \leq y \leq R\), επαληθεύουν τη ζητούμενη σχέση.

Παρατήρηση:

• Αν \(x \texttt{ AND } y = x\), τότε για κάθε bit \(x_i \texttt{ AND } y_i = x_i\), με \(0 \leq i < k\), όπου \(k\) ο αριθμός των bits του \(y\).
• Αν \(x_i = 0\), τότε \(0 \texttt{ AND } y_i = 0\), που ισχύει ανεξαρτήτως του \(y_i\). Όμως αν \(x_i = 1\), τότε \(1 \texttt{ AND } y_i = 1 \Rightarrow y_i = 1\).
• Ομοίως, αν \(y_i = 0\), τότε \(x_i \texttt{ AND } 0 = x_i \Rightarrow 0 = x_i\).

Άρα έχουμε τους περιορισμούς

1. \(x_i = 1 \Rightarrow y_i = 1\),
2. \(y_i = 0 \Rightarrow x_i = 0\),

Ας πάρουμε για παράδειγμα \(x = 26\) (\(11010_2\)) και \(R = 87\) (\(1010111_2\)) τότε ποιες είναι οι δυνατές τιμές του \(y\); Χρησιμοποιώντας την παραπάνω παρατήρηση (και προσθέτωντας μηδενικά για να έχουμε το ίδιο μήκος με το \(R\)):

με τα ερωτηματικά ? να μπορούν να είναι είτε \(0\) είτε \(1\) για να ικανοποιήσουν την σχέση. Ουσιαστικά απλά αντικαταστήσαμε τα \(0\) bits του \(x\) με ?. Αν δεν είχαμε το όριο \(R\) και έπρεπε να μετρήσουμε όλες τα πιθανά \(y\) αυτής της μορφής με \(7\) bits, αφού έχουμε \(4\) ερωτηματικά και το κάθε ένα έχει \(2\) επιλογές, θα είχαμε συνολικά \(2 \times 2 \times 2 \times 2 = 2^4 = 16\) πιθανούς συνδυασμούς (Μεταθέσεις με επανάληψη). Οπότε μπορούμε να βρούμε πόσοι συνδυασμοί είναι μεγαλύτεροι από το \(R\) και να τους αφαιρέσουμε.

Για να είναι \(y > R\), πρέπει το πρώτο bit που διαφέρει στους δύο αριθμούς να είναι μεγαλύτερο στο \(y\), δηλαδή \(y_j > R_j\) και \(y_i = R_i\), για κάθε \(i\), όπου \(i > j\). Επειδή είμαστε στο δυαδικό σύστημα και τα ψηφία μπορούν να πάρουν μόνο δύο τιμές, πιο συγκεκριμένα έχουμε \(y_j = 1, R_j = 0\). Παίρνουμε μία μία τις πιθανές θέσεις που διαφέρουν, δηλαδή τις τιμές του \(j\) και ελέγχουμε πόσοι συνδυασμοί αντιστοιχούν σε αυτή.

Ας δούμε το παραπάνω παράδειγμα αναλυτικά και μέσα από αυτό να δούμε τις διαφορετικές περιπτώσεις των \(y_j, R_j\) που μπορούμε να συναντήσουμε:

Θέση 1η

Έχουμε \(R_6 = 1\). Άν \(y_6 = 0\) τότε \(y < R\) ανεξάρτητα από τις τιμές των ? στα μικρότερα bits, οπότε δεν μας κάνει. Οπότε θέτουμε \(y_6 = 1\) και συνεχίζουμε.

Θέση 2η

Έχουμε \(R_5 = 0\) οπότε αν \(y_5 = 1\), το \(y\) θα είναι πάντα μεγαλύτερο. Τα \(2\) εναπομείναντα ? μπορούν να πάρουν οποιαδήποτε τιμή άρα συνολικά έχουμε \(2^2 = 4\) συνδυασμούς. Έπειτα, θέτουμε \(y_5 = 0\) και συνεχίζουμε.

Θέση 3η

Έχουμε \(R_4 = y_4 = 1\) οπότε απλά συνεχίζουμε.

Θέση 4η

Έχουμε \(R_3 = 0\) και \(y_3 = 1\), άρα το \(y\) είναι πάντα μεγαλύτερο, και από τα \(2\) ερωτηματικά ? που μένουν, παίρνουμε άλλους \(2^2 = 4\) συνδυασμούς. Επίσης, το μέτρημα σταματάει εδώ, αφού το συγκεκριμένο \(y_3\) δεν είναι ? και άρα δεν μπορούμε να έχουμε το πρώτο διαφορετικό bit σε μετέπειτα θέση.

Άρα συνολικά οι αριθμοί \(y > R\) είναι \(4 + 4 = 8\). Άρα οι αριθμοί \(y \leq R\) είναι \(2^4 - 8 = 16 - 8 = 8\).

Άρα μπορούμε με μία επανάληψη για όλα τα bits να μετρήσουμε το πλήθος των \(y\) για ένα συγκερκιμένο \(x\). Θυμίζουμε ότι τα ερωτηματικά ? που χρησιμοποιήσαμε για διευκόλυνση αντιστοιχούν στα \(0\) του \(x\).

Άρα για κάθε θέση \(i\) ξεκινώντας από τη μεγαλύτερη:

1. Αν \(R_i = 1\), συνεχίζουμε στην επόμενη θέση
2. Αν \(R_i = 0\), αυξάνουμε το πλήθος κατά \(2^m\), όπου \(m\) τα μηδενικά στα μικρότερα bits (δεξιά) του \(x\). Συνεχίζουμε μόνο αν \(x_i = 0\) αλλιώς σταματάμε.

Για κάθε \(x\) η πολυπλοκότητα είναι \(\mathcal{O}(\log R)\), όσο και ο αριθμός των bits. Συνολικά έχουμε το πολύ \(R\) πιθανά \(x\) να ελέγξουμε για κάθε ερώτημα άρα η συνολική πολυπλοκότητα είναι \(\mathcal{O}(Q R \log R)\).

Ολόκληρος ο κώδικας εδώ.

Λύση για το 3ο υποπρόβλημα

Για τα υποπροβλήματα από εδώ και πέρα πρέπει να βρούμε ένα γρήγορο τρόπο να μετράμε των αριθμό των ζευγών χωρίς να ελέγχουμε μία-μία όλες τις πιθανές τιμές του \(x\) ή του \(y\).

Πριν προχωρήσουμε στο διάστημα \([L, R] = [2^k, 2^m - 1]\), \(k, m\) θετικοί ακέραιοι του προβλήματος ας ασχοληθούμε λίγο με ένα πιο απλό διάστημα, το \([0, 2^m - 1]\), \(m\) θετικός ακέραιος. Πιο απλά, το διάστημα όλων των αριθμών με έως \(m\) bits. Συμπληρώνοντας \(0\) μπροστά στους αριθμούς με λιγότερα από \(m\) bits, μπορούμε να τους θεωρήσουμε όλους ότι έχουν \(m\) bits.

Σε αυτή την περίπτωση δεν έχουμε κάποιο περιορισμό πέρα από το πλήθος των bits. Οι επιτρεπτοί συνδυασμοί \((x_i, y_i)\) που ικανοποιούν \(x_i \texttt{ AND } y_i = x_i\) είναι \(3\), \((0, 0), (0, 1), (1, 1)\). Ο συνδυασμός \((1, 0)\) δεν την ικανοποιεί. Άρα για κάθε ένα από τα \(m\) bits των \(x, y\) έχουμε \(3\) επιλογές, χωρίς περαιτέρω περιορισμούς, άρα συνολικά έχουμε \(3^m\) συνδυασμούς \(x, y\).

Ας επιστρέψουμε στο διάστημα \([L, R] = [2^k, 2^m - 1]\). Τα ζεύγη \(x, y\) που ανήκουν σε αυτό είναι όλα τα ζεύγη με \(m\) bits (όπως στο \([0, 2^m - 1]\)), εκτός από εκείνα στα οποία \(x < L = 2^k\), η πιο απλά τα \(x\) με έως \(k\) bits. Η γενική μορφή αυτών των \(x, y\) είναι:

Η γραμμή | χωρίζει τους αριθμούς στα πρώτα \(m-k\) bits και στα τελευταία \(k\) bits. Όπως είπαμε και πριν για κάθε bit μετά τη γραμμή έχουμε \(3\) επιλογές, ενώ για τα πρώτα \(m-k\) έχουμε μόνο \(2\) (αφού \((x_i,y_i) = (0, 0)\) ή \((x_i, y_i) = (0, 1)\)). Άρα το πλήθος των αριθμών που δεν ανήκουν στο ζητούμενο διάστημα είναι \(2^{m-k}3^k\), και άρα τα ζεύγη που ανήκουν είναι \(3^m - 2^{m-k}3^k\).

Για να βρούμε τα \(m, k\) αρκεί μια γραμμική αναζήτηση στα bits των \(L, R\), δηλαδή \(\mathcal{O}(\log R)\) (ή πιο απλά τις συναρτήσεις std::popcount και std::countr_zero της C++ από τη C++20 και μετά αν το επιτρέπει ο μεταγλωτιστής του διαγωνισμού) και ο υπολογισμός των δυνάμεων του \(2\) και του \(3\), που αν τα προϋπολογίσουμε στην αρχή του προγράμματος, έπειτα θα είναι \(\mathcal{O}(1)\). Άρα συνολική πολυπλοκότητα είναι \(\mathcal{O}(Q\log R)\).

int find_bit_count(ll x) {
  int count = 0;
  while (x) {
    count++;
    x >>= 1;
  }
  return count;
}

ll calculate_bquery(ll L, ll R) {
  // Λύση για το υποπρόβλημα με L = 2^k, R = 2^m - 1
  // Υπολογίζουμε τα k, m και επιστρέφουμε 3^m−2^(m−k)3^k

  int m = find_bit_count(R);
  int k = find_bit_count(L) - 1;

  return pow3[m] - pow2[m - k] * pow3[k];
}

Ολόκληρος ο κώδικας εδώ.

Λύση για το 4ο υποπρόβλημα

Σε αυτό το υποπρόβλημα, \(L = 0\), που σημαίνει ότι μόνο το επάνω όριο έχει σημασία. Αρκεί να εστιάσουμε στην ανισότητα \(y \leq R\), αφού ξέρουμε ήδη ότι για τα αποδεκτά ζεύγη \(x, y\) ισχύει \(x \leq y\). Έστω \(k\) το πλήθος των bits του \(R\), και \(R'\) ο αριθμός \(R\) μετά την αφαίρεση του μεγαλύτερου ((\(k-1\))-οστού) bit του. Ας προσπαθήσουμε να προσεγγίσουμε το πρόβλημα αναδρομικά. Κοιτώντας το μεγαλύτερο bit του \(R\).

Υπάρχουν \(2\) περιπτώσεις:

• \(R_{k-1} = 0\): Τότε αναγκαστικά \(y_{k+1}=0\) και \(x_{k+1}=0\) άρα μπορούμε να αγνοήσουμε αυτό το bit και η απάντηση είναι ίδια με το διάστημα \([0, R']\).
• \(R_{k-1} = 1\): Τότε έχουμε τις \(2\) επιλογές:
  • \(y_{k-1} = 0\): Θα ισχύει πάντα \(y<R\) και άρα αφού τα υπόλοιπα \(k-1\) bits δεν έχουν κανένα περιορισμό, έχουμε \(3^{k-1}\) ζεύγη.
  • \(y_{k-1} = 1\): Το \(x_{k-1}\) μπορεί να πάρει \(2\) τιμές (\(0, 1\)) και τα υπόλοιπα \(k-1\) bits μπορούν να πάρουν τις τιμές του διαστήματος \([0, R']\).

Αν ορίσουμε \(G_i\), την απάντηση με τα τελευταία (μικρότερα) \(i\) bits του \(R\), τότε το παραπάνω μπορούμε να το γράψουμε ως:

• \(R_{i} = 0\): \(G_i = G_{i-1}\)
• \(R_{i} = 1\): \(G_i = 3^{i-1} + 2 G_{i-1}\)

Η τελική απάντηση είναι το \(G_k\). Η πολυπλοκότητα της λύσης είναι ένα πέρασμα από τα bits του \(R\) άρα συνολικά έχουμε \(\mathcal{O}(Q\log R)\).

ll calculate_bquery(ll L, ll R) {
  // Λύση για το υποπρόβλημα με L = 0
  // Υπολογίζουμε αναδρομικά την απάντηση για τα τελευταία i bits του R

  ll count = 1;

  long i = 0;
  for (ll bit = 1; bit <= R; bit <<= 1) {
    ++i;
    if ((R & bit) == 0)
      continue;
    count = 2 * count + pow3[i - 1];
  }

  return count;

Ολόκληρος ο κώδικας εδώ.

Τελική λύση

Ας πάρουμε τις περιπτώσεις για το μεγαλύτερο bit των δύο αριθμών \(L, R\) (αν το \(L\) έχει μικρότερο πλήθος bits, προσθέτουμε \(0\) ώστε να τα θεωρούμε στο ίδιο μήκος). Έστω \(k\) το πλήθος των bits τους και \(L', R'\) οι αριθμοί \(L, R\) μετά την αφαίρεση του μεγαλύτερου ((\(k-1\))-οστού) bit τους.

• \(L_{k-1} = 1, R_{k-1} = 0\): Σε αυτή την περίπτωση \(L > R\), άρα δεν υπάρχουν ζεύγη που να ικανοποιούν την συνθήκη, οπότε σταματάμε.
• \(L_{k-1} = 0, R_{k-1} = 0\): Αν τα πρώτα bits είναι ίσα αυτό σημαίνει ότι και \(x_{k-1} = y_{k-1} = 0\), για να είναι τα \(x, y\) ανάμεσα στα \(L\) και \(R\). Άρα μπορούμε να αφαιρέσουμε το πρώτο bit από τα \(L\) και \(R\) και αναδρομικά να βρούμε πόσα \(x, y\) είναι στο διάστημα \([L', R']\).
• \(L_{k-1} = 1, R_{k-1} = 1\): Ομοίως, \(x_{k-1} = y_{k-1} = 1\), και λύνουμε αναδρομικά στα υπόλοιπα \(k-1\) bits.
• \(L_{k-1} = 0, R_{k-1} = 1\): Σε αυτή την περίπτωση τα \(x_{k-1}, y_{k-1}\) μπορούν να πάρουν με τη σειρά τους \(3\) διαφορετικά ζεύγη τιμών \((0, 0), (0, 1), (1, 1)\):
  • \((x_{k-1}, y_{k-1}) = (1, 1)\): Σε αυτή την περίπτωση ικανοποιείται πάντα η συνθήκη \(L < x\), οπότε μας ενδιαφέρει μόνο η \(y < R\). Αφαιρόντας το πρώτο bit, αυτό ισοδυναμεί με πόσα ζεύγη \(x, y\) υπάρχουν από \(0\) έως \(R'\), το οποίο το απαντήσαμε στο 4ο υποπρόβλημα.
  • \((x_{k-1}, y_{k-1}) = (0, 0)\): Σε αυτή την περίπτωση έχουμε πάντα \(y < R\), και άρα μας ενδιαφέρει μόνο η \(L < x\). Αφαιρώντας το πρώτο bit, έχουμε το διάστημα από \(L'\) έως \(2^{k-1} - 1\). Με παρόμοια λογική με το 4ο υποπρόβλημα μπορούμε γρήγορα να μετρήσουμε όλα αυτά τα ζεύγη (η αντίστοιχη αναδρομική σχέση που προκύπτει είναι \(H_i = H_{i-1}\) αν \(L_i=1\) και \(H_i = 3^i + 2 H_{i-1}\), αν \(L_i=0\)).
  • \((x_{k-1}, y_{k-1}) = (0, 1)\): Η απάντηση για αυτή την περίπτωση είναι ίση με την απάντηση στο έυρος \([L', R']\), που θα το εξετάσουμε αναδρομικά.

  Άρα συνολικά έχουμε να μετρήσουμε τα \(3\) διαστήματα, \([0, R'], [L', 2^{k-1} - 1], [L', R']\).

Ας ορίσουμε \(G_i\) την απάντηση μόνο με άνω όριο τα τελευταία \(i\) bits του \(R\), \(H_i\) την απάντηση μόνο με κάτω όριο τα τελευταία \(i\) bits του \(L\) (και συνολικά \(i\) bits), και \(F_i\) την απάντηση με άνω όριο τα τελευταία \(i\) bits του \(R\) και κάτω όριο τα τελευταία \(i\) bits του \(L\).

Συνοπτικά τα παραπάνω γράφονται ώς:

• \(L_{i} = 1, R_{i} = 0\): \(F_i = 0\)
• \(L_{i} = 0, R_{i} = 0\): \(F_i = F_{i-1}\)
• \(L_{i} = 1, R_{i} = 1\): \(F_i = F_{i-1}\)
• \(L_{i} = 0, R_{i} = 1\): \(F_i = F_{i-1} + G_{i-1} + L_{i-1}\)

Τελική απάντηση είναι η \(F_k\) όπου \(k\) τα συνολικά bits του \(R\). Η πολυπλοκότητα είναι \(\mathcal{O}(\log R)\) για τον υπολογισμό των \(G_i, H_i\) για κάθε \(i\), και \(\mathcal{O}(\log R)\) για τον υπολογισμό του \(F_i\), για κάθε \(i\). Οπότε συνολικά έχουμε \(\mathcal{O}(Q\log R)\).

ll calculate_bquery(ll L, ll R) {
  ll total = 1;        // Συνολικός αριθμός ζευγών
  ll upperBounded = 1; // Αριθμός ζευγών με άνω όριο
  ll lowerBounded = 1; // Αριθμός ζευγών με κάτω όριο
  ll digits = 0;
  // Για κάθε bit μικρότερο ή ίσο του R
  for (ll bit = 1; bit <= R; bit <<= 1) {
    digits++;
    ll rBit = R & bit;
    ll lBit = L & bit;
    if (rBit == 0 && lBit == bit) {
      // Αν το bit είναι 0 στο R και 1 στο L, τα ζεύγη στα μικρότερα bits δεν
      // είναι πλέον έγκυρα
      total = 0;
    } else if (rBit == bit && lBit == 0) {
      // Αν το bit είναι 1 στο R και 0 στο L, τοτε προσθέτουμε και όλα τα
      // ζεύγη που σχηματίζονται από τα bounds
      total += upperBounded + lowerBounded;
    }

    if (rBit == bit) {
      upperBounded = pow3[digits - 1] + 2 * upperBounded;
    }
    if (lBit == 0) {
      lowerBounded = pow3[digits - 1] + 2 * lowerBounded;
    }
  }

  return total;
}

Ολόκληρος ο κώδικας εδώ.