Zadanie 1

Ze wzoru Eulera wiemy, że !!\sum_{i=1}^n \frac{1}{i} \approx \log n!!, as !!n!! approaches infinity.

!! T(n) = 2T(\frac{n}{2}) + \frac{n}{\log n} = !!
!! = 2(2*T(\frac{n}{4}) + \frac{n/2}{\log \frac{n}{2}}) + \frac{n}{\log n} =!!
!! = 4T(\frac{n}{4}) + \frac{n}{\log \frac{n}{2}} + \frac{n}{\log n} =!!
!! = n \cdot 1 + \sum_{i=1}^{\log n} \frac{n}{\log 2^i} = !!
!! = n + n \sum_{i=1}^{\log n} \frac{1}{\log 2^i} = !!
!! = n + n \sum_{i=1}^{\log n} \frac{1}{i} = (euler)!!
!! = n + n \log\log(n) \approx !!
!! \approx n \log\log(n) !!

Zadanie 2

Disclaimer: w moim rozwiązaniu przechodzimy przez piekło dla strywializowania problemu (a przynajmniej piekło dla mnie, bo nie miałem rozwa :(). Co więcej, nie wiem czy przejście przez piekło nie jest grzybable.

Oczywiście zaczynamy od próby zrozumienia o co chodzi.

Kolorkami zaznaczyłem zbiory punktów (!!q!!) na trzech prostych, które są widoczne z p, ten jasnozielonkawy to !!x = 0!!. Zatem te 3 proste są widoczne z p. Teraz, w zadaniu musimy znaleźć wszystkie proste które są widoczne z punktu !!(0, +\infty)!!.

Na co musimy zwrócić uwagę?
Proste z największym i najmniejszym współczynnikiem kierunkowym na pewno będą widoczne. Teraz najważniejsza rozkmina - jakie proste jeszcze będą widoczne? Posortujmy po b. Na pewno prosta z największym będzie widoczna. Mamy takie szczypce z prostych ze skrajnymi współczynnikami kierunkowymi i prostą przechodzącą przez nie. Teraz, żeby kolejna prosta mogła być widoczna, to jej punkt przecięcia z tą prostą z największym b musi być w środku "szczypiec".

Już tłumaczę. Umieśćmy nasze proste jako punkty w układzie współrzędnym, zaznaczmy sobie te skrajne i ten z największym b. Tzn, dla prostej (y = ax + b) wstawiamy na układ współrzędnych punkt (a, b). Przeprowadźmy przez nie proste.

Każdy punkt odpowiada prostej z zadania - tzn. są to punkty dla prostych !!y = -15x - 3!!, !!y = -3x + 9!!, !!y = 15x - 2!!. Tak się one mają na wykresie (niebieski i czerwony to "szczypce"):

Rozważmy dodatkową prostą, np. !!y = 2x + 2!!.

Jak widzimy, przecinają się poza "szczypcami", nie są widoczne. Rozważmy teraz prostą !!y = 4x + 5!!.

Ledwo bo ledwo, ale przecinają się w "szczypcach", będzie widoczna.

Teraz ważna obserwacja - jak wyrazić proste, które łączą np. !!(-3, 9)!! i !!(15, -2)!!? Oczywiście obliczamy sobie prostą przechodzącą przez dwa punkty, będzie to !!y = \frac{11}{18} x + 7.1666667!!. Wyliczone współczynniki tej prostej są niczym innym jak ich punktem przecięcia. To znaczy, proste !!y = -3x + 9!! i !!y = 15x - 2!! przecinają się w punkcie !!P(\frac{11}{18}, 7.166667)!!. No i teraz nasz nowy punkt leży "nad" tą prostą, prosta będzie przechodziła pomiędzy prostymi !!(-3, 9)!! i !!(15, -2)!! nad ich punktem przecięcia, więc będzie widoczna. Troche lipnie wytłumaczone, ale nie umiem lepiej. Prosta !!(4, 5)!! będzie widoczna i updatujemy nasze proste.

Teraz, jeżeli jakaś prosta będzie pod tym pomarańczowym wykresem, to będzie się przecinała z innymi prostymi pod widocznymi prostymi, więc nie będzie widoczna. W tym momencie dochodzimy do tego o co chodziło mi na samym początku. Wykminienie i pokazanie (jak ktoś umie to pokazać dokładniej i łatwiej to błagam, powiedzcie mi) o co tu chodzi to big brain, ale samo rozwiązanie jest absolutnie trywialne. Wystarczy przedstawić nasze proste jako punkty i znaleźć ich górną otoczkę wypukłą.

Do znalezienia otoczki górnej wykorzystamy monotone chain convex hull algorithm, algos z wiki.

def find_upper_convex_hull(points):
    points = sorted(set(points))

    if len(points) <= 1:
        return points

    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    return upper


def find_visible_lines(lines):
    points = map(lambda x: (x.a, x.b), lines)
    return find_upper_convex_hull(lines)

Zadanie 3

!!k = 2!!

Dzielimy se nasz argument na pół, jak w Karatsubie. Mamy !!x = x_0 \cdot 2^\frac{n}{2} + x_1!!. Po skwadraceniu, dostajemy: !!x^2 = x_0^2 \cdot 2^n + 2 \cdot x_0 x_1 \cdot 2^\frac{n}{2} + x_1^2!!

No i teraz obserwacja: !!2 x_0 x_1 = (x_0 + x_1)^2 - x_0^2 - x_1^2!!.

Zatem !!x_0^2, x_1^2!! obliczamy rekurencyjnie, !!(x_0 + x_1)^2!! też. Mamy więc nadal 3 wywołana rekurencyjne wartości które są ~połowę mniejsze, złożoność będzie taka sama.

!!k = 3!!

Chyba chodzi o Toom-Cook. Na początku myślałem że tu złożoność będzie gorsza, także lepiej nie ufać temu podpunktowi z k = 2 też.

Zadanie 6

def DFS(curr, acc, C, res):
    if acc <= C:
        # dla każdego nieodwiezdonego sąsiada curr
        for each unvisited v: e(curr, v):
            res += DFS(v, acc + weight(curr, v), C, res)
            if (acc == C):
                res += 1
            return res
    else:
        return 0

def pairs(T, C):
    if (C == 0):
        return n

    res = 0
    for each v in T:
        res += DFS(v, 0)
    res /= 2

    return res

Dla każdego wierzchołka przechodzimy do maksymalnie !!n!! innych wierzchołków, zatem złożoność to !!O(n^2)!!.

Zadanie 8

Przykład jak tego nie robić - dostałem za to 0 na egzaminie :(

Przesunięcie cykliczne - np. mając 11101101 i przesuwając to cyklicznie o 3, dostaniemy 01101111, tj. 3 pierwsze lądują na początku, a pozostałe są przesunięte. Może lepiej będzie widać jak przesuniemy cyklicznie o 3 ciąg abcdefgh, będzie to wtedy defghabc.

Zacznijmy od przetworzenia naszych danych. Zauważmy, że np. dwa przesunięcia o 1 są równoważne jednemu przesunięciu o 2, dwa przesunięcia o 2 są równoważne jednemu przesunięciu o 4 i tak dalej. Doprowadzimy dane do postaci, gdzie będziemy mieć maks jedno przesunięcie danego rodzaju. Posortujmy nasz !!P_n!!. Dla każdych dwóch !!2^i!!, usuwamy dwa !!2^i!! ze zbioru i dodajemy jedno !!2^{i+1}!!. Mamy zbiór z przesunięciami, gdzie jest maksymalnie jedno !!2^i!! na zbiór. Przesunięcia większe bądź równe !!n!! możemy po prostu wyrzucić, jako że przesunięcie ciągu n-elementowego o n zwróci nam ten sam ciąg, a przesunięcie ciągu n-elementowego o jeszcze większą potęgę dwójki tylko powtórzy operację przesunięcia o n ileś razy. Dla prostoty, nasz zbiór możemy zwyczajnie przedstawić teraz jako !!\sqrt n !!-bitową liczbę, gdzie !!i!!-ty bit będzie mówił, czy potrzebne jest przesunięcie o !!2^i!!.

Przykład konstrukcji sieci:

Krok pierwszy, mamy 1 - zatem wymagane jest przesunięcie o 8.

Przesunięcia o 4 nie ma, przespiujemy.

Przesunięcie o 2 jest, to przesuwamy o 2.

Przesunięcie o 1 też jest, no to też przesuwamy.

I mamy nasze wyjście. Ogólniej mówiąc, budując sieć, na danym kroku, jeżeli !!P_n[i] = 1!!, to każdy element przesuwamy w lewo o !!2^i !!, bierzemy to modulo !!2^n!!, czyli elementy które przsuwane w lewo wysuwają sie za zakres, pojawiają się na początku.