PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Disjoint sets,Amortized Analysis
PROBLEM:
You have a list of permutations L. Initially, it consists of only one permutation \{1\}.
You are asked to construct a given permutation P consisting of N elements. The following rules are followed for constructing permutations:
You can choose two indices i,j (not necessarily different) such that P_1=L_i (the first permutation) and P_2=L_j (the second permutation).
Afterward, you create a new permutation by concatenating P_1 and P_2 in any order you wish.
In the end, you can either add the size of P_1 to elements of P_2 in the new permutation or add the size of P_2 to elements of P_1. As a result, you would have a new permutation that you can use in future operations and it’s appened to L.
Your task is to find out if the given permutation can be generated through these rules. If it is, show a possible sequence of moves or state that it’s impossible.
This description is brief, it’s recommended to read the original problem statement.
N \leq 10^6
Explanation:
Well, the solution to this problem is done by just implementing the reverse process. We know that each permutation is constructed by combining 2 preconstructed permutations and concatenating them.
Let’s write a recursive function that takes a permutation P as an argument and checks for a valid split point. Then,it splits our permutation into 2 parts and constructs each part separately recursively.
What’s a valid split point?
Let’s assume that we want to split at the x^{th} element (and this element belongs to the left part). This implies that the first x elements must be the smallest x elements in the permutation or the largest x elements. In the first case, we pass the first x elements to our function and tell to construct a corresponding permutation, then we pass the rest of the elements after we subtract x from each of them to our function to construct an equivalent permutation (the second case is done the same but we subtract from left part). After our function returns from both calls, we simply merge the constructed two permutations. Once we find a split point we can immediately split there, we don’t need to try other split points (think about the proof).
Our function looks like solve(l\,,r\,,dec). it denotes the interval we are interested in constructing a permutation for, and the amount of decrement for each element in the interval.
Now we should find a split point. If we do this in a linear loop that scans all the elements, our complexity will reach O(N^2). Let’s reduce it to O(N\,log\,N).When breaking the permutation into two, the smaller of them will have at most half of the big permutation’s size. Let’s search for this small part by keeping 2 pointers (one running from left to right and another in the opposite direction). When finding a split point we pass the smaller part and the bigger part (note that we don’t process the elements of the bigger part), and we pass the corresponding decrement along with each part.
How did this reduce the complexity to O(N\,log\,N) ?
Imagine our solution running bottom up, it’s always merging 2 permutations into big one by processing the elements of the smaller one. It’s the same as (small to big) trick used in disjoint set data structures. When moving one element from one set to another, the set which is moved to has at least the same size as its current set. That means that each element will be processed and moved at most log\,N times. We are doing the same here. Note that even we are running 2 loops (one from each end) but that only multiplies the whole complexity by a constant factor of 2.
Check my implementation for more details.