# HIV3

## Zadanie 2

Mając 3 proste $A,B,C$ o wzorach:
- $A: y = m_Ax + c_A$
- $B: y = m_Bx + c_B$
- $C: y = m_Cx + c_C$

(gdzie b.s.o. $c_A < c_B$)

Sprawdźmy jak możemy określić, czy proste $A, B$ "zakrywają" prostą $C$.

### Przypadek: $c_C < c_A < c_B$

(Ja tutaj rozpatruję zwykle po jednym przypadku, bo dużo jest przypadków symetrycznych).

#### 1. $sgn(m_A)=sgn(m_B)$
Wówczas prosta $C$ będzie zakryta jeśli $m_A \leq m_C \leq m_B$.

#### 1. $sgn(m_A)\neq sgn(m_B)$

Wówczas prosta $C$ będzie zakryta jeśli $m_A \leq m_C \leq m_B$.

#### Wniosek?

Generalnie współczynnik $m_C$ musi się mieścić pomiędzy współczynnikami $m_A$ i $m_B$.

### Przypadek: $c_A < c_C < c_B$

#### 1. $sgn(m_A)=sgn(m_B)$

Tutaj sytuacja jest całkiem interesująca. Dolna granica naszego $m_C$ jest całkiem prosta, bo po prostu musi zajść $m_B\leq m_C$ (w przypadku symetrycznym gdzie $m_A<m_B$ robimy to samo ale po drugiej stronie osi OY). Za to górna granica jest uzależniona od punktu przecięcia.
Możemy obliczyć punkt przecięcia $(x, y)$.
$m_Bx + c_B = m_Ax + c_A \rightarrow x=\frac{c_A - c_B}{m_B - m_A}$.
$y = m_A(\frac{c_A - c_B}{m_B - m_A}) + c_A$

Teraz możemy obliczyć współczynnik kierunkowy $m_C'$:
$m_C' = \frac{m_A(\frac{c_A - c_B}{m_B - m_A}) + c_A - c_C}{\frac{c_A - c_B}{m_B - m_A}}=m_A+\frac{m_A-m_B}{c_A-c_B}(c_C - c_A)$

Czyli nasze $m_C$ będzie do takiej wartości raczej. Mało nam ona mówi aktualnie, ale później się okaże, że jest ona całkiem sensowna.

#### 1. $sgn(m_A)\neq sgn(m_B)$
Przypadek symetryczny do poprzedniego tak naprawdę.

#### Wniosek?
Generalnie współczynnik $m_C$ musi się mieścić pomiędzy jednym ze współczynników prostych $A$ i $B$ i jakąś liczbą, która okaże się niebawem całkiem sensowna.

### Przypadek: $c_A < c_B < c_C$
Tu chyba jest oczywiste, że nieważne jaki współczynnik będzie, to proste $A, B$ nie dadzą rady zakryć.

### Podejście jakiegoś rozwiązania

Zamieńmy każdą prostą na punkt $(m_i, c_i)$. Zobaczmy wówczas jak takie punkty się zachowuje względem tych przypadków które już rozpatrzeliśmy.

### Przypadek: $c_C < c_A < c_B$


Wywnioskowaliśmy, że współczynnik $m_C$ będzie musiał się mieścić pomiędzy współczynnikami $m_A$ i $m_B$.

### Przypadek: $c_A < c_C < c_B$

Tutaj wywnioskowaliśmy, że współczynnik musi mieścić się od jednego współczynnika do jakiejś liczby. Narysujmy sobie zatem takie rysunek:


Wyznaczymy wzór na prostą $AB$:
$m_{AB} = \frac{c_B - c_A}{m_B - m_A}$
$c_{AB} = c_A - \frac{c_B - c_A}{m_B - m_A}(m_A)$

Teraz zobaczmy dla jakiej wartości $m$ prosta $AB$ osiągnie wartość $c_C$:
$m = \frac{c_C - c_A + \frac{c_B - c_A}{m_B - m_A}(m_A)}{\frac{c_B - c_A}{m_B - m_A}} = m_A +\frac{c_B - c_A}{m_B - m_A}(c_C - c_A)$.

Otrzymaliśmy tą samą wartością. Co to tak naprawdę oznacza w takim razie? **Nasz punkt $C$ nie może przekroczyć prostej $AB$ jeśli prosta $C$ ma zostać zakryta prostymi $A$ i $B$.**

### Przypadek: $c_A < c_B < c_C$

Ten przypadek już omówiliśmy.

### Wniosek?

Jeśli punkt $C$ znajduja się poniżej prostej wyznaczonej przez punkty $AB$, to prosta $C$ jest zakryta przez proste $AB$. Redukujemy więc nasze zadanie i otrzymujemy trochę prostszy problem: **wyznaczyć takie punkty $(m_i, c_i)$, że jak wybierzemy dowolne trzy punkty z nich, to punkt pomiędzy nimi leży nad prostą wyznaczoną przez pozostałe.**

Jest to problem górnej otoczki wypukły (upper convex hull problem) - odsyłam to https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain. Pewnie rozpiszę tutaj później.

## Zadanie 3

