27ος ΠΔΠ Γ' Φάση: Παρέες αριθμών (aces) - Λύση

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

Μας δίνονται κάποιοι ακέραιοι (μικρότεροι από \(2^{30}\)), τους χωρίζουμε σε ομάδες ανάλογα με τον αριθμό των άσων στην δυαδική τους αναπαράσταση και μας ζητείται να βρούμε το πλήθος των αριθμών στην μεγαλύτερη ομάδα.

Γενική λύση

Το πρόβλημα αυτό έχει δύο μέρη:

1. Μετράμε τους άσους στη δυαδική αναπαράσταση του \(x\).
2. Κρατάμε πόσες φορές έχουμε δει ένα συγκεκριμένο πλήθος άσων.

Αφού το πλήθος των άσων είναι μεταξύ \(0\) και \(30\), αρκεί να κρατήσουμε έναν πίνακα cnt[i] όπου μετράμε το πλήθος των αριθμών με i άσους στην δυαδική τους αναπαράσταση. Επομένως για κάθε ακέραιο A[k] κάνουμε ++cnt[count_bits(A[k])].

long cnt[32];

int main() {
   FILE *fi = fopen("aces.in", "r");
   
   long n;
   fscanf(fi, "%ld", &n);
   for (long i = 0; i < n; ++i) {
      long tmp;
      fscanf(fi, "%ld", &tmp);
      ++cnt[count_bits(tmp)];
   }
   
   int max_count = 0;
   for (int i = 0; i < 32; ++i) {
      if (max_count < cnt[i]) max_count = cnt[i];
   }
   fclose(fi);
   
   FILE *fo = fopen("aces.out", "w");
   fprintf(fo, "%ld\n", max_count);
   fclose(fo);
   
   return 0;
}

Τώρα θα δούμε μερικούς τρόπους για να υλοποιήσουμε την count_bits(x) για την μέτρηση των άσων στην διαδική αναπαράσταση του ακεραίου \(x\).

Μέθοδος 1η: Βρίσκουμε το κάθε ψηφίο στην δυαδική αναπαράσταση του αριθμού και αθροίζουμε τους άσους. Ας πάρουμε για παράδειγμα τον αριθμό \(25_{10} = 11001_{(2)}\).

• Μπορούμε να βρούμε το δεξιότερο ψηφίο κοιτώντας αν ο αριθμός είναι μονός ή ζυγός. Σε αυτή την περίπτωση είναι μονός άρα το τελευταίο ψηφίο είναι \(1\).

• Για να βρούμε το επόμενο ψηφίο διαιρούμε δια δύο, τότε ο αριθμός γίνεται \(x_1 = 12 = 1100_{(2)}\) (είναι σαν να αφαιρέσαμε το δεξιότερο ψηφίο).

  Μετά βλέπουμε ότι ο αριθμός είναι ζυγός, άρα το επόμενο ψηφίο είναι \(0\).

• Συνεχίζουμε με τον ίδιο τρόπο, \(x_2 = 6 = 110_{(2)}\) και το επόμενο ψηφίο είναι \(0\).
• Συνεχίζουμε με τον ίδιο τρόπο, \(x_3 = 3 = 11_{(2)}\) και το επόμενο ψηφίο είναι \(1\).
• Συνεχίζουμε με τον ίδιο τρόπο, \(x_4 = 1_{(2)}\) και το επόμενο ψηφίο είναι \(1\).
• Ο αριθμός είναι μηδέν, άρα όλα τα υπόλοιπα ψηφία είναι \(0\).

Αυτό που μπορούμε να το υλοποιήσουμε ως εξής (και όποτε βρίσκουμε άσο αυξάνουμε έναν μετρητή):

int count_bits(long x) {
   int total = 0;
   while (x > 0) {
      total += x % 2;
      x /= 2;
   }
   return total;
}

Αφού κάθε φορά διαιρούμε δια δύο, κάθε υπολογισμός θέλει χρόνο \(\mathcal{O}(\log_2(x))\), επομένως ο αλγόριθμος θέλει \(\mathcal{O}(n \log(\mathrm{MAX}))\) χρόνο και \(\mathcal{O}(1)\) μνήμη.

Ολόκληρος ο κώδικας βρίσκεται εδώ.

Μέθοδος 2η: Μπορούμε να αντικαταστήσουμε τα / 2 και το %2 με τα bitwise operations & 1 και << 1, ώστε ο κώδικας να γίνει λίγο πιο αποδοτικός (συνήθως ο compiler κάνει αυτή την αντικατάσταση).

int count_bits(long x) {
   int total = 0;
   while (x > 0) {
      total += x & 1;
      x >>= 1;
   }
   return total;
}

Ολόκληρος ο κώδικας βρίσκεται εδώ.

Μέθοδος 3η: Η C++ έχει κάποιες συναρτήσεις που χρησιμοποιούν low-level εντολές για την μέτρηση των ψηφίων. Για ακεραίους \(32\) και \(64\)-bit στους περισσότερους υπολογιστές αυτές αντιστοιχούν σε μία εντολή assembly (μπορείτε να διαβάσετε εδώ για την εντολή POPCNT σε επεξεργαστές Intel). Η συνάρτηση bitset::count() καλεί αυτές τις εντολές αν υπάρχουν στο σύστημα.

int count_bits(long x) {
   return std::bitset<32>(x).count();
}

Ολόκληρος ο κώδικας βρίσκεται εδώ.

Μέθοδος 4η: Μπορούμε να προϋπολογίσουμε τα counts για μικρούς αριθμούς πχ για όλα τα bytes (ακέραιοι \(0\) έως \(2^8 - 1\)) στον πίνακα byte_count. Μετά για κάθε \(32\)-bit ακέραιο τον σπάμε σε \(4\) bytes βρίσκουμε το πλήθος σε κάθε ένα από αυτά με τον πίνακα byte_count και τα αθροίζουμε:

int count_bits_slow(long x) {
   int total = 0;
   while (x > 0) {
      total += x & 1;
      x >>= 1;
   }
   return total;
}

int byte_count[256];

void precompute() {
   for (int i = 0; i < 256; ++i) {
      byte_count[i] = count_bits_slow(i);
   }
}

int count_bits(long x) {
   // Το x & 0xFF επιστρέφει το χαμηλότερο byte από τον x. 
   // Τα x >> 8, x >> 16, x >> 24, μετακινούν τον αριθμό
   // ώστε το 2ο, 3ο και 4ο byte να είναι μεταξύ 0..255.
   return byte_count[x & 0xFF] + byte_count[(x >> 8) & 0xFF] 
      + byte_count[(x >> 16) & 0xFF] + byte_count[(x >> 24) & 0xFF];
}

Ολόκληρος ο κώδικας βρίσκεται εδώ.

Σημείωση: Θα μπορούσαμε να είχαμε προϋπολογίσει έως το \(2^{16} - 1\), με τον precompute χρόνο και τη μνήμη να είναι μεγαλύτερος, αλλά για την count_bits ο χρόνος να είναι μικρότερος.

Μερικές ακόμα μεθόδους μπορείτε να βρείτε εδώ.