---
# System prepended metadata

title: Untitled

---

## **A: Rep-ore-ting**
### Cel:

Si dla każdej z T gdzie Si będzie liczbą uporządkowanych par pracowników

(x,y) tak, że pracownik x może bezpośrednio lub pośrednio otrzymywać raporty od pracownika y po utworzeniu pierwszych i par partnerskich

Mamy wypluć iloczyn Si … m mod 1,000,000,007.

### Rozwiązanie:

Do Si zawsze  musimy doliczyć  $N(N−1)/2$ bo każdy pracownik może raportować pracownikowi wyżej. Żeby obliczyć pary które mogą się ze sobą komunikować pomimo że komunikująca osoba ma stopień wyżej niż otrzymująca komunikat.

Spróbujemy dla i-tej pary podzielić pracowników na grupy tż. każdy pracownik w jednej grupie może komunikować się z resztą w tej grupie.

Potem jeżeli dodamy relację pomiędzy pracownikami z dwóch różnych grup to będziemy musieli je zmergować. Czyli Union Find $O((N+M)log(N))$

## B: **Auth-ore-ization**
$N$ - długość planszy, $M$ - liczba pracowników 
### Cel:
Iloczyn $D_i$. $D_i$ - minimalna liczba kroków dla pracownika i tż. dojdzie on do docelowego pokoju

### Rozwiązanie:

Najpierw zaznaczamy do których pokoi może wejść agent $L_i$. Skoro mamy planszę $3xN$ podróżując z jednego punktu do drugiego nie będziemy mieli momentu w którym wystąpiłaby potrzeba zrobienia "podkowy", oprócz momentów końcowych.
Możliwości ruchów wyglądają tak:
a) Idziemy z  $(R1_i,C1_i)$ do  $(R1_i,a)$ - pierwsze ruchy
b) Idziemy z $(R1_i,a)$ do $(R2_i,b)$ - środek
c) Idziemy z $(R2_i​,b)$ do $(R2_i,C2_i)$ - ostatnie ruchy

Dla pierwszego i ostatniego przypadku trzymamy set wierszy, które można przejść w całości (są wypełnione jedynkami). Chcemy wtedy znaleźć piewszy pełny wiersz nad startem / pod celem. 

Dla drogi pomiędzy będziemy trzymać drzewo przedziałowe postawione na liczbie wierszy. Wierzchołek i będzie trzymać macierz 3x3 mówiący jaka jest najkrótsza droga pomiędzy przedziałami $x_i$ $y_i$ przechodząca przez a i b używając ruchów prawo/lewo/dół.

Przerabiamy pracowników rosnąco. Każde zaznaczenie punktu na dostępny to update na drzewie w punkcie. Złożoność: $O((N+M)log(N))$
## C: Perf-ore-mance
### Cel:
Maksymalna możliwa liczba pracowników, których zarobki możemy określić.
### Rozwiązanie:
Możemy patrzeć na strukturę firmy jak na drzewo, gdzie niżej od pracownika $i$ są tylko jego podwładni. Możemy określić zarobki pracownika i wtedy gdy: 
a) ojciec $i$ ma jednego syna i poddrzewo $i$ jest większe równe $K$
b) ojciec $i$ ma dwóch synów, poddrzewo dziadka $i$ jest większe równe $K$ oraz dla innych synów dziadka wielkości poddrzew wynoszą 1 albo są większe od $K$. Użyjemy programowania dynamicznego w postaci $DP[wierzchołek][wielkośćPoddrzewa ]$. - maksymalna liczba ludzi w poddrzewie, których pensję możemy obliczyć.