### Idea
Załóżmy, że mamy już dwie poprawne otoczki $O_1$ i $O_2$.
Powiedzmy, że jest między nimi pionowa linia.
Weźmy dwa wierzchołki, po jednym z każdej otoczki, który jest najbliżej prostej.
Rozważmy osobno górną i dolną prostą otoczki (przypadki są symetryczne).
Weźmy prostą łączące te dwa wierzchołki.
Jeśli istnieje jakiś wierzchołek w $O_1$, który jest nad prostą, to powiemy, że ten wierzchołek
będzie nowym przez, który poprowadzimy prostą. Jeśli już nie będzie takiego wierzchołka to robimy to samo dla $O_2$.

### Czemu to działa?
No zobaczmy, że tak naprawdę zachłannie szukamy pierwszego który działa. Nie może być mniejszej, bo mniejsze oznacza, że jest wcześniej wierzchołek, który to spełnia, a my idziemy po kolei.

### Ewentualne uwagi
Możemy spróbować wprost określić jakiś wzór kiedy wierzchołek rzeczywiście jest "nad" lub "pod" prostą. Mi się np. nie chciało o tym myśleć

### Ewentualnie trochę inne podejście
Rozdzielamy sobie obie otoczki na górną i dolną. Bierzemy tą otoczkę która jest po lewej. Lecimy po kolejny punktach q z górnej otoczki po prawej. Powiedzmy że dwa ostatnie punkty prawej otoczki to p[n-1] i p[n]. Jeżeli strzałeczki p[n-1] -> p[n] -> q tworzą cykl zgodny z kierunkiem wskazówek zegara, to normalnie bierzemy to q do naszej otoczki. Jeżeli nie, to wywalamy punkt p[n] z otoczki i powtarzamy sprawdzanie. (tak z resztą działa standardowy algorytm otoczki wypukłej).

# Zadanie 4

## Idea
Odkrywamy roota i jego jedno dziecko.
Mamy 2 możliwości:
1. dziecko jest większe
Wtedy odkrywamy drugie dziecko
Jeśli też jest większe to mamy minimum, jeśli nie patrz 2.
2. dziecko jest mniejsze
Ignorujemy rodzica i odkrywamy dzieci dziecka

## Przykład
No dla takiego prostego drzewa
Odkrywamy A i B. Załóżmy, że A < B.
Wtedy odkrywamy C. Jeśli A < C to triw, więc załóżmy A > C.

Teraz ignorujemy A i przechodzimy do C.
Odkrywamy F i powiedzmy F > C, bo jeśli F < C to mamy minimum w F.
Wtedy odkrywamy G i znów albo G < C i mamy minimum w G lub G > C i jest minimum w C.

I to tak się rozrasta niżej. Potencjalnie dojdziemy aż do liścia

Odkrywamy 2*log[2,n] - 1

Tak, da się lepiej

# Zadanie 5

a) Jakiś trywialny DFS z każdego wierzchołka. Jeśli waga == C to dodajemy do wyniku. Naszą odpowiedzią jest wynik/2, bo każdą ścieżkę policzymy 2 razy.
Złożonościowo to $O(N^2)$, gdzie N to liczba wierzchołków.
::: warning

UWAGA $O(N^2)~$ podobno nie zawsze przechodzi
:::
No ogólnie słabo i na pewno można lepiej np. DP $O(NK)$, gdzie K to stopień wierzchołka, a N to liczba wierzchołków.

b)
Chyba harde nwm

# Zadanie 6
a) Możemy przekątne trzymać w tablicy o rozmiarze 2n - 1. Gdzie każda przekątna ma swoje miejsce w tablicy.
Wtedy dodawanie tablic rzeczywiście jest w O(n)
b) Były pomysły o przekątnych, ale do dopracowania

# Zadanie 7

## Idea
Będziemy chcieli korzystać z merge sorta

Powiedzmy, że mamy dwie posortowane tablice $t_1$ i $t_2$, które chcemy mergować.
Niech $i$ wskazuje element w $t_1$, a $j$ w $t_2$.
Jeśli $t_1[i]$ > $t_2[j]$ to dodajemy $t_1.size() - i$ inwersji //to chyba śmiga, ale do sprawdzenia

## Czemu to działa?
No wydaje mi się, że to jakoś wprost wynika z działania mergesorta. Mamy niezmiennik, że liczby są posortowane.
Jeśli w 'dalszej' tablicy jest jakiś mniejszy element to musi być mniejszy od reszty elementów z 'bliższej' tablicy, której jeszcze nie wzięliśmy pod uwagę.
Stąd można wprost policzyć te inwersje

Jakiś pseudokod:

merge_sort(arr, l, r)
    inv_count += (arr, l, (l+r)/2)
    inv_count += (arr, (l+r)/2 + 1, r)
    inv_count += merge(arr, l, r )
    return inv_count


merge(arr, l, r):
    i = l, j = r, m = (l+r)/2 + 1
    while(i <= m - 1 && j <= r){
        if(arr[i] <= arr[j]){
            
        }
        else{
            inv_count += m - i;
        }
    }

    //Dopchaj jeśli tam szybciej się skończy jak klasyczny merge

    return inv_count