Zadanie 4. Korporacja
W korporacji pracuje n osób, które na potrzeby zadania ponumerujemy liczbami 1, 2, …, n.
Pracownik numer 1 jest prezesem korporacji, a każdy z pozostałych pracowników ma
dokładnie jednego bezpośredniego przełożonego.
Numer bezpośredniego przełożonego pracownika x jest zawsze mniejszy od numeru tego
pracownika.
Prezes korporacji nie ma żadnego przełożonego. Przełożonym pracownika jest jego
bezpośredni przełożony i każdy przełożony tego bezpośredniego przełożonego.
Jeśli x jest (bezpośrednim) przełożonym y, to powiemy, że y jest (bezpośrednim)
podwładnym x. Prezes jest przełożonym każdego pracownika.
Przykład 1.
Rysunek 1. Przykład hierarchii w korporacji (strzałki wskazują na bezpośrednich
przełożonych).
Przełożonymi pracownika 7 są pracownicy 3, 2 i 1. Bezpośrednim przełożonym pracownika 7
jest pracownik 3. Pracownik 3 (podobnie jak 5 oraz 6) jest bezpośrednim podwładnym
pracownika 2, a podwładnymi pracownika 2 są pracownicy 3, 5, 6 i 7.
1
1
Odpowiedź: 4.1. Dla hierarchii z Rysunku 1.: | Pracownik | Bezpośredni podwładni | Wszyscy podwładni | |---|---|---| | 1 | 2 | 7 | | 2 | 3 | 4 | | 3 | 1 | 1 | | 4 | 1 | 1 | | 5 | 0 | 0 | | 6 | 0 | 0 | | 7 | 0 | 0 | | 8 | 0 | 0 | 4.2. 25 113 4.3. 2 19 — pracownik numer 2 ma 19 bezpośrednich podwładnych. 4.4. 22 2 — największa liczba przełożonych to 22, a takich pracowników jest 2.
\nTreść zadania (CKE)
\nStruktura danych — to jest drzewo
\nHierarchia korporacji to drzewo ukorzenione w prezesie:
\nPlik korpo.txt to zapis tablicy rodziców: przel[i] w i-tym wierszu.
\nRozwiązania wszystkich podpunktów
\n```python
przel = [int(x) for x in open('korpo.txt')]
n = len(przel) # przel[0] dotyczy pracownika 1
4.2 — liczba liści
bezposredni = [0] * (n + 1)
for i in range(2, n + 1):
bezposredni[przel[i - 1]] += 1
print('4.2', sum(1 for i in range(1, n + 1) if bezposredni[i] == 0))
4.3 — najwięcej bezpośrednich podwładnych
naj = max(range(1, n + 1), key=lambda i: bezposredni[i])
print('4.3', naj, bezposredni[naj])
4.4 — największa liczba przełożonych (głębokość)
glebokosc = [0] * (n + 1)
for i in range(2, n + 1): # numer przełożonego < i, więc jest już policzony
glebokosc[i] = glebokosc[przel[i - 1]] + 1
m = max(glebokosc[1:])
print('4.4', m, glebokosc.count(m))
```
Wszystko w jednym przebiegu po tablicy — złożoność O(n).
\nDlaczego kolejność numerów ma znaczenie
\nGdyby przełożony mógł mieć numer większy od podwładnego, tablicy głębokości nie dałoby się wypełnić prostą pętlą rosnącą — trzeba by przejść drzewo w porządku BFS/DFS od korzenia. Zadanie celowo daje tę gwarancję, żeby rozwiązanie mieściło się w jednej pętli.
\nPunktacja CKE
\nTypowy błąd: Warunek „numer przełożonego jest zawsze mniejszy" to nie ozdobnik — to klucz do wydajności. Dzięki niemu można policzyć liczbę przełożonych jednym przebiegiem od 1 do n, bo przetwarzając pracownika i, jego przełożony jest już policzony: `` przelozonych[i] = przelozonych[przel[i]] + 1 `` Bez tej obserwacji naturalne jest wspinanie się po drzewie dla każdego pracownika osobno — to działa, ale przy 50 000 pracowników i głębokim drzewie robi się kwadratowo wolne. 4.2 — „nie jest przełożonym żadnego pracownika" to liście drzewa, czyli pracownicy o zerowej liczbie bezpośrednich podwładnych. Nie mylić z „nie ma przełożonego" — taki jest tylko jeden, prezes. 4.4 — pytanie jest o przełożonych, nie podwładnych, i o wszystkich, nie bezpośrednich. To po prostu głębokość pracownika w drzewie. Odpowiedź ma dwie liczby: maksymalną głębokość i liczbę pracowników na tej głębokości. W 4.1 kolumny łatwo pomylić. „Wszyscy podwładni" liczy całe poddrzewo, nie tylko dzieci — pracownik 2 ma 3 bezpośrednich (3, 5, 6), ale 4 wszystkich (dochodzi 7).