Editorial for Canada Day Contest 2021 - Half Heart

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Loop through the blocks and holes after sorting them by the x dimension. Let dx, dy, dz be the distance of a block to a hole in the x,y,z dimension. If you fix dy and dz, you can easily find the minimum dx using a range minimum query. To do this range minimum query you can use a segment tree for one dimension and cdq for another. Since you don't know dy and dz yet, you can binary search for them. Now you have 4 log factors. You can remove 2 log factors by incorporating the binary search into your segment tree and cdq using something resembling a segment tree walk, always making sure the value you are binary searching matches a boundary of your segment tree or cdq function call.

Time complexity: \mathcal O((n+q)\log^2(n+q))

Richard: apparently turning the first dim segtree into a parallel binary search significantly improves runtime. I think it's because memory goes from n \log n to n. I'm unable to get similar gains by turning the 2nd level into recursive though (that seems in line with 1D seg and div-conquer doing similarly).

The other optimization is to initialize the event queues using sorted arrays. Not doing this seems to increase my code's runtime by about 50% or so: the segtree itself is actually quite fast (due to being memory efficient I guess).


There are no comments at the moment.