[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Messages posted by: VlatkoSh
Forum Index » Profile for VlatkoSh » Messages posted by VlatkoSh
Author Message
despotovski01 wrote:
Нека N се парите што ги имаме, и нека имаме 2 градови опишани со вредностите P1 R1 и P2 R2 и нека важи дека R1 > R2. Да претпоставиме дека ...


Fala za objasnuvanjeto, nema podobro od dokaz!
Vo dobra nasoka si so toa sto probuvas da go konstruiras brojot na "greedy nacin". Moeto resenie na povrsinata izgleda dosta slicno so tvoeto, ama tvoeto resenie ima nekakvi propusti vo toa kako go konstruiruva brojot. Ti preporacuvam da pocnes od novo, odnosno probaj da go napises toa sto go imas vo glava na drug nacin, bidejki si vo dobra nasoka.
longhi wrote:
Но, по кој редослед да ги поминуваме градовите? Од кога ќе ни текне дека единствениот начин да добиеме пари е од организацијата на митинг (инаку само трошиме), тогаш може да забележиме дека е најдобро да ги сортираме во опаѓачки редослед според R[x].


Ne razbiram zosto gi sortiruvas po R[x] a ne po P[x]?
Gresna ti e postapkata... tvojot kod bi napravil 2^n operacii, a n <= 36. 2^36 e ogromen broj.

Razgledaj za Meet In The Middle.
Da.
Mislam deka treba da se znae sto se bitmaski i osnovni bitni manipulacii za da mozes da ja resis zadacava. Eve ti link ako ne znaes sto se.

Koga ke znaes sto se tie, zadacata e relativno lesna.

Zapisi gi prvite nekolku "srekni" broevi:



Seka napisi gi prvite nekolku broevi i nivnite binarni reprezentacii:



Probaj da gi povrzes nekako.
Ja resiv posle 4 meseci Treba BFS i da se najde nacin voopsto da ne se razgledaat polinjata sto znaeme deka sme gi dodale vekje.
Ne mozam da razberam sto sakas da napravis, ni vo tekstot ni vo kodot. Ako uspees da go resis na tvojot nacin, super, ama ne znam zosto nekoj bi se macel da ti bara popravka vo kodot?
Jas go resiv vaka (vo slucajot deka ne moze direktno da se stigne od Sase do Elena):

0) Pustas BFS od Sase, a potoa BFS od Elena. Dvete se na istata dist matrica. Isto taka sakame da znaeme dali nekoe pole e na "stranata na Sase" ili na "stranata na Elena". Ova moze da go napravis ako koristis nekoja druga matrica i stavas na primer sign[r][c] = 'S' ili sign[r][c] = 'E' za vreme na BFSto.

1) Odi kaj sekoe pole sto e baricka. Neka koordinatite se r i c. Sakame da vidime dali ako go izbriseme ova pole ke moze da se stigne od Sase do Elena. Ako moze, sakame da go najdeme najdolgiot pat za toa. Ovoj broj e odgovorot za zadacata. Neka se vika ovoj broj ans. Na pocetok ans = 0.

2) Probaj gi site mozni parovi na sosedni polinja (na pr. (r-1, c) i (r+1, c) za toa nad i pod, ili pak (r-1, c) i (r, c+1) za toa nad i toa desno, i slicno). Na primer neka gi probuvame (r1, c1) = (r-1, c) i (r2, c2) = (r+1, c). Togas ako ovie koordinati ne se baricka, i ako ednoto bilo stignato od Sase, a drugoto od Elena, pravime ans = max(ans, dist[r1][c1] + 1 + dist[r2][c2]). (edinicata vo sredina e deka go pominuvame samoto pole (r, c))
Da, najverojatno toa e. Dali ima nekoj drug nacin da se implementira dinamicko? (deka toa go rece MOI) Ili dali moze da se resi na drug nacin? Nemam ideja vekje.
Probav dinamicko ama dobiva Runtime Error na povekje testovi (izgleda bara premnogu memorija?): https://pastebin.com/S4TG5782
Isto taka probav Meet In The Middle, sto e pobrzo ama dobiva Runtime Error na istite testovi: https://pastebin.com/34V0q9GH
Moze da mi pomogne nekoj?
Eve ti go relevantniot del od kodot:
Pretpostavuvam deka ne mora nesto kako BigInt da se koristi?
Dodeka ja procesiras matricata, dodaj gi koordinatite na sekoj zatvorenik vo queue. Potoa pravis normalno bfs, ama namestno od eden izvor (pocetna pozicija), od poveke izvori istovremeno. Nesto vaka:




Taka ke bide isto brzo kako da bi bilo od eden izvor, (kako sto ti planirase da pravis za sekoj zatvorenik). Inaku na dobar pat si.
 
Forum Index » Profile for VlatkoSh » Messages posted by VlatkoSh
Go to:   
Powered by JForum 2.1.8 © JForum Team