# Lista 4

## Zadanie 1

Niech $A$ będzie tablicą $n\times m$ zawierającą koszty stanięcia na dane pole.
Niech tablica $D$ będzie $(n+2)\times m$ i niech wartość elementu $d_{i,j}$ odpowiada najtańszej drodze do pola $i,j$ w $A$.

W pierwszej kolumnie tablicy $D$ przekopiujmy wartości z $A$. Wiersze $0$ oraz $n+1$ wypełnijmy nieskończonością.

paths(A[][],D[][]):
    for j = 2, 3, ... , m
    
        // Przypadek, w którym przechodzimy drogę z poprzedniej kolumny
        for i = 1, 2, ... , n
            D[i][j] = A[i][j] + min(D[i-1][j-1], D[i],[j-1], D[i+1], [j-1])
        
        // Rozważamy możliwość przejścia z dołu
        for i = 1, 2, ... , n
            D[i][j] = min(D[i][j], D[i+1][j] + A[i][j])
        
        // Rozważamy możliwość przejścia z góry
        for i = 1, 2, ... , n
            D[i][j] = min(D[i][j], D[i-1][j] + A[i][j])    
            
return min(D[][m])

Aby odtworzyć ścieżkę wystarczy znaleźć minimalną wartość $w$ z $m$-tej kolumny i w sąsiedztwie (z lewej strony) wyszukać pole o wartości $w - A[k][m]$.

Złożoność mamy $O(m \cdot 3n) = O(nm)$.

Weźmy dowolną najkrótszą drogę, zauważmy, że w żadnej kolumnie nie wykonuje ruchów zarówno w dół jak i w górę. Wpp. moglibyśmy wziąć taki element drogi, która sekwenycjnie wykonuje ruch w dół, w górę i zabrać te dwa ruchy, tym samym polepszając drogę.

## Zadanie 3

Niech $P$ będzie listą par wejściowych o długości $r$. $F$ będzie tablicą, która dla $i$-tego elementu posiada wartość $i! \mod p$, $INV$ dla $i$-tego elementu zawiera $i^{-1} \mod p$, natomiast $INV\_F$ dla $i$-tego elementu przechowuje wartość $i!^{-1} \mod p$.

def binom_coef(P,p):
    F = [1,1]
    INV = [1,1]
    INV_F = [1,1]
    n_max = 1
    for (n,k) in P:
        if n > n_max:
            for i in range (n_max+1, n+1):
                F.append((F[i-1]*i) % p)
                INV.append((p - (p//i) * INV[p%i]) %p)
                INV_F.append((INV[i] * INV_F[i-1]) %p)
            n_max = n
        print((F[n] * INV_F[k] * INV_F[n-k]) %p)

#### Lemat 1
Dla $p$ będącą liczbą pierwszą oraz $i < p$.
$$
i^{-1} \equiv - \Big\lfloor \frac{p}{i} \Big\rfloor \cdot (p \mod i)^{-1} \mod p
$$

Dowód:

Z definicji:
$$
p \mod i = p - \Big\lfloor \frac{p}{i} \Big\rfloor \cdot i
$$

Zastosujmy $\mod p$ na obu stronach równania:
$$
p \mod i \equiv - \Big\lfloor \frac{p}{i} \Big\rfloor \cdot i \mod p
$$
Pomnóżmy obie strony przez $i^{-1} \cdot (p \mod i)^{-1}$
$$
(i^{-1} \cdot (p \mod i)^{-1} \cdot p) \mod i \equiv (- \Big\lfloor \frac{p}{i} \Big\rfloor \cdot i \cdot i^{-1} \cdot (p \mod i)^{-1} \mod p)\\
i^{-1} = - \Big\lfloor \frac{p}{i} \Big\rfloor \cdot (p \mod i)^{-1} \mod p
$$

## Zadanie 4

Oznaczenia:
$L(i,j)$ jest długością najdłuższego wspólnego podciągu dla $A_{1,i}$ oraz $B_{1,j}$.

Niech $B[k:j]$ lub $B_{k,j}$ oznacza ciąg $b_k b_{k+1} ... b_j$ dla $j \leq k$ i $b_k b_{k-1}...b_j$ wpp.

Naturalnym wydaje się, że aby zmniejszyć złożoność pamięciową, trzeba zamiast całej macierzy wykorzystać dwa wiersze -- w końcu odnosimy się tylko do poprzedniego wiersza i ewentualnie komórki w wierzszu, w którym aktualnie się znajdujemy.

def LSC(n, m, A, B, LL):
    K[] = [0,0 ... 0] 
    for i in range (1,m+1):
        K[0,i] = K[1,i]
        for j in range (1,n+1):
            if A[i] == B[j]:
                K[1,j] = K[0, j-1] + 1
            else:
                K[1,j] = max(K[1,j-1], K[0,j])
    
    for j in range (0,m+1)
        LL[j] = K[1,j]
        
    return LL

Algorytm jest analogiczny do tego z wykładu z wyjątkiem tego, że zamiast korzystać z całej macierzy wykorzystujemy tylko dwa wiersze przepisując je w międzyczasie. Złożoność wciąż wynosi $O(n^2)$, natomiast ze względu na to, że przechowujemy tylko dwa wiersze z macierzy $n \times n$ oraz $3$ tablice długości $n$ to złożoność pamięciowa wyniesie $O(n)$.

Problem może pojawić się w przypadku odtworzenia najdłuższego wspólnego podciągu -- a przecież o to chodzi w zadaniu.

Wektor $LL$, który wypełnialiśmy w poprzedniej procedurze dla pozycji $j$ przechowuje wartość $K[1,j]$, co oznacza, że $j$ element jest długością LSC dla dwóch ciągów: $A_{1,m}$ i $B_{1,j}$.

Niech $L^{*}(i,j)$ określa wartość najdłuższego wspólnego podciągu dla ciągów $A_{i+1, n}$ i $B_{j+1,n}$.

def LSC_subs(n, m A, B, C):
    if n == 0:
        C = ""
        return
    else if m == 1:
        for i in range (1, n)
            if A[1] == B[i]:
                C == A[1]
                return
        C = ""
        return
    
    i = m/2
    
    for j in range (0,n+1):
        LCS(i, n, A[1:i], B[1:n], L1)
        LCS(m - i, n - k, A[m:i+1], B[n:1], L2)
    
    M = 0
    for j in range (0, n+1):
        if M < L1[j] + L2[n-j]
            M = L1[j] + L2[n-j]
            k = j
            
    LCS_subs(i, k, A[1:i], B[1:k], C1)
    LCS_subs(m-i, n-k, A[i+1:m], B[k+1:n], C2)
    
    return concat(C1, C2)

#### Dowód poprawności

Niech
$$
M(i) = \max_{0 \leq j \leq b}\{L(i,j) + L^{*}(i,j)\}
$$

##### Lemat

Dla każdego $0 \leq i \leq n \, \, M(i) = L(n,n)$

Dowód

Z poprawnośći algorytmu $LCS$ wiemy, że $L1[j]$ jest wartością najdłuższego podciągu między $A_{1,i}$ oraz $B_{1,j}$. Analogicznie $L2[j]$ między $A[m,i+1]$ a $B[n,n-j+1]$.

## Zadanie 5

## Zadanie 6

#### Najdłuższy wspólny podciąg zawierający podsłowo "matura"

#### Najdłuższy wspólny podciąg nie zawierający podsłowa "matura"

## Zadanie 7

## Zadanie 8

## Zadanie 9

## Zadanie 10
###### tags: `aisd`