AlexLorintz's blog

By AlexLorintz, 8 months ago, In English

Hello! I've been thinking about this problem for a while and I couldn't be able to come up with a decent solution(basically implementing operations of type 2 and 3 which are the hard ones) and, unfortunately, there's no editorial describing the solution on the internet, only codes(or at least I can't find any editorial). I think the problem is a quite interesting tree task and I was wondering if someone could describe a possible approach to solve it? Problem statement:

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

8 months ago, # |
Rev. 4   Vote: I like it +32 Vote: I do not like it

Hey, I am actually the author of this problem. Unfortunately I seem to have never written an analysis, and I can't fully remember my solution. I remember some of the key ideas, though, so I'll give some guidelines and maybe you can fill in the gaps yourself.

First, there is a key observation for operations of type 2. The total amount of nodes which will be cleared by ultrasound (after having been infested) is actually quite low. You can intuitively see this from the fact that the only way to infest something is through operations 1 or 2. If it is through 1, the number of infested nodes increases by only 1. If we infect through operation 2, you can notice that all newly infected nodes after operation 2 finishes are on disjoint root-paths, so future operations of type 2 can't cover more than one of them simultaneously. This is intuition only, the formal proof (which I think used the method of potentials) wasn't trivial.

I don't remember whether the formal amortized analysis yielded a total of $$$O(N)$$$ or $$$O(NlogN)$$$ cleared nodes for operations of type 2, but it's one of these. This means that you can handle ultrasound cleanings one-by-one if you manage to skip all already-clear nodes.

The core of the implementational idea is to use heavy-light decomposition with segment trees on heavy paths. This lets you easily skip over chunks of non-infested nodes on a root path (and hence handle operation 2 in proper amortized time).

The second big problem is how to handle ultrasound "explosion" of a node, i.e. sending rats to all its children. You can't do this naively child by child. I don't remember the exact details of the implementation here, but the key trick was that you do this lazily. Whenever a node is cleared by ultrasound, you log that in the node, but you actually send the rats only to the single child sharing the node's heavy path (if there is one), all other children don't receive any information. With this approach nodes which are not roots of heavy paths always have the right value, while roots of heavy paths must check the logs of their parent to be sure.

My code seems nasty so probably not the easiest task, but I hope I've given you some pointers to the idea. The first observation about the amortized number of nodes cleared by ultrasound was the core idea of the problem, the rest was a lot of tricks in implementing it smartly.

Final complexity was likely a lightweight $$$O(Nlog^2N)$$$, although I'm not 100% sure.

Funnily enough this was a simplified version of another problem that I decided is too ridiculously hard to set and hard to solve to ever see the light of day.

Good luck :)