38ος ΠΔΠ : Παιχνίδι συγχώνευσης 2 (mergegame2) - Λύση

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

Μας δίνεται ένα σύνολο από \(N\) ακεραίους αριθμούς και σε κάθε βήμα διαλέγουμε δύο από αυτούς \(A_i, A_j\) που είναι και οι δύο περιττοί ή και οι δύο ζυγοί. Έπειτα τους αντικαθιστούμε

• με \(A_i + A_j + 7\) αν είναι και οι δύο περιττοί, ή
• με \(A_i + A_j + 8\) αν και οι δύο είναι ζυγοί.

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

Βέλτιστη λύση

Ξεκινάμε με την εξής βασική παρατήρηση:

Παρατήρηση 1η: Οι περιττοί αριθμοί αντικαθίστανται με περιττό αριθμό και οι ζυγοί με ζυγό.

(Αιτιολόγηση) Αυτό προκύπτει επειδή το άθροισμα δύο περιττών είναι ζυγός (άρα το \(A_i + A_j + 7\) είναι περιττός) και το άθροισμα δύο ζυγών είναι ζυγός (άρα το \(A_i + A_j + 8\) είναι ζυγός).

Χρησιμοποιώντας την παραπάνω παρατήρηση οδηγούμαστε στο συμπέρασμα ότι δεν μπορούμε να αφαιρέσουμε όλους τους περιττούς ή όλους τους ζυγούς, άρα:

Παρατήρηση 2η: Αν το αρχικό σύνολο έχει περιττούς και ζυγούς αριθμούς, τότε δεν είναι εφικτό να καταλήξουμε σε ένα στοιχείο.

Άρα τώρα, μπορούμε να θεωρήσουμε ότι το σύνολο έχει είτε μόνο περιττούς είτε μόνο ζυγούς αριθμούς, και βλέπουμε ότι η σταθερά \(7\) ή \(8\) δεν κάνει διαφορά στο ποια στοιχεία διαλέγουμε σε κάθε βήμα. Το πρόβλημα λύνεται άπληστα σε κάθε βήματα διαλέγοντας τα δύο μικρότερα στοιχεία.¹ Για να το κάνουμε αυτό αποδοτικά κρατάμε τα στοιχεία σε μία ουρά προτεραιότητας (ή ένα set) και κάθε φορά αφαιρούμε τα δύο μικρότερα στοιχεία.

  ll additive_factor = found_even ? 8 : 7;
  ll cost = 0;
  while (pq.size() != 1) {
    // Διαλέγουμε τα δύο μικρότερα στοιχεία.
    ll one = pq.top(); pq.pop();
    ll two = pq.top(); pq.pop();
    // Προσθέτουμε το κόστος για το βήμα.
    ll new_item = one + two + additive_factor;
    cost += new_item;
    // Αντικαθιστούμε το καινούργιο στοιχείο.
    pq.push(new_item);
  }

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

Αντί για std::priority_queue, μπορούμε να χρησιμοποιήσουμε std::multiset (δείτε ολόκηρο τον κώδικα εδώ).