37ος ΠΔΠ Α' Φάση: Πρόσληψη πιτσαδόρων (hiring) - Λύση
Επεξήγηση εκφώνησης
Σε αυτό το πρόβλημα μας δίνονται τρία συμβόλαια για κάθε έναν από τους \(N\) πιτσαδόρους, με τιμές απόδοσης \(A_i \leq B_i \leq C_i\) για τον \(i\)-οστό πιτσαδόρο. Σκοπός είναι να αναθέσουμε ένα από τα τρία συμβόλαια στον κάθε πιτσαδόρο ώστε να μεγιστοποιήσουμε το άθροισμα των αποδόσεων, με τον περιορισμό ότι μπορεί να έχουμε το πολύ \(X\) συμβόλαια του πρώτου τύπου (χάλκινα), \(Y\) του δεύτερου (ασημένια) και \(Z\) του τρίτου (χρυσά).
Λύση ωμής βίας
Η λύση της ωμής βίας είναι να δοκιμάσουμε όλους τους δυνατούς τρόπους να αναθέσουμε τα συμβόλαια στους πιτσαδόρους ώστε να ικανοποιούνται οι περιορισμοί, και επιλέξουμε αυτόν που μεγιστοποιεί την απόδοση.
Υπάρχουν το πολύ τρία δυνατά συμβόλαια για κάθε πιτσαδόρο, επομένως πρέπει να ελέγξουμε το πολύ \(O(3^N)\) δυνατούς τρόπους, που είναι εκθετικά πολλοί. Η λύση αυτή περνάει μόνο το πρώτο υποπρόβλημα. Μία ενδεικτική αναδρομική υλοποίηση είναι η παρακάτω.
void try_all(const std::vector<Score>& scores, long i, ll cur_ans, long x, long y, long z) {
if (i == scores.size()) {
ans = std::max(ans, cur_ans);
return;
}
if (x + 1 <= X) try_all(scores, i + 1, cur_ans + scores[i].A, x + 1, y, z);
if (y + 1 <= Y) try_all(scores, i + 1, cur_ans + scores[i].B, x, y + 1, z);
if (z + 1 <= Z) try_all(scores, i + 1, cur_ans + scores[i].C, x, y, z + 1);
}
Δείτε ολόκληρο τον κώδικα εδώ.
Λύση για το 2ο και 3ο υποπρόβλημα
Στο 2ο και 3ο υποπρόβλημα υπάρχουν μόνο δύο είδη συμβολαίων (ας υποθέσουμε μόνο χάλκινα και ασημένια). Ξέρουμε ότι κάθε συμβόλαιο θα είναι είτε χάλκινο με απόδοση \(A_i\) είτε ασημένιο με απόδοση \(B_i\), και ότι \(B_i \geq A_i\). Άρα αυτό που κερδίζουμε κάνοντας το \(i\)-οστό συμβόλαιο ασημένιο είναι η διαφορά \(B_i - A_i\). Επομένως, για να μεγιστοποιήσουμε την συνολική απόδοση, ταξινομούμε ως προς τις διαφορές και βάζουμε τις \(Y\) μεγαλύτερες.
// Ταξινόμηση με βάση την διαφορά Bi - Ai.
std::sort(scores.begin(), scores.end(), [](const Score& one, const Score& two) {
return one.B - one.A > two.B - two.A;
});
ll ans = 0;
for (long i = 0; i < N; ++i) {
if (i < Y) ans += scores[i].B;
else ans += scores[i].A;
}
Η ταξινόμηση χρειάζεται \(O(N \log N)\) χρόνο, συνεπώς ο αλγόριθμος χρειάζεται \(O(N \log N)\) χρόνο. Μπορούμε επίσης να χρησιμοποιήσουμε τον αλγόριθμο για το nth_element, για να μειώσουμε τον χρόνο σε \(O(N)\). Δείτε ολόκληρο τον κώδικα εδώ και εδώ.
Λύση για το 4ο υποπρόβλημα
Σε αυτό το υποπρόβλημα μας δίνεται επιπλέον ότι \(A_1 = \ldots = A_N\), \(B_1 \leq \ldots \leq B_N\) και \(C_1 \geq \ldots \geq C_N\). Η βασική παρατήρηση εδώ είναι ότι μας συμφέρει να βάλουμε τα πρώτα \(Z\) στα χρυσά και τα τελευταία \(Y\) από τα υπόλοιπα στα ασημένια. Αυτό μπορεί να υλοποιηθεί με τον εξής άπληστο αλγόριθμο:
for(long i = 0; i < N; ++i) {
long A, B, C;
fscanf(in, "%ld%ld%ld", &A, &B, &C);
if (i < Z) ans += C;
else if (i >= N - Y) ans += B;
else ans += A;
}
Ο αλγόριθμος διατρέχει μία φορά τα δεδομένα επομένως χρειάζεται \(O(N)\) χρόνο και χρησιμοποιεί \(O(1)\) μνήμη. Δείτε ολόκληρο τον κώδικα εδώ.
Λύση για το 5ο υποπρόβλημα
Το 5ο υποπρόβλημα μοιάζει με το 2ο και το 3ο, με την διαφορά ότι έχουμε επιπλέον, ένα χρυσό συμβόλαιο. Αυτό που μπορούμε να κάνουμε είναι να θεωρήσουμε κάθε μία από τις \(N\) πιθανές εκδοχές για το ποιος θα πάρει χρυσό συμβόλαιο και τα συμβόλαια των υπόλοιπων πιτσαδόρων να τα αναθέσουμε με τον αλγόριθμο που χρησιμοποιήσαμε προηγουμένως. Κάτι τέτοιο θα χρειαζόταν \(O(N^2 \log N)\) χρόνο που είναι σχετικά αργό.
Αυτό όμως που παρατηρούμε είναι ότι κάθε φορά που δοκιμάζουμε ένα άλλο \(i\) για να είναι το χρυσό συμβόλαιο, η λύση δεν αλλάζει πολύ. Για την ακρίβεια υπάρχουν οι εξής δύο περιπτώσεις:
- Το \(i\) δεν ανήκει στις \(Y\) μεγαλύτερες διαφορές \(B_i - A_i\), επομένως η απόδοση αυξάνεται κατά την διαφορά \(C_i - A_i\).
- Το \(i\) ανήκει στις \(Y\) μεγαλύτερες διαφορές \(B_i - A_i\), επομένως η απόδοση αυξάνεται κατά την διαφορά \(C_i - B_i\). Το ασημένιο συμβόλαιο του \(i\)-οστού πιτσαδόρου θα διατεθεί στον πιτσαδόρο με κατάταξη \(Y+1\), και η απόδοση αυξάνεται επιπλέον κατά \(B_{Y+1} - A_{Y+1}\).
Ο παρακάτω κώδικας υλοποιεί αυτήν την ιδέα και χρειάζεται \(O(N \log N)\) χρόνο.
// Δοκιμάζουμε όλες τις πιθανότητες για το χρυσό συμβόλαιο.
for (long i = 0; i < N; ++i) {
ll cur_ans = base;
if (i >= Y) {
// Αλλάζουμε ένα χάλκινο σε χρυσό.
cur_ans += scores[i].C - scores[i].A;
} else {
// Αλλάζουμε ένα ασημένιο σε χρυσό.
// Επίσης αυτό μας επιτρέπει να αλλάζουμε ένα χάλκινο σε ασημένιο (και διαλέγουμε
// αυτό με την μέγιστη διαφορά (που δεν έχουμε χρησιμοποιήσει).
cur_ans += scores[i].C - scores[i].B + scores[Y].B - scores[Y].A;
}
ans = std::max(ans, cur_ans);
}
Δείτε ολόκληρο τον κώδικα εδώ.
Γενική λύση
Για να λύσουμε την γενική περίπτωση θα γενικεύσουμε την λύση για το 5ο υποπρόβλημα. Θα ξεκινήσουμε βρίσκοντας μία λύση που έχει \(Y\) ασημένια και \(N-Y\) χάλκινα συμβόλαια. Έπειτα θα προσθέτουμε ένα ένα τα χρυσά συμβόλαια. Κάθε φορά που προσθέτουμε ένα χρυσό συμβόλαιο έχουμε πάλι δύο επιλογές
- Κάνουμε ένα από τα χάλκινα συμβόλαια \(i\) χρυσό, με αλλαγή απόδοσης \(C_i - A_i\), ή
- Κάνουμε ένα από τα ασημένια συμβόλαια \(i\) χρυσό (με αλλαγή απόδοσης \(C_i - B_i\)) και ένα από τα χάλκινα συμβόλαια \(j\) ασημένιο (με αλλαγή απόδοσης \(B_j - A_j\)).
Σε κάθε βήμα θέλουμε να βρούμε ποια αλλαγή μεγιστοποιεί την απόδοση. Για να το κάνουμε αυτό αποδοτικά κρατάμε τρεις ουρές προτεραιότητας: την from_a_to_b που κρατάει τις αλλαγές αποδόσεων από χάλκινα σε ασημένια, την from_a_to_c και την from_b_to_c, αντίστοιχα. Τότε, μπορούμε να ελέγξουμε την μέγιστη αύξηση της απόδοσης για τις δύο περιπτώσεις:
- Περίπτωση 1η: Βρίσκουμε το συμβόλαιο \(i\) που έχει την τιμή
from_a_to_c.front()(αν υπάρχει). - Περίπτωση 2η: Βρίσκουμε το συμβόλαιο \(i\) που έχει την τιμή
from_b_to_c.front()και το συμβόλαιο \(j\) που έχει την τιμήfrom_a_to_b.front()(αν υπάρχουν).
Αν η πρώτη περίπτωση έχει μεγαλύτερη αύξηση, τότε αλλάζουμε το \(i\) σε χρυσό, διαφορετικά αλλάζουμε το \(i\) σε χρυσό και το \(j\) σε ασημένιο.
Οι λεπτομέρειες δίνονται στον παρακάτω κώδικα:
// Βρίσκουμε μία λύση μόνο με τα χάλκινα και τα ασημένια.
ll ans = 0;
std::vector<int> contract(N, 0);
// Κρατάμε τα κόστη του να αναβαθμίσουμε ένα συμβόλαιο σε καλύτερο σε ουρές προτεραιότητας.
std::priority_queue<std::pair<ll /* score */, long /* id */>>
from_a_to_c, from_b_to_c, from_a_to_b;
for (long i = 0; i < N; ++i) {
if (i < Y) {
ans += scores[i].B;
contract[i] = 1;
from_b_to_c.push({ scores[i].C - scores[i].B, i });
}
else {
ans += scores[i].A;
from_a_to_c.push({ scores[i].C - scores[i].A, i });
from_a_to_b.push({ scores[i].B - scores[i].A, i });
}
}
// Προσθέτουμε ένα ένα τα χρυσά.
for (long i = 0; i < Z; ++i) {
// Περίπτωση 1η: Αλλάζουμε ένα χάλκινο σε χρυσό.
ll score_1 = 0;
if (!from_a_to_c.empty()) score_1 = from_a_to_c.top().first;
// Περίπτωση 2η: Αλλάζουμε ένα ασημένιο σε χρυσό.
ll score_2 = 0;
if (!from_b_to_c.empty() && !from_a_to_b.empty()) {
score_2 = from_b_to_c.top().first + from_a_to_b.top().first;
}
if (score_1 >= score_2) {
ans += score_1;
contract[from_a_to_c.top().second] = 2;
} else {
ans += score_2;
contract[from_b_to_c.top().second] = 2;
long id2 = from_a_to_b.top().second;
contract[id2] = 1;
from_b_to_c.push({ scores[id2].C - scores[id2].B, id2 });
}
// Βγάζουμε τα στοιχεία που δεν είναι πια valid.
while (!from_a_to_c.empty() && contract[from_a_to_c.top().second] != 0) from_a_to_c.pop();
while (!from_a_to_b.empty() && contract[from_a_to_b.top().second] != 0) from_a_to_b.pop();
while (!from_b_to_c.empty() && contract[from_b_to_c.top().second] != 1) from_b_to_c.pop();
}
Δείτε ολόκληρο τον κώδικα εδώ.