b Da li mogu da dobijem neko resenje za ovaj zadatak?Predugo se mucim da ga uradim.Evo ga moj kod koji na svim test primerima ima vremensko prekoracenje:
Edite by boba5551
Pokusaj da opises ideju, a ne da postujes kod. Prva stvar je kao sto ti je Relja rekao - tesko da ce neko drugi naci tvoju gresku ako sam nisi, a drugo je sto neko moze da se navodi tvojim kodom, a to nema potrebe. Oni koji su ga uradili mogu da vide tvoj kod na z-treningu, tako da stvarno nemas potrebe da postujes kod, niti bilo ko drugi.
Ono sto sam ne mozes da nadjes u svom kodu, tesko da ce neko drugi..
No, evo ti jedne ideje :
Znaci ubacas u stack polja koja trebaju da se otope ( dakle, otapas polja redom, kako im dodje vreme ).
I tako znas kada ce koje polje biti otopljeno..
Posle samo nadjes put od jednog do drugog labuda na kome
je najvece vreme topljenja nekog polja minimalno..
Ubacim u stack? Zar nije u red (queue), kao BFS?
Znaci, izracunam matricu u kojoj mi polje (i,j) govori nakon koliko dana ce se otipiti led na toj poziciji.
E, kada pronalazim taj put od jednog labuda do drugog, ja koristim priority_queue< prioritet, pair<x,y> > i nad time vrsim BFS, pri cemu stajem kada naletim na polje na kojem je drugi labud.
Ovo trosi puno memorije i u nekim slucajevima daje pogresno resenje. Koja je efikasnija metoda za racunanje ovog puta?
Radi mi na sve test primjere ali izvan vremena i previse memorije. Znaci, pamtim polja, polja koja se tope danas, i posjecena polja. To sve radim dok ne nadjem put izmedju labudova. Ima tko ideju kako ubrzati i smanjiti memoriju ?
Kod:
http://www.z-trening.com/new/www/html/submit.php?submit=7100007438&subm_code=1
Sto se tice brzine, evo ti na primer:
1) izbaci cin, koristi scanf
2) nemoj koristiti vektore, koristi nizove za queue. Znas da ti queue nece imati vise od 1500*1500 polja, pa rezervisi niz te duzine (ili pravi dinamicki listu, mada nema potrebe) i to ce ti ubrzati ceo alg.
3) jesi li siguran da ti za polje i bil treba 1610*1610, a ne 1510*1510 ili slicno?
to 1610x1610 sam stavio samo kod par njih jer sam nesto isprobavao, uglavnom, sada je samo na 12. i 14. previše memorije ali i dalje je vrijeme predugo
Ja bih ti predlozio i da izbacis pair i set ako ti bas ne treba, a moze to i bez toga. Recimo, umesto pair mozes da imas dva niza. Takodje ona jedna bool matrica sigurno moze da se zameni sa nekom vrednosti u char matrici, recimo 255 i na taj nacin mozes da smanjis jednu matricu. Te stvari bi trebalo da rode plodom, zapravo sigurno ce ako ih sredis kako treba.
Imam cudan problem kod ovog zadatka.
Naime, puca na svim primerima, ispise time limit.
Medjutim, ako smanjim velicine nizova onda radi za par primera, a ne radi za one za koje mu treba veci niz. Program kod mene zauzima oko 8mb, tako da bi trebalo da radi bez problema, da li neko ima ideju kako da otklonim problem?
To te Z-trening laze :D. I meni je to bilo problem na jednoj dinamici. Uporno sve puca na vremenu -.- I onda skuzio da imam jednu nulu previse u deklariranju polja :)
Ma da, za 0.001s izbaci na svih 10 time limit.... a ne zauzimam vise od 16mb.....
