the chat about WC2018 Task1
Remark: All the time is UTC+8. | |
Etaoin Wu, [13.03.18 08:24] | |
subtask 1: a path, so the answer is the sum of all edge weights | |
Etaoin Wu, [13.03.18 08:25] | |
subtask 2: one same tree repeating 3 times, equal to 3 * the distance, calculating the distance is O(n) | |
Etaoin Wu, [13.03.18 08:26] | |
subtack 3: a tree and a path, dis(a,b)=dep(a)+dep(b)-2 dep(LCA(a,b))+abs(L(a)-L(b)) | |
Etaoin Wu, [13.03.18 08:26] | |
where L is the position in path(with weight) and dep() is the depth on that tree | |
Etaoin Wu, [13.03.18 08:28] | |
enumerate p=LCA(a,b), we are maximazing dep(a)+dep(b)+abs(L(a)-L(b)) where a, b in different subtrees of sons of p | |
Etaoin Wu, [13.03.18 08:30] | |
we do a DP on tree and calculate the 1st and 2nd maximal f(x)=dep(x)+L(x) and g(x)=dep(x)-L(x) | |
Etaoin Wu, [13.03.18 08:31] | |
to calculate answer, choose one f() and one g() to update the answer | |
Etaoin Wu, [13.03.18 08:32] | |
thus subtask 3 can be solved in O(n) time | |
Etaoin Wu, [13.03.18 14:40] | |
subtask 4: two trees. | |
Etaoin Wu, [13.03.18 14:41] | |
enumerate p=LCA(a,b), we are maximazing dep(a)+dep(b)+dis2(a,b)-2*dep(p) where a, b in different subtrees of sons of p, dep() is depth on the first tree, dis2(,) is distance on the second tree | |
Etaoin Wu, [13.03.18 14:42] | |
same as last subtask, dep(p) is useless | |
Etaoin Wu, [13.03.18 14:43] | |
and we need to put the effect from the first tree (which means dep(x)) on the second tree | |
Etaoin Wu, [13.03.18 14:44] | |
then we can find a way: for any node on second tree x, create a new node x' which have only one edge from x' to x. Its length is dep(x). | |
Etaoin Wu, [13.03.18 14:44] | |
so the problem is converted to this: mainlain some sets on a tree(converted second tree) | |
Etaoin Wu, [13.03.18 14:45] | |
which supports merging two sets C=merge(A,B) and query the maximal distance Dis2(A,B) which means "max{a in A, b in B} dis2(a,b)" | |
Martin, [13.03.18 14:46] | |
But doesn't dep(p) matter in the second tree? lca(a,b) in the first tree != lca(a,b) in the second tree | |
Etaoin Wu, [13.03.18 14:47] | |
we enumerate p right? | |
Etaoin Wu, [13.03.18 14:47] | |
[Reply to Etaoin Wu] | |
LCA(,) is the lca on the first tree | |
Martin, [13.03.18 14:48] | |
Yeah but when you do a DSU on tree in the second tree, don't you fix the LCA in the second tree too? | |
Martin, [13.03.18 14:48] | |
Or are the sets arbitrarily merged? | |
Etaoin Wu, [13.03.18 14:49] | |
we dont need DSU to keep the sets | |
Martin, [13.03.18 14:49] | |
I mean the small-to-large technique, whatever it's called | |
Etaoin Wu, [13.03.18 14:50] | |
we dont need it | |
Etaoin Wu, [13.03.18 14:50] | |
we can easily find a result: for a graph whose every edge length >= 0, a maximal distance over two sets A and B must be obtained by the endpoints of diameter of A and B | |
Etaoin Wu, [13.03.18 14:51] | |
so for any set we just need to maintain its endpoints of diameter | |
Etaoin Wu, [13.03.18 14:52] | |
using DSU on tree (or small-to-large technique) will cause a slow algorithm | |
Martin, [13.03.18 14:52] | |
I get it, okay | |
Etaoin Wu, [13.03.18 14:52] | |
so we get an O(nlogn) algorithm right? | |
Etaoin Wu, [13.03.18 14:52] | |
O(logn) for any dis2(,) query | |
Etaoin Wu, [13.03.18 14:53] | |
which any merge() over sets of tree2 will call dis(,) 4 times | |
Martin, [13.03.18 14:54] | |
How do you merge(a,b) quickly? | |
Etaoin Wu, [13.03.18 14:54] | |
Note that a set only storages endpoints of its diameter, let's call it (L,R) | |
Etaoin Wu, [13.03.18 14:55] | |
so merge(A,B) = longest of {dis(A.L,A.R), dis(B.L,B.R), dis(A.L,B.L), dis(A.R,B.R), dis(A.L, B.R), dis(A.R, B.L)} which dis(,) means on 2nd tree | |
Martin, [13.03.18 14:57] | |
Ohh, right | |
Etaoin Wu, [13.03.18 14:57] | |
so we finished subtask 4: tree+tree? | |
Etaoin Wu, [13.03.18 14:57] | |
any question? | |
Martin, [13.03.18 14:58] | |
No | |
Etaoin Wu, [13.03.18 14:58] | |
[Reply to Etaoin Wu] | |
actually dis2(,) can be solved by faster lca2(,) which can be optimized to O(1) per query using RMQ structure (ST table) | |
Etaoin Wu, [13.03.18 15:01] | |
subtask 5. tree + path + path | |
Etaoin Wu, [13.03.18 15:01] | |
lets call the tree 1st and call the paths 2nd and 3rd | |
Etaoin Wu, [13.03.18 15:02] | |
enumerate p=LCA(a,b), we are maximazing dep(a)+dep(b)+abs(L2(a)-L2(b))+abs(L3(a)-L3(b))-2*dep(p) | |
Etaoin Wu, [13.03.18 15:05] | |
for any subtree we maintain f11(x)=maximal(dep(a)+L2(a)+L3(a)), f12(x)=maximal(dep(a)+L2(a)-L3(a)), f21(x)=maximal(dep(a)-L2(a)+L3(a)), f22(x)=maximal(dep(a)-L2(a)-L3(a)), and the answer can be updated using 2*2*2*2 different ways | |
Etaoin Wu, [13.03.18 15:06] | |
(correctness by abs(x)=max(a,-a)) | |
Etaoin Wu, [13.03.18 15:07] | |
then we solved st5 with an O(n) algorithm. | |
Etaoin Wu, [13.03.18 15:07] | |
subtask 6. 1st tree + 2nd tree + 3rd path. | |
Etaoin Wu, [13.03.18 15:08] | |
it's complex, so we try to convert it to the "tree + tree" subtask which we solved previously. | |
Etaoin Wu, [13.03.18 15:09] | |
we do a divide & conquer on the 3rd path and calculate all the path over the midpoint. now the problem is : | |
Etaoin Wu, [13.03.18 15:10] | |
find l <= mid, r >= mid, maximize dis1(l,r) + dis2(l,r) + len(l) + len(r), where len() denotes the distance to the midpoint | |
Etaoin Wu, [13.03.18 15:11] | |
then we can put the effect from the path on the 2nd tree: create a node x' for any node x where dis2(x,x') = len(x) | |
Etaoin Wu, [13.03.18 15:12] | |
but if we call the "tree+tree" subtask directly we will get a O(n^2) algorithm, for divide & conquer calls O(n) steps | |
Etaoin Wu, [13.03.18 15:13] | |
the problem is that most points on 1st tree and converted 2nd tree is useless in the calculation | |
Etaoin Wu, [13.03.18 15:16] | |
so we need to construct the auxiliary tree of 1st and converted 2nd and do DP on it | |
Etaoin Wu, [13.03.18 15:34] | |
which we got O(r-l) for any divide and conquer step | |
Etaoin Wu, [13.03.18 15:34] | |
the overall running time is O(nlogn*time of LCA) | |
Martin, [13.03.18 17:34] | |
Okay I get it | |
Etaoin Wu, [13.03.18 17:35] | |
and the next subtask i will translate later | |
Etaoin Wu, [13.03.18 20:44] | |
so you know "auxiliary tree" right? | |
Etaoin Wu, [13.03.18 20:44] | |
I'm not sure about its translation | |
Martin, [13.03.18 20:45] | |
I've never heard of it actually | |
Martin, [13.03.18 20:45] | |
Ohhh | |
Martin, [13.03.18 20:45] | |
Centroid decomposition? | |
Etaoin Wu, [13.03.18 20:45] | |
oops | |
Etaoin Wu, [13.03.18 20:45] | |
no | |
Etaoin Wu, [13.03.18 20:45] | |
when you are doing DP on tree | |
Etaoin Wu, [13.03.18 20:45] | |
the complexity is O(n) | |
Etaoin Wu, [13.03.18 20:46] | |
but most nodes on that tree is useless | |
Etaoin Wu, [13.03.18 20:46] | |
and we have a set of node, that's what we are interested in, lets call it A | |
Etaoin Wu, [13.03.18 20:47] | |
we can find a set B = A ∪ {lca(x,y) | x,y in A} | |
Etaoin Wu, [13.03.18 20:47] | |
and the size of B is O(|A|) | |
Martin, [13.03.18 20:47] | |
Isn't that centroid decomposition though? | |
Etaoin Wu, [13.03.18 20:48] | |
it's different | |
Etaoin Wu, [13.03.18 20:48] | |
[Reply to Martin] | |
if you use centroid decomposition in this step there is one more O(log) in the complexity | |
Martin, [13.03.18 20:49] | |
Anyway, go on | |
Etaoin Wu, [13.03.18 20:49] | |
this is an example | |
<photo> https://i.loli.net/2018/03/15/5aa9b36d035ff.jpg | |
Martin, [13.03.18 20:51] | |
Oh I get it now | |
Etaoin Wu, [13.03.18 20:51] | |
we can see that using B to dp will lead to an O(|A|) complexity | |
Etaoin Wu, [13.03.18 20:51] | |
[Reply to Martin] | |
is there a name of it? in chinese it's called 虚树 which means "auxiliary tree" | |
Etaoin Wu, [13.03.18 20:53] | |
to calculate B we can sort A with the dfs order (order same as DFN in tarjan's algorithm), and get LCA() of any A(i) and A(i+1) | |
Etaoin Wu, [13.03.18 20:55] | |
when solving subtask 6 we use divide&conquer right? we can use merging sort to avoid a more O(log) complexity when building auxiliary tree. | |
Etaoin Wu, [13.03.18 20:55] | |
and we come to subtask 7. | |
Etaoin Wu, [13.03.18 20:56] | |
if you do a naive centroid decomposition on the 1st tree, you will find it hard that the set of vertex was divided into many subsets (equal to the degree of the decomposition centroid) | |
Martin, [13.03.18 20:56] | |
[Reply to Etaoin Wu] | |
I don't think so, I've never seen a problem with it either | |
Etaoin Wu, [13.03.18 20:57] | |
https://www.google.com/search?num=30&newwindow=1&ei=c3qnWrTVLYnSjwSFt7SIAw&q=auxiliary+tree+site%3Acodeforces.com&oq=auxiliary+tree+site%3Acodeforces.com&gs_l=psy-ab.3...29631.29631.0.30091.1.1.0.0.0.0.250.250.2-1.1.0....0...1.1.64.psy-ab..0.0.0....0.62Qi36Bx-RM | |
Etaoin Wu, [13.03.18 20:57] | |
I found some results in CF, you can view this later. | |
Martin, [13.03.18 20:57] | |
The concept is very easy, I understand it | |
Etaoin Wu, [13.03.18 20:58] | |
yes | |
Etaoin Wu, [13.03.18 20:58] | |
then we do a three-degree cenvertion (I never saw this in English either) on the first tree | |
Martin, [13.03.18 20:59] | |
What's that? | |
Etaoin Wu, [13.03.18 20:59] | |
we need to convert a tree with a larger max-degree into a tree whose max-degree <= 3, and in this problem we need to keep the dis() property unchanged | |
Martin, [13.03.18 21:02] | |
[Reply to Etaoin Wu] | |
https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree this? | |
Etaoin Wu, [13.03.18 21:02] | |
no | |
Etaoin Wu, [13.03.18 21:02] | |
this convertion don't keep the dis() property | |
Etaoin Wu, [13.03.18 21:02] | |
<photo> https://i.loli.net/2018/03/15/5aa9b3a7c2902.jpg | |
the red ink means edge weight | |
Etaoin Wu, [13.03.18 21:03] | |
this is a segment tree structure | |
Etaoin Wu, [13.03.18 21:03] | |
and the grey vertex means new nodes, can be proven O(n) | |
Etaoin Wu, [13.03.18 21:04] | |
can you understand this? | |
Martin, [13.03.18 21:04] | |
And you do that for the children of every node, right? | |
Etaoin Wu, [13.03.18 21:04] | |
yes | |
Etaoin Wu, [13.03.18 21:04] | |
for every node degree > 3 | |
Etaoin Wu, [13.03.18 21:05] | |
so when we do a centroid decomposition, the tree is divided into <=3 parts. | |
Etaoin Wu, [13.03.18 21:06] | |
[Reply to Etaoin Wu] | |
like this, we're going to find l r in different parts, maximize dis2(l,r) + dis3(l,r) + len(l) + len(r), where len() denotes the distance to the centroid | |
Etaoin Wu, [13.03.18 21:09] | |
[Reply to Etaoin Wu] | |
and DP on 1st and 2nd auxiliary tree: maintain f[1..3][1..3] which f[i][j] means maximal distance from ith part to jth part | |
Etaoin Wu, [13.03.18 21:09] | |
and it can be merged (and update to the answer) in 6*6*time of dis(,) time | |
Etaoin Wu, [13.03.18 21:10] | |
so we get an O(n log n * (time of LCA) * 36) algorithm. | |
Etaoin Wu, [13.03.18 21:14] | |
any questions? | |
Martin, [13.03.18 21:18] | |
[Reply to Etaoin Wu] | |
What does 'part' mean? | |
Etaoin Wu, [13.03.18 21:19] | |
we do a centroid decomposition on the 3rd tree | |
Etaoin Wu, [13.03.18 21:19] | |
the centroid divide the 3rd tree into 3 parts | |
Etaoin Wu, [13.03.18 21:19] | |
and we calculate the answer of path(x,y) where centroid is on path3(x,y) | |
Etaoin Wu, [13.03.18 21:20] | |
that means x,y are in different parts of the tree | |
Martin, [13.03.18 21:20] | |
Oh, yes, right | |
Martin, [14.03.18 01:42] | |
[Reply to Etaoin Wu] | |
I'm not very sure about the 2 * 2 * 2 * 2 part, because it only makes sense to pair f11 with f22 and f12 with f21 | |
Martin, [14.03.18 01:43] | |
Because the answer is the maximum value of (f11(a) + f22(b)) or (f12(a) + f21(b)) | |
Martin, [14.03.18 02:58] | |
Also they call the segment tree-ish method you describe similar to the one in the Wikipedia article I sent (左儿子右兄弟) | |
Etaoin Wu, [14.03.18 07:29] | |
[Reply to Martin] | |
it seems that it's correct | |
Etaoin Wu, [14.03.18 07:30] | |
[Reply to Martin] | |
with that left-child right-sibling method, you cannot keep the distance information unchanged | |
Etaoin Wu, [14.03.18 07:30] | |
I think this is correct too: | |
<photo> https://i.loli.net/2018/03/15/5aa9b402c4e2c.jpg | |
still, red and orange ink is edge weight | |
Etaoin Wu, [14.03.18 07:58] | |
I've read the markdown file and thank you for your awesome work. | |
Etaoin Wu, [14.03.18 08:05] | |
[Reply to Etaoin Wu] | |
I'm going to change the segment tree-ish method to this method | |
Etaoin Wu, [14.03.18 19:59] | |
one of my friends suggested such an idea: | |
Etaoin Wu, [14.03.18 20:01] | |
instead of Centroid Decomposition (in that we determin a centroid node), we can use "Centroid Edge Decomposition" in which any round of D&C we find an edge, maximizing min(node count on side1, node count on side2) and divide the tree into 2 parts | |
Etaoin Wu, [14.03.18 20:02] | |
and we can avoid the (A,B) (B,C) (C,A) loop | |
Martin, [14.03.18 20:19] | |
If you use that technique, you don't have to make the tree binary, right? | |
Etaoin Wu, [14.03.18 20:19] | |
[Reply to Martin] | |
you still need to make the tree binary | |
Martin, [14.03.18 20:20] | |
Oh right yes | |
Etaoin Wu, [14.03.18 20:20] | |
think of a star graph <菊花图 in chinese> | |
Etaoin Wu, [14.03.18 20:20] | |
and the complexity becomes O(n^2) | |
Martin, [14.03.18 20:21] | |
node count on side1 + node count on side2 = n always right? | |
Martin, [14.03.18 20:21] | |
or n + extra nodes to make the tree binary | |
Etaoin Wu, [14.03.18 20:21] | |
[Reply to Martin] | |
no | |
Etaoin Wu, [14.03.18 20:21] | |
when you D&C into a deeper level, the side1+side2 = the node count of this level (subtree) | |
Etaoin Wu, [14.03.18 20:22] | |
and number of "extra nodes to make the tree binary" is O(n) | |
Martin, [14.03.18 20:22] | |
Yep I see | |
Etaoin Wu, [14.03.18 20:23] | |
now we don't have 3 parts | |
Etaoin Wu, [14.03.18 20:23] | |
it becomes 2 parts because of "Centroid Edge Decomposition" | |
Martin, [14.03.18 20:25] | |
And what do we do after that? | |
Etaoin Wu, [14.03.18 20:25] | |
then we give every node a color, 1 and 2 | |
Etaoin Wu, [14.03.18 20:26] | |
and we can ignore the 1st tree, maximize d2(x,y)+d3(x,y) where x,y have different color | |
Martin, [14.03.18 20:27] | |
The nodes on each side have the same color right? | |
Etaoin Wu, [14.03.18 20:27] | |
yes | |
Etaoin Wu, [14.03.18 20:30] | |
[ 图片 ] | |
let's call this structure a "diameter structure" | |
Etaoin Wu, [14.03.18 20:30] | |
and we do a DP on the 2nd tree, maintaining f1(p) and f2(p) means the diameter structure of color 1 and color 2 in subtree of p on the 1st tree | |
Martin, [14.03.18 20:30] | |
Don't you actually have to maximize d2(x,y)+d3(x,y)+distance_to_edge(x)+distance_to_edge(y)? | |
Etaoin Wu, [14.03.18 20:31] | |
yes | |
Etaoin Wu, [14.03.18 20:31] | |
we build a node x' where d2(x', x) = distance_to_edge(x) and d3(x', x) = 0 for any node x | |
Etaoin Wu, [14.03.18 20:31] | |
therefore the dis_to_edge() can be avoided | |
Martin, [14.03.18 20:32] | |
Yep, you're right, I see | |
Etaoin Wu, [14.03.18 20:32] | |
then it's a subtask tree+tree right? | |
Martin, [14.03.18 20:32] | |
So we use that and naively call the "tree+tree" subtask every time? | |
Etaoin Wu, [14.03.18 20:33] | |
we call "tree+tree" on two auxiliary trees | |
Martin, [14.03.18 20:34] | |
And this is O(nlogn) if we make the tree binary? | |
Etaoin Wu, [14.03.18 20:34] | |
yes | |
Etaoin Wu, [14.03.18 20:35] | |
[Reply to Martin] | |
O(nlogn*(time of LCA)) | |
Martin, [14.03.18 20:35] | |
Yeah I mean the D&C part is O(nlogn)\ | |
Etaoin Wu, [14.03.18 20:35] | |
and LCA can be solved with st table (O(nlogn) preprocessing and O(1) per query) | |
Martin, [14.03.18 20:36] | |
ST is actually <O(n), O(1)> for LCA but it doesn't matter much I gues | |
Martin, [14.03.18 20:36] | |
s | |
Etaoin Wu, [14.03.18 20:36] | |
[Reply to Martin] | |
that <O(n) O(1)> is ugly | |
Etaoin Wu, [14.03.18 20:36] | |
using that bitmask trick, maybe called "4 russians" | |
Martin, [14.03.18 20:37] | |
hahaha the total code length is going to be like 6kb, why not add a few hundred bytes | |
Etaoin Wu, [14.03.18 20:37] | |
one of my friends have wrote it | |
Etaoin Wu, [14.03.18 20:37] | |
7.9 kb total | |
Etaoin Wu, [14.03.18 20:37] | |
(his code style is ugly i think) | |
Etaoin Wu, [14.03.18 20:38] | |
http://uoj.ac/submission/228833 | |
Martin, [14.03.18 21:12] | |
can you write some pseudocode for D&C on edges? | |
Martin, [14.03.18 21:12] | |
I want to add it to the article | |
Etaoin Wu, [14.03.18 21:13] | |
first let's assume the tree has max degree 3 | |
Martin, [14.03.18 21:14] | |
it's rec(Graph) { find edge maximizing min(nodes on side1, nodes on side2); colour edges on side1 black; colour edges on side2 red; solve(side1,side2); rec(side1); rec(side2);} right? | |
Etaoin Wu, [14.03.18 21:14] | |
yes | |
Etaoin Wu, [14.03.18 21:16] | |
https://www.etaoinwu.win/jedojidahaqe.coffeescript |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment