lmn0x4F's blog

Time complexity of dp on tree. Round #322 F
By lmn0x4F, history, 8 years ago, In English

Hi,

I was doing some virtuals and found this problem 581F - Зубликанцы и мумократы

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi! Out of curiosity, how does your solution perform on the input produced by this python code ?

print(str(5000))
for i in range(1, 2500):
        print(str(2*i-1) + " " + str(2*i))
        print(str(2*i-1) + " " + str(2*i+1))
print("2 5000");

I tested it on my computer, adding a counter, and it looks as though the inner loop is executed 2,607,292,500 times.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply