Editorial for CCO '23 P6 - Triangle Collection
Submitting an official solution before solving the problem yourself is a bannable offence.
There are several greedy solutions that work. We will describe two of them.
First, greedily form as many pairs of equal-length sticks as possible. We then loop through these pairs in descending order, completing a triangle using the largest base possible at each step. If we run out of unpaired sticks, then try breaking apart the smallest paired sticks in order to form two new bases.
Binary search on the answer. To check if it is possible to make at least triangles, note that we should take the largest pairs of equal sticks and after that, the smallest remaining sticks. Then, we can sort these sticks in increasing order and form triangles one by one in order, checking that the triangle inequality holds at each step.
Note that simulating the subtask 1 solutions do a lot of repeated work on equal-length sticks. With some math, it is possible to handle groups of equal-length sticks at the same time, improving the complexity from to .
Time Complexity: or
We will start with the binary search greedy solution from subtasks 1 and 2. Note that the answer can change by at most per update. The main idea is to maintain some data structures representing the current set of triangles, such that updating these data structures by incrementing/decrementing or adding/deleting a stick is efficient.
We need to maintain the set of such that and the set of such that . It might help to split both of these sets into two
std::sets, say "small" and "large", representing the sticks we used and the sticks we did not use. We also maintain a segment tree with a at position whenever we use an and a at position whenever we use an . This way, we can check whether a configuration of triangles is possible by querying whether the prefix minimum is .
For each event, we first delete all sticks involved in the event from all the data structures, possibly decrementing our answer in the process. Then, we repeatedly attempt to increment by , moving sticks between the "small" and "large" sets and using the segment tree to check whether this is possible.
Two observations greatly simplify the implementation in this subtask. One observation is that if we have extra pairs of equal-length sticks after using all the single sticks, say pairs, then it is always possible to form more triangles with them, which is the maximum possible. This way, we never have to consider explicitly "breaking" apart a pair of equal-length sticks. Another observation is that we do not need to ensure "small" and "large" store precisely the smallest/largest sticks after a deletion, and instead just start from the smallest/largest unused sticks whenever we attempt to increase the answer. The correctness of this can be proved similar to the original greedy algorithm.
The observation from subtask 3 that the answer changes by at most per update still holds. Now, we need to represent the sets more efficiently by grouping equal-length sticks into one entry, similar to the optimization from subtask 1 to subtask 2. The rest of the details are the same as in subtask 3.
We will need a slightly different approach now that updates can significantly change the answer. The observation that extra pairs of equal-length sticks can always be completely used after using all the odd sticks is essential to the solution we will present.
Let be a list of all the indices with odd in increasing order. Note that if of these sticks get used, it suffices to use the smallest ones, and we can consider doing a binary search on . The condition we need to check is that:
Let be the number of paired sticks that can be used with a stick of length or smaller. Then we need for all , which rearranges to for all , i.e. the minimum for is at least .
This condition is sufficient, e.g. by Hall's Marriage Theorem.
We can maintain a range minimum query, range increment lazy segment tree mapping an index to . To represent indices not in , we can add a large value to those indices. Whenever we add/delete an odd stick of length , we add to indices , representing shifting the index . Whenever we add/delete some pairs of sticks of length , we update the range , representing a change in . To get the answer, we can do a binary search on and perform a segment tree query each time, taking time in total. It is also possible to combine the binary search on with a segment tree walk to get the answer in time. Finally, the overall answer after each event is , where is the total number of pairs.
Time Complexity: or