Author |
Message |
13/08/2018 14:10:44
|
VlatkoSh
Joined: 10/08/2016 12:39:15
Messages: 48
Offline
|
Линк за задачата
Задачата бара да се направи дрво со n темиња, со дијаметар од d и секое теме може да има најмногу k степен. 1 <= n, d, k <= 400000
Сам успеав само дијаметарот да го направам. Меѓутоа, не разбирам како да ги поврзам останатите темиња. Ова е едиториалот. Во едиториалот, не можам да го разбирам третиот параграф, односно делот после правењето на првите d+1 темиња (дијаметарот). Идеи?
|
|
|
13/08/2018 20:58:06
|
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)
|
|
|
14/08/2018 09:35:18
|
VlatkoSh
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
|
|
|
14/08/2018 12:55:23
|
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.
|
|
|
14/08/2018 14:20:54
|
VlatkoSh
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
|
|
|
|