[ Goran Rakić @ 30.11.2002. 21:32 ] @
Danas sam gledao ovaj zadatak, "razbijao" glavu i nemam uopšte ideju. Da napomenem, zadatak nije niti za ocenu, niti za školu, niti ja imam rok do kada trebam da ga uradim. Čista razonoda. Siguran sam da nije težak, ali...

Naime, data je kvadratna matrica (dvodimenzionalan niz) n x n (n kolona i n redova). Treba naći koordinate početka i kraja glavne dijagonale podmatrice (ne mora biti kvadratna) koja ima najveću sumu elemenata. Svi elementi su celi brojevi, u rasponu od -100000 do 100000, a n je manje ili jednako 60. Znači za matricu:

Code:

  1   1   1   0  -50
  1  -9   1   0    0
  1   2   1   1    1
  0   0   1   8    1
 -50  0   1   1    1


treba pronaći 3 2 5 5, jer je najveća vrednost zbira elemenata u podmatrici čija glavna dijagonala počinje u preseku 3 reda i 2 kolone (broj 2), a završava u preseku 5 reda i 5 kolone (broj 1).

U principu, u ekstremnom slučaju, da su svi elementi pozitivni, najveća podmatrica bi bila sama matrica. Kako je n veliko (max 60) samo izračunavanje svih kombinacija ne dolazi u obzir. Onda sam razmišljao da počnem od matrice označene sa 1 1 2 2 (ako uzmemo da matrica počinje sa index-om 1) pa onda izračunam matricu 1 1 2 3 i tako dalje, ali sam se pogubio kada sam uzeo da n može da bude i neparno, a opet mi se čini mnogo "prolaza".

Onda sam najviše razmišljao o ideji da iz svakog koraka u sledeći mogu na 8 različitih načina. ("smaknem" prvi red, zadnji red, prvu ili zadnju kolonu, kao i kombinacije prvi red i prva kolona, prva kolona i zadnji red, zadnji red i druga kolona, druga kolona i prvi red) Stoga mogu "probati" tih 8 vrednosti na osnovu pozicije gl. dijagonale trenutne podmatrice i odabrati najmanju, jer njenim eliminisanjem dobijam naveću preostalu vrednost. Mana toga je što ako u prvom koraku odem na 3 izbor (druga kolona) onda možda neću ni stići do neke kombinacije u kojoj sam trebao sačuvati tu treću kolonu. (ala sam ovo objasnio, ali nadam se da kapirate).

Da sortiram matricu ne mogu, jer mi trebaju koordinate.

Imate li neke ideje?
[ Dragoslav Krunić @ 30.11.2002. 23:38 ] @
Zaista interesantan i na prvi pogled lak zadatak. Baš ću da pokušam. Očekujte rešenje u Perlu, a posle je lako to prebaciti u drugi programski jezik ako je potrebno...
[ dRock9 @ 04.12.2002. 11:30 ] @
Prvo, ako moze jedna mala ispravka : Matrica koja nije kvadratna NEMA dijagonalu (ni glavnu ni sporednu).....

Drugo: Ovaj tvoj problem spada u kategorijiu poznatih problema koji se resvavaju tehnikom, tzv. dinamickog programiranja (nema veze sa dinamickim strukturama - listama, drvetima i ostalo). Potrudicu se da iskucam resenje pa cu tada da post-ujem i vise objasnjenja, a ti si deo ideje (koju doduse treba doterati, malko) vec dao - ono sa vrstama i kolonama, dodavanje i oduzimanje - sta vise mislim da je slican (ako ne i isti) problem postavljen na nekom takmicenju ranije....

pozdrav, ocekuj source uskoro (Perl ne znam, ali potrudicu se da to bude citljiv C kod...)
[ Goran Rakić @ 04.12.2002. 13:28 ] @
Da bio je 1998. godine na regionalnom, a bio je sličan i u Makedoniji na republickom *97. godine, ali rešenje nigde ne mogu da nađem. Rešenje znam i ja da je tehnikom dinamičkog programiranja, ali ne mogu da pronađem kako tačno. Očekujem source. ;)
[ Rapaic Rajko @ 06.12.2002. 10:27 ] @
Sjajan post (mislim na opis algoritma); toliko dobar da je nasao mesto u mojoj kolekciji dragulja.
Inace, zivo me zanima kako si zamislio optimizaciju. Ja vec vidim neki put ka brzem racunanju Item-a pomocne matrice: tu se stalno sabiraju jedne te iste vrednosti...hm, hm, hm...nesto mi se kuva...
Pozdrav

Rajko
[ Ivan Dimkovic @ 06.12.2002. 10:50 ] @
Ahh

Ja se izvinjavam - slucajno sam obrisao poruku umesto da skinem .zip file

Zamolio bih autora algoritma da ponovo postuje algo :(((((((


Izvinjavam se again!!!

[ Goran Rakić @ 06.12.2002. 14:25 ] @
hoćeš da kažeš da je ovde bilo rešenje???? NEE" for(i=0;i<10;i++) printf("E"); "!!! ;)
[ dRock9 @ 07.12.2002. 19:20 ] @
Ok, nema problema evo algoritama.

matrica.zip je onaj stari, a optimizovano.zip je ova nova ideja (u stvari slicna je kao stara, ali je izbaceno secenje)..
Analiza slozenosti:
algoritam 1: O(n^4)
algoritam 2: O(n^3) (Worst Case: O(n^4))

pojasnjenje algoritama (detaljno) saljem uskoro - ako je nekom potrebno.
Nisam bas stigao da testiram, javite ako vidite greske.
Kao sto sam rekao prosli put - ANSI C - kompajlirajte u cemu god hocete, a imate i exe ....

poz !
[ dRock9 @ 07.12.2002. 19:23 ] @
1 fajl, 25 K, xmmm

evo i drugog
[ dRock9 @ 07.12.2002. 23:04 ] @
Posto sam zakasnio na bus za Kragujevac, otkucao sam obecano pojasnjenje.

Da ne bih kopirao zakacicu TXT uz poruku...

Rapaic Rajko: Nisam siguran kako bi se moglo optimizovati racunanje matrice vise od ovog. Ako imas neku ideju reci, mada mora se proci n^2 puta da bi se sracunala cela matrica.... Da ne bude zabune ovaj odgovor se odnosi na post sa predlogom za optimizaciju.

oxo, vidim da je limit za attachment povecan na 45k - pohvalno...

Pozdrav