Editorial for COCI '20 Contest 1 #3 3D Histogram
Submitting an official solution before solving the problem yourself is a bannable offence.
We will solve the problem in complexity .
Let and .
We want to find the interval which maximises . Solution is based on divide-and-conquer approach: function will find the best interval contained in that includes the point . It will recursively call and .
Let be an interval such that and . We consider four cases:
- and are determined by the left half, i.e. and .
- and are determined by the right half, i.e. and .
- is determined by the left, and by the right half.
- is determined by the right, and by the left half.
First and second cases are analogous, and so are third and fourth, so we will describe the solution for the first and the third case.
Case 1: and are determined by the left half.
Note that this implies and .
This case can easily be solved using the two pointers method in complexity , i.e. in total.
Case 3: is determined by the left, and by the right half.
Note that this implies and .
This case is much more complex, and it can also be solved in total complexity. We will first describe an solution, and then optimise it.
For some , let's denote the interval of possible 's by . Borders and can again be found using the two pointers method.
We have
where represents the dot product of vectors and . Note that the first vector depends only on , and the second vector depends only on .
For a fixed , we want to find the that maximises the dot product. If was not limited to that interval, we could calculate the convex hull of the set of second points, and use ternary search to find the optimal for each . But now, we can sort the points by (for example) the first coordinate and build a segment tree that has the convex hull of the corresponding points in each node. So, for each we will look at nodes in the segment tree, and do a ternary search on the hull in each node in complexity. This gives us the total complexity of , because we also need to count in the divide-and-conquer.
Now we want to get rid of the binary search. Notice that points move counterclockwise as increases, and so the optimal point on the hull will also move counterclockwise! For each node in the segment tree, we can answer its queries in amortised linear complexity, by keeping a pointer to the optimal point for the last query. This gives us a total complexity of .
Comments