# Zadanie 6


### IDEA:
Dzielimy tablicę $A$ o $n$ elementach $a_i$ na dwie podtablice $L$ i $P$ poprzez zapamiętywanie odpowiednich wskaźników wskazujących na dany element tablicy $L$ oraz $P$. Na początku ustawiamy lewy wskaźnik na $0$ oraz prawy na $\lceil n/2 \rceil$. Przechodzimy tablicę wskaźnikiem prawym aż uzyskamy $right >=n$, $right$ to prawy wskaźnik.
Wskaźnik $left$ inkrementujemy tylko jeśli dany element z tablicy $P$ jest conajmniej dwukrotnie większy od aktualnego elementu z $L$. Wtedy również zwiększamy ilość liczb, które możemy usunąć ($count$) o dwa, ponieważ usunęliśmy element z $L$ oraz $P$.
$right$ inkrementujemy z każdym wykonaniem pętli.

def func(a[], n) {
    count = 0
    left = 0
    right = ceil(n / 2)
    for(right = ceil(n / 2); right < n; right++){
        if(2 * a[left] <= a[right]){
            left += 1
            count += 2
        }
    }
    return count;
}

**Złożoność czasowa:** $O(n)$, bo przechodzimy przez całą tablicę raz.
**Złożoność pamięciowa:** $O(n)$, przechowujemy tylko rozmiar tablicy oraz 3 zmienne(dwa wskaźniki i jeden licznik).

#### Lemat 1
Zawsze istnieje optymalne rozwiązanie $T$, takie że $\forall (x,y) \in T$, $x \in L$ oraz $y \in P$

**D-d:**
Weźmy dowlne optymalne rozwiązanie $O$, pokażemy, że możemy przekształcić je w $O'$, takie że $\forall (x,y) \in O'$, $x \in L$ oraz $y \in P$.

Weźmy dowolną parę $(x, y) \in O$ oraz pusty zbiór $O'$.

Jeżeli $x \in L$ oraz $y \in P$ dodaj parę $(x,y)$ do $O'$
Jeżeli $x \in L$ oraz $y \in L$:

1. Jeżeli istnieje para $(a, b) \in O$, taka że $a \in P$ oraz $b \in P$, wtedy dodaj do $O'$ pary $(x, a)$ oraz $(y, b)$. Możemy połączyć te pary ponieważ wiemy, że $x \leq y \leq a \leq b$ i $2x \leq y$ oraz $2a \leq b$, stąd $2x \leq a$ i $2y \leq b$, czyli pary $(x,a), (y,b)$ są poprawne.
2. Wpp. istnieje przynajmniej jeden elemnty w zbiorze $P$, który nie znajduje się w żadnej parze w rozwiązaniu $O$ nazwijmy ten elemnty $z$. Skoro $z \in P$ to $y \leq z$, stąd $2x \leq z$, więc do $O'$ dodajmy parę $(x,z)$.
3. Jeżeli $x \in P$ oraz $y \in P$: analogicznie jak dla przypadku $x \in L$, $y \in L$.

Wykonując przeształcenia jak powyżej $\forall(x,y)\in O$ otrzymamy optymalne rozwiązanie $O'$, takie że $\forall(x',y')\in O'$, $x'\in L$ oraz $y'\in P$

#### Dowód poprawności:

$T$ - rozwiązanie naszego algorytmu
$O$ - rozwiązanie optymalne, takie że $\forall(x,y)\in O$, $x\in L$, $y\in P$ - lemat 1

Załóżmy nie wprost, że $|T| < |O|$.
Wiemy wtedy, że istnieje $x \in L$ oraz $y \in P$, takie że $\exists_ a (x, a) \in O$ oraz $\exists_ b (b, y) \in O$ oraz $\forall_ a (x, a) \notin T$ oraz $\forall_ b (b, y) \notin T$.

Niech $x' = max(\{c | (c,d) \in T\})$
Niech $g' = g$ t. że $(x', g) \in T$
Niech $y' = min(\{d | (c,d) \in T\})$
Niech $f' = f$ t. że $(f, y') \in T$

Jeżeli $x' > x$ to wtedy wynik naszego algorytmu zawierałby parę $(x, g')$ bądź jakiś element mniejszy od $g'$ ale zawierałby $x$ sprzeczność.

Jeżeli $y' < y$ oraz $g' > y$ (z poprzedniego podpunktu wiemy, że $b > x'$) to wtedy nasz algorytm wcześniej utworzyłby parę $(x',y)$ sprzeczność.

Jeżeli $y' < y$ oraz $g' < y$ to wtedy z działania naszego algorytmu para $(b, y) \in T$ bądź jakiś element mniejszy od $b$ ale zawierałoby $y$ sprzeczność.

Zostaje nam przypadek że $x' \leq x$ oraz $y' \geq y$.
Skoro $y' \geq y$ oraz $\exists_ b (b, y) \in O$ i $\forall_ b(b,y)\notin T$ to oznacza, że nasz algorytm nie znalazł żadnego elementu pasującego do $y$ mimo to, że przejrzał wszystkie elementy oraz wiemy że taki element (co najmniej jeden istnieje) co jest sprzeczne z działaniem alogrytmu sprzeczność.

Zatem $|T| = |O|$, stąd nasz algorytm jest optymalny.

Warunek stopu oczywisty - iterujemy się od $\lceil{n/2}\rceil$ do $n$.

$$ \begin{pmatrix} 1 & 1 & 0 & 0 & 0\ 0 & 1 & 0 & 0 & 0\ 0 & 0 & 0 & 1 & 0\ 0 & 0 & 0 & 0 & 1\ 1 & 1 & 1 & 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} i+2\ 1\ fi\ f{i+1}\ f{i+2}\ \end{pmatrix}= \begin{pmatrix} i+4\ 1\ f{i+1}\ f{i+2}\ f{i+3} \end{pmatrix} $$