Editorial for OCC '19 G4 - Willson and Fighting
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For subtask 1, the intended solution is to do exactly what is described in the problem statement. That is, for all pairs of geese, if they both honk at each other, then increment the answers for both of the geese. There are
Time complexity:
For the other subtasks, it is helpful to find an algorithm that can be optimized from
The input contains
The geese are sorted by increasing radius, and each goose is described by a point and a square. There is no need to keep track of which pairs of geese are mates. In the rest of this editorial, "Goose
To get the answer for goose
Case 1,
. In this case, goose 's radius is less than or equal to goose 's radius. The following are equivalent conditions:- Goose
will fight with goose . - Goose
is honking at goose . - Point
is strictly inside square .
In summary, if point
is in square , then increment the answer for goose .- Goose
- Case 2,
. In this case, goose 's radius is greater than or equal to goose 's radius. If point is strictly inside square , then increment the answer for goose .
It takes
Time complexity:
For subtask 2, the intended solution is to optimize the previous solution to run in sub-
In the naive
- Insert a 2D point.
- Query a rectangle. Return the number of points that are inside the rectangle.
Then use the data structure like this. Query square
The data structure can be implemented with a 2D segment tree that uses
Similarly, to do the case 2's in sub-
- Insert a rectangle.
- Query a 2D point. Return the number of rectangles that the point is in.
Again, the data structure can be a 2D segment tree.
At this point, all of the case 1's and case 2's are handled. It is time to print the answer.
Time complexity:
Memory complexity:
For subtask 3, the intended solution is to memory optimize the subtask 2 solution. However, the author strongly dislikes 2D segment trees, so he used a different approach to solve subtask 3.
Consider a function
- If there are fewer than 2 geese in
, then nothing needs to be done. - Split the range
into the two ranges and . - Do the case 1's where goose
is in and goose is in . - Do the case 2's where goose
is in and goose is in . - Call
and . This will do the remaining case 1's and case 2's.
(Insert a diagram when I have time. Maybe it can help the reader visualize what's happening.)
The idea is to get the answer by running
The second observation is that the case 1's can be done quickly. First, insert all of the points in
- Insert a 1D point.
- Query a line segment. Return the number of points in this line segment.
- Reset. That is, remove all 1D points from the data structure.
The line sweep will generate
(Note: It is possible to use a BIT instead of a 1D segment tree. The time complexity is the same.)
The third observation is that the case 2's can be done quickly with line sweep. The approach is similar. The time complexity is also
At this point, the algorithm is complete. The time complexity of the algorithm can be described as:
The
The time complexity simplifies to
Time complexity:
Memory complexity:
Fun fact: This problem was originally supposed to be tle17c7p5, but my
Comments