Instantly share code, notes, and snippets.

Embed
What would you like to do?
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