### ersahinceumut's blog

By ersahinceumut, history, 7 weeks ago,

Here is the problem: 1790F - Timofey and Black-White Tree

Here is the idea behind the solution: We add black nodes to the tree one by one, each time calling a BFS starting on the newly added black node in order to find the closest black node. If the path we find is smaller than the previous answer, we update accordingly. I also implemented an optimization where if the BFS depth exceeds the previous smallest path length, we stop the BFS.

My question is why / in what type of test case does this TL? I tried some randomized tests on $2\cdot10^5$ nodes but couldn't find a TL.

Here is my implementation of said solution: 191442467

• +1

 » 7 weeks ago, # |   0 Auto comment: topic has been updated by ersahinceumut (previous revision, new revision, compare).
 » 7 weeks ago, # |   +1 I was able to modify it to get AC: 191641295. I think the worst case is something like this: A tree of about $10^5$ nodes and 10,000 leaves. Each leaf has a path of length 10 to the root and the paths don't overlap except the root. The first vertices colored are the leaves. Because they're all the same distance apart, I think your algorithm needs to search the whole tree for every leaf in this case. I edited it so that we stop at a vertex when we know we're not going to find a shorter distance down that path. I'm not sure what the worst case time complexity is (or if it's hackable) tbh, I'd have to think about it.
 » 7 weeks ago, # |   0 Consider a tree with $O(\sqrt n)$ links of length $O(\sqrt n)$ attached to the root, and all colored vertices are the leaves. I think it's the worst case for you to BFS from one leaf to update another leaf.The most important optimization is: you only push the vertice if you can make the answer smaller, because answer will $\le O(\sqrt n)$ in the first $O(\sqrt n)$ operations, with this observation, all vertices will be updated at most $O(\sqrt n)$ times, so its time complexity is $O(n\sqrt n)$, I think so...