Makovník¶

35 úspešných riešiteľov (48 submitov)

  • 22x Python (3.68 - 9.62 s) [568-1 496 B]
  • 21x Java (0.59 - 3.19 s) [1 130-2 734 B]
  • 5x C++ (0.71 - 0.87 s) [844 - 1 656 B]

chyby¶

  • nesprávne načítanie vstupu (v poradí $n$, $k$)
  • vytvorenie poľa $dasa[x]$ pre všetky možné hodnoty (ale tých može byť až $1.999.999.999$), čo znamenalo RUN ERROR - java.lang.OutOfMemoryError: Java heap space - treba binárne vyhľadávať, pričom si priebežné výsledky nemôžeme ukladať
  • skúšať postupne vštky možné hodnoty (max $1.999.999.999$)
  • rozsah hodnôt sa zmestí do rozsahu int, ale odpoveď v druhom riadku v extrémnom prípade nemusí
  • rozsah hodnôt sa zmestí do rozsahu int, ale operácia súčet pri binárnom vyhľadávaní už pretečie a výsledkom je WRONG ANSWER
    int lavy = 1999999998, pravy=1999999999;
System.out.println((lavy+pravy)/2); 
//vysledok je -147483649

chyby 2¶

  • nesprávny predpoklad, že makovníky sú na vstupe usporiadané
  • binárne vyhľadávanie funguje, ak na začiatku máme dva rôzne výsledky, teda dá sa pre $\text{velkost}= 0$ a nedá sa pre $\text{velkost}=1+\min\left(\max\left(p_i\right), \left\lfloor\frac{ \sum\limits_{i=1}^{k}p_i }{k}\right\rfloor \right)$
  • žiadny výstup NO OUTPUT v okrajovom prípade $n = 1$
  • chyba v prípade, ak je výsledkom $0$
  • v poli hľadáme prvé číslo $\ge k$ (nie rovné)
  • práca s reálnymi číslami (int(x/2) namiesto x//2)
  • zostávajúpci zvyšok nie je súčet celočíselných zvyškov jednotlivých makovníkov (nie z každého sa musí odkrojiť)

Mestá - hra s pohybom o 1-3 políčka¶

Predstavme si jednorozmernú hraciu plochu. Prvé (ľavé) políčko je štartovacie, posledné (pravé) cieľové. Ostatné políčka reprezentujú rôzne mestá a obahujú číselný údaj - mýto za prechod mestom. V jednom ťahu sa hráč pohybuje o 1 až tri políčka (hádže sa kockou, kde sú hodnoty 1, 2, 3 dva krát).

Akú minimálnu sumu je možné dosiahnuť pri uvedenej hre, presun zo štartovacieho do cieľového políčka?

Mýto v meste - príklad¶

hody 0 1 2 3 4 5 6 7 Suma
Š 9 5 3 5 9 2 C
3,3,1 * - - * - - * * 5
2,2,3 * - * - * - - * 10
In [2]:
myto = [0, 9, 5, 3, 5, 9, 2, 0]

Pažravý prístup (Greedy)¶

  • hypotéza: skákať čo najviac
hody 0 1 2 3 4 5 6 7 Suma
Š 9 5 9 5 9 2 C
3,3,1 * - - * - - * * 11
2,2,3 * - * - * - - * 10
  • hypotéza: z možných skokov vyberieme ten, kde je najmešie mýto
hody 0 1 2 3 4 5 6 7 Suma
Š 9 3 5 5 9 2 C
2,2,3 * - * - * - - * 8
3,3,1 * - - * - - * * 7

Simulácia všetkých možností¶

In [30]:
myto = [0, 9, 5, 3, 5, 9, 2, 0]

def sim(pozicia, suma): #som na pozicii a doteraz som zaplatil sumu (vratane pozicie kde som)
    if pozicia == len(myto)-1:
        print(suma) #nasli sme riesenie
        return
    for skok in range(1, min(4, len(myto)-pozicia)):
        sim(pozicia+skok, suma+myto[pozicia+skok]) #zaplatime myto na policku kde skaceme
    

sim(0, 0) #zaciname na lavom policku a neplatili sme zatial nic

33
31
24
22
28
26
19
30
28
21
19
25
23
28
26
19
17
23
21
14
25
23
16
14
24
22
15
13
19
17
10
21
19
12
10
16
14
19
17
10
8
14
12
5

image.png

Celkovo ide o 96 volaní sim a nájde sa 44 spôsobov ako rôzne skákať zo štaru do cieľa.

Memoizácia (memoization)¶

aka Dynamické programovanie zhora nadol

In [10]:
myto = [0, 9, 5, 3, 5, 9, 2, 0]
MEM = [None]*len(myto) #Medzivysledky ... None/-1 znamena ze sme nepocitali
MEM[:4] = myto[:4]

def memo(pozicia):
    #ak sme este nepocitali, tak vypocitaj a zapamataj si  
    if MEM[pozicia] is None:
        MEM[pozicia] = myto[pozicia]+min(memo(pozicia-1), memo(pozicia-2), memo(pozicia-3)) 
    return MEM[pozicia]
  
print(MEM)
print(memo(len(myto)-1)) #posledne, cielove policko
print(MEM)

[0, 9, 5, 3, None, None, None, None]
5
[0, 9, 5, 3, 8, 12, 5, 5]
In [12]:
myto = [0, 9, 5, 3, 5, 9, 2, 0]
MEM = [myto[i] if i < 4 else None for i in range(len(myto))] #Medzivysledky ... None/-1 znamena ze sme nepocitali

def memo(pozicia):
    #ak sme este nepocitali, tak vypocitaj a zapamataj si  
    if MEM[pozicia] is None:
        MEM[pozicia] = myto[pozicia]+min([memo(pozicia-skok) for skok in range(1, 4)]) 
    return MEM[pozicia]
  
print(MEM)
print(memo(len(myto)-1)) #posledne, cielove policko
print(MEM)

[0, 9, 5, 3, None, None, None, None]
5
[0, 9, 5, 3, 8, 12, 5, 5]

Memoizácia v Pythone pomocou dekorátora¶

In [13]:
from random import randrange

myto = [0]+[randrange(0,100) for i in range(28)]+[0]
print(*myto)

0 4 30 16 12 5 24 45 3 51 20 95 0 7 73 5 69 47 60 37 36 91 11 73 82 20 84 52 80 0
In [14]:
%%time

##rekurzivna funkcia
def memo(index):
    if index < 4:
        return myto[index]
    return myto[index] + min(memo(index - i) for i in range(1, 4))

memo(len(myto) - 1)

Wall time: 11.8 s
Out[14]:
215

https://docs.python.org/3/library/functools.html#functools.cache

In [2]:
%%time
from functools import cache

#zapnuta memoizacia
@cache
def memoCache(index):
    if index < 4:
        return myto[index]
    return myto[index] + min(memoCache(index - i) for i in range(1, 4))

memoCache(len(myto) - 1)

CPU times: total: 0 ns
Wall time: 0 ns
Out[2]:
215
In [ ]:
Iba od verzie Python 3.9

https://docs.python.org/3/library/functools.html#functools.lru_cache

In [15]:
%%time
from functools import lru_cache

#zapnuta memoizacia
@lru_cache(maxsize=None)
def memoLRU(index):
    if index < 4:
        return myto[index]
    return myto[index] + min(memoLRU(index - i) for i in range(1, 4))

memoLRU(len(myto) - 1)

Wall time: 995 µs
Out[15]:
215

Dynamické programovanie (zdola nahor)¶

  • prelínajúce sa podproblémy
  • výpočet z už vypočítaných medzivýsledkov, teda z hodnôt poľa, bez rekurzie ("magický" vzorec [PAZ1b])
In [17]:
OPT = [myto[i] if i < 4 else None for i in range(len(myto))]

for i in range(4, len(myto)):
    #magicky vzorec na vypocet i-tej hodnoty
    OPT[i] = myto[i]+min(OPT[i-hod] for hod in range(1,4))

print(OPT[-1])

215

$T(n)=O(n)$

  • LIS (Longest Increasing Subsequence)
  • LCS (Longest Common Subsequence)

Fibonacciho čísla¶

https://en.wikipedia.org/wiki/Fibonacci_number

http://oeis.org/A000045/

    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
In [21]:
%%time 
def fib_rek(n):
    if n < 2:
        return n
    return fib_rek(n-1)+fib_rek(n-2)

fib_rek(40)

Wall time: 55.6 s
Out[21]:
102334155

$ T(n) = T(n-1)+T(n-2)+1 $

$x^2=x+1$, $x^2-x-1=0$

$T(n)=\phi^n$, kde $\phi$ je zlatý rez

$\phi = \frac{1+\sqrt{5}}{2} = 1.618$

image-2.png

$\frac{a+b}{a}=\frac{a}{b}=\phi$

image-3.png

Majk Spirit - Primetime (Official Video)

https://www.youtube.com/watch?v=rruOu2nIPHc

Lyrics

https://www.youtube.com/watch?v=gPeTTOvKB_E
A trpezlivo staral sa oň ho kým stal sa veľkým,
Bol mu všetkým, takže bol občas ničím,
Ale to musí. Či sa ti to páčí má to
Postupnosť jak Fibonacci
Primetime!
Život bez umenia- hlúposť, na čo je tvor čo netvorí,
Kto klope tomu sa otvorí jak hovorí múdra kniha,
Inteligentný rapper alias moja Odysea,
Rap moja profesia, zlatý rez 1, 6 moje mystérium
In [24]:
%%time
def fib_dp(n):
    F = [ i if i < 2 else None for i in range(n+1)]
    for i in range(2, n+1):
        F[i] = F[i-1]+F[i-2]  #! O(n) bitov
    return F[-1]

fib_dp(1000)

Wall time: 999 µs
Out[24]:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Fibonacciho čísla rastú rýchlo¶

image-2.png

n.-té Fibonacciho číslo má približne n bitov, teda nevojde do štandardnej premenej long. Sčítanie teda nie je jednoduchá operácia a netrvá $O(1)$, ale až $O(n)$.

Algoritmus "Časová" zložitosť Skutočná časová zložitosť
rekurzia $O(\phi^n)$ $$T(n)=T(n-1)+T(n-2)+n$$, $$T(n)\in O(\phi^n)$$
dynamické programovanie $O(n)$ $$O(n^2)$$
In [29]:
#lepsia pamatova zlozitost O(1)
def fib_pz(n):
    a, b = 0, 1
    for i in range(n-1):
        a, b = b, a+b #Python vyhodnoti vypocty vpravo a potom zapise
    return b
    
fib_pz(40)
Out[29]:
102334155

image-2.png

Najrýchlejší spôsob výpočtu $n$-tého Fibonacciho čísla je cez mocninu matice

Algoritmus "Časová" zložitosť Skutočná časová zložitosť
rekurzia $O(\phi^n)$ $$T(n)=T(n-1)+T(n-2)+n$$, $$T(n)\in O(\phi^n)$$
dynamické programovanie $O(n)$ $$O(n^2)$$
rýchle umocňovanie $O(\log n)$ $$T(n)=T(n/2)+O(n \log n)$$, $$T(n) \in O(n \cdot \log n)$$

Vstupom je číslom $n$, teda veľkosť vstupu je $v = \Theta(\log n)$, zložitosť $O(n^2)$, to je $2^{2*v}$ ako funkcia veľkosti vstupu $v$.

Tento algoritmus je pseudopolynomiálny ... pre číslo $n$ na vstupe je časová zložitosť $T(n) \subset O(n^k)$.

Reťazové násobenie matíc (DP)¶

Máme dané rozmery $n$ matíc. Koľko najmenej násobení je potrebné urobiť, aby sme vypočítali výsledný súčin $A_1 \cdot A_2 \cdots A_n $. Rozmery označme $D[i], i=0,\dots,n$, teda matica $A_i$ má rozmery $D[i-1] \times D[i]$.

Násobenie dvoch matíc $A \cdot B = C$. Rozmery matíc $A...a \times b, B ... b \times c, C ... a \times c$. Prvok výslednej matice je skalárny súčin riadku prvej a stĺpca druhej matice

$$ c_{ij} = \sum_{k=1}^{b} a_{ik} \cdot b_{kj}$$

$\Theta(a \cdot c \cdot b)$ - pre všetky prvky výslednej matice musíme vypočítať danú sumu.

3
10 30 5 60

$A_1 \cdot A_2 \cdot A_3 = (A_1 \cdot A_2) \cdot A_3 = A_1 \cdot (A_2 \cdot A_3)$

$(A_1 \cdot A_2) \cdot A_3$:

prvým násobením vznikne matica $10 \times 5$ s použitím $10*30*5=1500$ násobení

dalším násobením vznikne matica $10 \times 60$ s použitím $10*5*60=3000$ násobení

$A_1 \cdot (A_2 \cdot A_3)$:

prvým násobením vznikne matica $30 \times 60$ s použitím $30*5*60=9000$ násobení

dalším násobením vznikne matica $10 \times 60$ s použitím $10*30*60=18000$ násobení

V závislosti od poradia násobenia vykonáme buď 4500 alebo 27000 násobení.

$A_1 \cdot A_2 \cdot A_3 \cdot A_4$

$(A_1 \cdot A_2) \cdot (A_3 \cdot A_4)$

$((A_1 \cdot A_2) \cdot A_3) \cdot A_4$

$A_1 \cdot (A_2 \cdot (A_3 \cdot A_4))$

$(A_1 \cdot (A_2 \cdot A_3)) \cdot A_4$

$A_1 \cdot ((A_2 \cdot A_3) \cdot A_4)$

Koľko máme možností na ozátvorkovanie pre 5 matíc?

Koľko máme možností na ozátvorkovanie pre n matíc?

Vieme využiť dynamické programovanie, teda násobenie menšieho počtu matíc ?