23ος ΠΔΠ B' Φάση: Εταιρική ιεραρχία (company) - Λύση

Σημείωση: Η λύση αυτή απαιτεί βασικές γνώσεις δένδρων και αναδρομής.

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

Πρέπει να υπολογίσουμε τη διαφορά μεταξύ του πλήθους των ιεραρχικών σχέσεων με προϊστάμενο γυναίκα (\(r\_f\)) και αυτών με προϊστάμενο άντρα (\(r\_m\)), δηλαδή την ποσότητα \(r\_m - r\_f\). Μία ιεραρχική σχέση είναι μία άμεση σχέση προϊσταμένου-υφισταμένου ή μία έμμεση, όπου μεσολαβούν αρκετοί υπάλληλοι.

Brute force λύση

Η brute force λύση είναι για κάθε εργαζόμενο να μετράμε αναδρομικά πόσοι ιεραρχικά ανώτεροί του έχουν αντίθετο φύλο από αυτόν και ανάλογα με το φύλο του, να αυξάνουμε ή να μειώνουμε τη μεταβλητή αποτελέσματος, έστω \(D\). Η \(D\) δηλαδή θα διατηρεί τη μέχρι τώρα υπολογισμένη τιμή της διαφοράς \(r\_m - r\_f\).

Ο αναδρομικός υπολογισμός που αναφέραμε μπορεί να γίνει ως εξής: Ορίζουμε τη συνάρτηση calc(id, w_sex), που θα δέχεται το id του τρέχοντος προϊσταμένου και το φύλο w_sex του εργαζομένου από τον οποίο ξεκίνησε η αναδρομή. Όποτε συναντάται προϊστάμενος αντίθετου φύλου θα μεταβάλλεται η τιμή της μεταβλητής \(D\) (\(+1\) αν ο προϊστάμενος είναι άντρας, αλλιώς \(-1\)), ενώ σε κάθε περίπτωση η αναδρομική συνάρτηση θα καλείται και για τον υφιστάμενο του τρέχοντος προϊσταμένου. Καλώντας calc για τον διευθυντή με απροσδιόριστο φίλο υφισταμένου, υπολογίζει το \(D\).

Η χειρότερη περίπτωση για αυτόν τον αλγόριθμο είναι αν το ιεραρχικό δέντρο είναι μία γραμμή. Εκεί χρειάζονται \(\mathcal{O}(N^2)\) κλήσεις της αναδρομικής συνάρτησης. Επομένως, η χρονική πολυπλοκότητα του αλγορίθμου είναι \(\mathcal{O}(N^2)\). Η χωρική πολυπλοκότητα είναι \(\mathcal{O}(N)\). Η λύση αυτή δε θα περάσει όλα τα testcases.

#include <cstdio>
using namespace std;
const long MAXN = 400005;
// Πίνακας με id προϊσταμένων
long P[MAXN];
// Πίνακας με φύλο εργαζομένων
char S[MAXN];
// Μεταβλητή για το αποτέλεσμα (r_m - r_f)
long D;
// Αναδρομική συνάρτηση υπολογισμών
void calc(long id, char w_sex) {
    // Αν κλήθηκες από το διευθυντή απλά επίστρεψε
    if (!id)
        return;
    // Αν έχεις άλλο φύλο από τον εργαζόμενο άλλαξε το D
    if (S[id] != w_sex) {
        if (S[id] == 'm')
            D++;
        else
            D--;
    }
    // Κάλεσε τη συνάρτηση για τον προσϊστάμενό σου
    calc(P[id], w_sex);
}
int main() {
    freopen("company.in", "r", stdin);
    freopen("company.out", "w", stdout);
    long N;
    scanf("%ld", &N);
    // Διάβασε τα id των προϊσταμένων και τα φύλα των εργαζομένων
    for (long i = 1; i <= N; i++) {
        scanf("%ld %c", &P[i], &S[i]);
    }
    // Ρύθμισε αναδρομικά το D για κάθε εργαζόμενο
    for (long i = 1; i <= N; i++) {
        calc(P[i], S[i]);
    }
    // Εκτύπωσε το αποτέλεσμα
    printf("%ld\n", D);
    return(0);
}

Βέλτιστη λύση με Δυναμικό προγραμματισμό

