Algoritmus O(n^4)

Predpočítavaš si niečo, či len to "na sprosťáka" prejdeš?

za b) :D myslíš, že to nebude n^4? Sekvenčním testem mi to prošlo..

No ja sa len pýtam, pretože to je n^4 a urobiť sumu z podmatice je n^2 tak nejako mi to nejde do hlavy, rozmýšľal som na Summed Area Table, ale obávam sa, že by to bolo zase "too much".

dneska jsem se na cvičení dozvěděl, že to skutečně n^4 není. Je na to prý potřeba algoritmus z PA1

Tak závisí, čo tým mysleli, že to v skutočnosti nie je n^4.

no zkrátka, dělal jsem to tím nejnajivnějším algoritmem jakým to snad jde a o něm říkali, že má složitost myslím n^6. Ukazovali tam neco jako, ze si budes pamatovat sumu v levo nahore nad danym bodem. Ale do detailu to nevim. Ale nasel jsem dobrej navod na findByCrime http://kam.mff.cuni.cz/~kuba/ka/jak_zrychlovat.pdf část 1.5 Spokojil jsem se s tím řešením n^3 a i tak mám ve speedtestu mnohem lepší časy než ref. Asi to bude tim, ze je to sice O(n^3) ale pokud budou matice nahodne, tak bude prumerna slozitost n^2