Algoritmus O(n^4)

asked 2015-03-17 02:38:09 +0100

Anonymous

updated 2015-03-17 13:25:26 +0100

Anonymous

Ahojte, muze mi nekdo prosim strucne vysvetlit ten algoritmus na FindByCost?

answered 2015-03-17 16:36:30 +0100

Ondřej Máca
192 ●7 ●11 ●20

updated 2015-03-20 10:27:29 +0100

EDIT2 Nejprve je to potřeba předpočítat tak, že si pro každý obdelník spočítáš součet plochy vlevo nad ním.
image description
A = C+B-D

A pak si projdeš všechny obdélníky tím způsobem, že si každý obdélník spočítáš takto:
image description
žlutá plocha = D - C - B + A

EDIT Níže uvedené řešení není O(n^4)

generuješ obdélníky délky 1x1 až NxN
pak je posouváš do všech míst kam to jde
a pro každé posunutí sečteš prvky uvnitř obdélníku.

A ty hledáš největší obdélník, který má ten součet menší nebo roven maxCost

edit flag offensive delete publish link

Comments

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

PeterBocan ( 2015-03-17 22:54:44 +0100 )edit

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

Ondřej Máca ( 2015-03-18 00:47:08 +0100 )edit

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".

PeterBocan ( 2015-03-18 00:50:10 +0100 )edit

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

Ondřej Máca ( 2015-03-18 20:42:13 +0100 )edit

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

PeterBocan ( 2015-03-18 22:59:08 +0100 )edit

Algoritmus O(n^4)

1 Answer

Comments

Your answer

Question tools

Stats

Related questions