Η προηγούμενη λύση είχε αυξημένη πολυπλοκότητα καθώς γίνονταν \(\mathcal{O}(N)\) κλήσεις της αναδρομικής συνάρτησης για κάθε εργαζόμενο. Αυτές οι κλήσεις ουσιαστικά έγιναν για να υπολογίσουμε πόσοι ιεραρχικά ανώτεροι προϊστάμενοι του κάθε εργαζομένου έχουν φύλο αντίθετο από το δικό του. Αν μπορούσαμε να ξέρουμε γρήγορα πόσοι ιεραρχικά ανώτεροι προϊστάμενοι κάθε εργαζομένου είναι άντρες και πόσοι γυναίκες, τότε θα είχαμε την απαιτούμενη πληροφορία. Αυτός ο υπολογισμός μπορεί να γίνει γρήγορα εάν χρησιμοποιήσουμε την εξής παρατήρηση:

Παρατήρηση: Εάν γνωρίζουμε πόσοι ιεραρχικά ανώτεροι του προϊσταμένου ενός εργαζομένου έχουν το κάθε φύλο, τότε μπορούμε να υπολογίσουμε πόσοι ιεραρχικά ανώτεροι του εργαζομένου αυτού έχουν το κάθε φύλλο απλά αυξάνοντας κατά \(1\) το πλήθος αυτών με το φύλο του προϊσταμένου του.

Ορίζουμε, λοιπόν, dp(id) πόσοι ιεραρχικά ανώτεροι του id-οστού εργαζομένου από το κάθε φύλο υπάρχουν. Υπολογίζουμε dp[id] είτε άμεσα μέσω της πληροφορίας αυτής για τον προϊστάμενό του αν είναι διαθέσιμη, είτε έμμεσα καλώντας τη συνάρτηση αυτήν πρώτα για τον προϊστάμενο του. Οι προϊστάμενοι κάθε φύλου για το διευθυντή είναι \(0\).

Μετά από τον υπολογισμό αυτόν μπορούμε να μεταβάλλουμε κατάλληλα το \(D\) για κάθε εργαζόμενο, ανάλογα με το πλήθος ιεραρχικά ανωτέρων του με αντίθετο φύλο από αυτόν.

Η συνάρτηση dp θα κληθεί ακριβώς μία φορά για κάθε εργαζόμενο, άρα η χρονική πολυπλοκότητα αυτής της λύσης είναι \(\mathcal{O}(N)\). Η χωρική πολυπλοκότητα είναι και εδώ \(\mathcal{O}(N)\). Ο αλγόριθμος αυτός περνάει όλα τα testcases και έχει βέλτιστη πολυπλοκότητα.

#include <cstdio>
using namespace std;
const long MAXN = 400005;
// Πίνακας με id προϊσταμένων
long P[MAXN];
// Πίνακας με φύλο εργαζομένων
char S[MAXN];
// Μεταβλητή για το αποτέλεσμα (r_m - r_f)
long D;
// Πίνακες δυναμικού προγραμματισμού πλήθους ιεραρχικά ανώτερων για κάθε φύλο
long CNT_M[MAXN], CNT_F[MAXN];
// Αναδρομική συνάρτηση υπολογισμών
void dp(long id) {
    // Αν δεν έχουν γίνει οι υπολογισμοί του προϊσταμένου σου τότε κάνε τους
    if (CNT_M[P[id]] == -1)
        dp(P[id]);
    // Τα πλήθη ιεραρχικά ανώτερων κάθε φύλου είναι ίσα με του προϊσταμένου...
    CNT_M[id] = CNT_M[P[id]];
    CNT_F[id] = CNT_F[P[id]];
    // ... βάζοντας +1 στο φύλο του προϊσταμένου
    if (S[P[id]] == 'm')
        CNT_M[id]++;
    else
        CNT_F[id]++;
}
int main() {
    freopen("company.in", "r", stdin);
    freopen("company.out", "w", stdout);
    long N;
    scanf("%ld", &N);
    for (long i = 1; i <= N; i++) {
        // Διάβασε τα id των προϊσταμένων και τα φύλα των εργαζομένων
        scanf("%ld %c", &P[i], &S[i]);
        // Το -1 δηλώνει ότι δεν έχουν γίνει οι υπολογισμοί
        if (P[i])
            CNT_M[i] = CNT_F[i] = -1;
    }
    // Ρύθμισε αναδρομικά το D για κάθε εργαζόμενο
    for (long i = 1; i <= N; i++) {
        // Αν δεν έχουν γίνει οι υπολογισμοί κάνε τους
        if (CNT_M[i] == -1)
            dp(i);
        // Ρύθμισε το D ανάλογα με το φύλο του και τους υπολογισμούς
        if (S[i] == 'f')
            D += CNT_M[i];
        else
            D -= CNT_F[i];
    }
    // Εκτύπωσε το αποτέλεσμα
    printf("%ld\n", D);
    return(0);
}