Hi,
I was doing some virtuals and found this problem 581F - Zublicanes and Mumocrates
We need to color each vertex of a tree of either color 0 or color 1, such that # of leaves of color 0 equals # of leaves of color 1 (there is an even number of leaves) and we're asked to minimize the # of "bad edges". A bad edge is an edge that connects two vertexes of different colors.
For solving it I tried a dp, I first rooted the tree at a non-leaf vertex and try dp[c][u][cnt] = minimum number of bad edges that let us paint the sub tree of u such that u is colored c and there are cnt leaves of color 0. So answer to the problem will be min( dp[0][ROOT][(#leaves)/2], dp[1][ROOT][(#leaves)/2])
For each node u I calculate this dp by starting with an empty subtree and adding one child at a time, for each child v I iterate cnt over the new size of the subtree of u, and for each cnt I iterate cntv ( cntv = how many leaves is contributing v to this cnt).
Here's the code: 19434646
I got accepted with it but this kind of dps always confuses me, I don't know how to measure time complexity. To me it seems to be not very good, I would say its something like O(N^3) at least but it ran in 109 ms for N=5000. I've done other dps like this one before and I think I'm not measuring the time correctly (major reason why I tried sending this code hehe). Could someone give me a reasoning that would led to a better measure?
Thanks.
Hope I made myself clear.
If you have a tree dp in a binary tree which does O(AB) operations in every node where A is the size of left subtree and B is the size of right subtree then the total complexity will be O(n2). Proof: work done in vertex u is number of pairs of vertices (v, w) such that lca(v, w) = u.
I did not look into your solution too carefully but this is a common way to prove that seemingly O(n3) tree dp is actually O(n2) so I think your time complexity can be proven to be O(n2) using argument like this.
When you process the contribution of a subtree of size q to its parent, you use O(q) operations. This happens N — 1 times, and q is never greater than N, so it is O(N2) overall.
Hi! Out of curiosity, how does your solution perform on the input produced by this python code ?
I tested it on my computer, adding a counter, and it looks as though the inner loop is executed 2,607,292,500 times.
It indeed takes several seconds on this input. Thank you for pointing out that my solution isn't actually O(n2) :D
I'll try to see why it isn't and how to make it O(n2)
Thank you!
(Sorry for taking so much to answer, I've been busy :p)