[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
1003E. Tree Constructing на Codeforces  XML
Forum Index » Други задачи
Author Message
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

Линк за задачата

Задачата бара да се направи дрво со n темиња, со дијаметар од d и секое теме може да има најмногу k степен. 1 <= n, d, k <= 400000
Сам успеав само дијаметарот да го направам. Меѓутоа, не разбирам како да ги поврзам останатите темиња. Ова е едиториалот. Во едиториалот, не можам да го разбирам третиот параграф, односно делот после правењето на првите d+1 темиња (дијаметарот). Идеи?
petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

Kakvi editoriali ima na Codeforces, ova i ne e tolku loso.

Inaku, toj e najgolemiot paragraf, pa neznam za shto konkretno treba pomosh. Ona shto ne e bash najdobro objasneto e dobro i ednostavno implementirano vo dadenoto reshenie (vednash do tutorialot).
Mozhebi samo ne objasnile deka strukturata za shto zboruvaat e implementirana so set<pair<int, int>> q; (vo reshenieto)
bidejki set e binarno drvo, pa ona shto se dobiva so q.begin() e najmaliot element (koga imame parovi, prvo se gleda par->first pa par->second)
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

petarsor wrote:Kakvi editoriali ima na Codeforces, ova i ne e tolku loso.
Inaku, toj e najgolemiot paragraf, pa neznam za shto konkretno treba pomosh.


Vo pravo si, trebase podobro da objasnam. Ne razbiram sto saka da kaze vo boldiranoto:


Also let's keep all free vertices forming the diameter in some data structure which allows us to take the vertex with the minimum maximal distance to any other vertex and remove such vertices. It can be done by, for example, set of pairs (distv,v), where distv is a maximum distance from the vertex v to any other vertex. Now let's add all vertices from starting from the vertex d+1(0-indexed) to the vertex n−1, let the current vertex be u. We get the vertex with the minimum maximal distance to any other vertex, let it be v. Now we increase the degree of vertices u and v, add the edge between they, and if v still be free, return it to the data structure, otherwise remove it. The same with the vertex u (it is obvious that its maximal distance to any other vertex will be equals distv+1).


Minimum maximal distance? Od kade go dobiva ova? Prespostavuvam deka so ova se obiduva da go napravi drvoto taka sto nema pateka megu koi bilo 2 teminja podolga od d, ama ne razbiram kako.

This message was edited 2 times. Last update was at 14/08/2018 09:37:17

petarsor



Joined: 15/07/2018 11:58:27
Messages: 87
Offline

VlatkoSh wrote:Minimum maximal distance? Od kade go dobiva ova? Prespostavuvam deka so ova se obiduva da go napravi drvoto taka sto nema pateka megu koi bilo 2 teminja podolga od d, ama ne razbiram kako.

Da go minimizirame maksimalnoto rastojanie - koristejki greedy algoritam - za da pravime pateki, a da ne napravime pateku podolga od "d". Koga imame greedy, za da ne pishuvame komplicirani dokazi, najednostavno e da se ubedime vo tocnosta na algoritamot preku kontradikcija ("Zoshto da ne dodademe vrska od najmaliot element, a da se dodade od nekoj drug element ... itn?", dali ima kontra sluchaj, ...)
Barem mene mi e taka najlesno i najbrzo.
VlatkoSh


[Avatar]

Joined: 10/08/2016 12:39:15
Messages: 48
Offline

Ok, ja razbrav i ja resiv. Fala mn! Inaku, prv pat srekjavam zadaca vo koja treba da se /izgradi/ graf, mnogu interesno
 
Forum Index » Други задачи
Go to:   
Powered by JForum 2.1.8 © JForum Team