neal's blog

An interesting algorithm for Edu Round 98 Problem G
By neal, 4 years ago, In English

I finally got AC on problem G from Edu Round 98 earlier today. The editorial mentions centroid decomposition to get a runtime of $$$n \log^2 n$$$ or $$$n \log n$$$, but I actually had a completely different algorithm and I'm not 100% sure of the time complexity.

Like the editorial, my first idea was to compute the distances for each vertex to the closest of Bob's vertices using multi-source BFS. Then my goal is to iterate each vertex $$$v$$$, and for every vertex $$$u$$$ whose distance from $$$v$$$ is at most bob_distance[v] - 1, update answers[u] to be at least bob_distance[v].

Doing this directly via DFS is correct but obviously gets TLE, e.g., 99053280. I initially thought we could iterate $$$v$$$ in decreasing order of bob_distance[v] and stop the DFS anytime we reach a node that already has an answer. But this is incorrect because there can be cases where a smaller distance node reaches farther in some direction than a larger distance node.

Instead, by adding a key optimization to track the remaining steps we can still take from our current node and only continue the DFS when we strictly increase the maximum value of remaining this node has seen, the algorithm is correct and gets AC: 99053359.

I suspect this algorithm is $$$n \sqrt n$$$ in runtime. (I have a specific case where it takes $$$n \sqrt n$$$ steps to finish). Can anyone prove this runtime as an upper bound?

  • Vote: I like it
  • +128
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 3   Vote: I like it +118 Vote: I do not like it

I think I have a construction that requires $$$n^{5/3}$$$ steps. Here's a rough sketch.

Bob has a token at both B and B'. Then the $$$i$$$-th of the nodes on the right has bob_distance of $$$D-jk+2k-i$$$. This will update the A vertex with remaining of $$$jk+2i-k$$$. The token at B' is just to ensure that these are the only updates that happen to A. Note this has size $$$O(D+k^2)$$$. If we duplicate this $$$k$$$ times for different even values of $$$j$$$, sharing the common A vertex, and add a bunch of leaves to A, this should force $$$Ω(n^{5/3})$$$ updates if we pick (roughly) $$$D=k^2=n^{2/3}$$$.

I also think this example is tight. In an arbitrary tree, for each Bob token, the vertices that are closest to that token form a subtree, disjoint from the subtrees for the other tokens. Each subtree must have size $$$Ω(D+k^2)$$$ in order to trigger updates with $$$k$$$ distinct values for remaining at a given node, and with bob_distance at least $$$D$$$, and the worst we can do is pick $$$D,k$$$ as above.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    Awesome! This might be the first time I've implemented something with $$$\displaystyle n^{\frac{5}{3}}$$$ runtime. Luckily the constant factor still seems good--I implemented your test case and it still runs well under the time limit.

    → Reply