Editorial for DMOPC '21 Contest 2 P6 - Strange Function
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Throughout this editorial, we refer to as just . We also use 1-indexing for all indices.
Subtask 1
For subtask 1, it suffices to simulate the function explicitly for each type 1
query and handle type 2
and 3
queries naively. However, the implementation of given in the problem statement is , which is not fast enough. There are many ways to optimize to , one of which is to observe that all the indices involved in a recursive call to are indices where the suffix minimum changes and find these with e.g. a stack.
Time complexity:
Subtask 2
For subtask 2, observe that after one call to , and similarly for all after calls to . Hence converges to the identity permutation after only calls to , so we don't need to continue updating after this point. To handle type 3
queries in constant time, we also maintain the inverse of and update this after each of the first type 1
queries.
Time complexity:
Subtask 3
For subtask 3, we essentially need to efficiently simulate calls to in a row.
Consider where the maximum element of ends up after calls. Unless it gets "pushed" all the way to the right end of the permutation, it will never be selected as an index in a call to and thus it will move one index to the right each time. Hence if initially, then after calls. As for the other elements, the maximum element does not interfere with their relative orders during a call to . Consider deleting this maximum element, finding the final permutation if this maximum element didn't exist, and inserting it back into the final permutation at the correct position. Repeating this reasoning with the second maximum element, third maximum element, and so on, we can efficiently simulate these operations with a data structure such as an order statistic tree (policy based data structures in C++).
Time complexity:
Subtask 4
For subtask 4, we need to handle general type 2
queries.
Some observations/ideas that motivate the solution:
It might help to think of the queries as "given and , what is after calls to ?" instead of trying to maintain after each individual call to . This suggests handling all the queries offline.
It also might help to find a simple way of thinking about what does. Two interpretations include:
- Consider drawing a histogram with positions in a row and square blocks at position . Then is equivalent to letting all the blocks get pushed horizontally by one unit, with a "wall" after the rightmost position preventing blocks from getting pushed after this point.
- is also equivalent to one iteration of a bubble-sort like loop:
void f(int l,int r) { int i; for (i = r; i > l; i--) { if (p[i-1] > p[i]) swap(p[i-1],p[i]); } }
Now for the solution:
For a number , consider writing a at index if and a if . Focusing on what does to this binary "slice" of , we can find that calls to is equivalent to moving all the 's by to the right, then "pushing" any 's that overflowed the right end back into the array, forming a suffix of entirely 's. If we have the set of all 's in the original stored in a data structure like a binary indexed tree, then we can check whether index () is a after calls with two cases:
- is not in the suffix. We can check if index exists and is a .
- is in the suffix. This occurs if there are at least 's between and .
Using this, we can perform a simultaneous binary search on all the queries.
Remark: The second way of thinking about means that is a "layer" of a bubble sorting network. A standard idea regarding sorting networks is the 0-1 principle. This might help motivate the simultaneous binary search approach above.
Time complexity:
Subtask 5
For subtask 5, we need to handle general type 3
queries.
We can process the queries in decreasing order of while maintaining a binary indexed tree with a at index if and otherwise, similarly to subtask 4. For each query, do a binary search on this binary indexed tree to find the length of the suffix that is entirely 's after calls. All 's before this point get shifted by exactly to the right. Using this and another binary indexed tree for sums of indices, we can find the sum of all indices where after calls. By creating two events for each query, one at and one at , we can subtract these two sums to answer each query.
Time complexity:
Subtask 6
For subtask 6, we can combine the solutions for type 2
and 3
queries described in subtasks 4 and 5.
Time complexity:
Even Faster Solutions
It is actually possible to solve both type 2
and 3
queries in if we analyze what the above algorithms are really calculating.
During the simultaneous binary search for type 2
, if then the answer is simply as it is in the converged area. Otherwise, case 1 is equivalent to checking if and case 2 is equivalent to checking if the th smallest with is at least . It follows that the answer for a type 2
query is equal to if and if . These th smallest queries can be answered by sweeping through in decreasing order and maintaining an order statistic tree.
For type 3
, the binary search to find the length of the suffix is equivalent to finding the smallest index such that there are exactly 's between and . We can do this in with order statistics as well.
There exist some simpler solutions for type 3
as well, based on observing that each number will always move right by until it reaches a suffix of numbers greater than itself. After that, it will move left every time a larger number before it "pushes" it to the left. Finding the number of times the number gets "pushed" to the left turns out to be equivalent to some order statistic queries too.
Time complexity:
Further Thoughts
There is a very unexpected connection between this problem and th smallest queries, for both type 2
and type 3
queries. It is not obvious that the type 2
formula above is indeed still a permutation of !
The solution presented above for type 3
queries can just as easily answer queries of the form 3 l r
: Output the sum of the indices with . It is possible to generalize type 2
queries as well (2 l r
: Output the sum of all with ) with a solution based on splitting the sum into two parts: the numbers in the suffix and the numbers that are not, using some more data structures to handle these.
Comments