Author: Serj Nagin
Tester: Sergey Kulik
Editorialist: Florin Chirica
You’re given an unknown permutation. From it, every element is erased. Then, all elements greater than it decrease by 1. All new permutations are noted on a paper, in random order (we don’t know which element was deleted to obtain a specific permutation). Given the list of obtained permutations, find a possible result for the unknown permutation.
QUICK EXPLANATION (Thanks to Serj Nagin):
Lets take first permutation, we will try to insert every element on every position. What do we have now? Yes, some possible candidates of the initial permutation. The only thing that we need to make is to check: is it good permutation or not. We can do it using polynomial hashes, we just calculate hash for every permutation in input and check that set of such permutations is equal to set of hashes of permutation that we can get after deleting every element.
How to check if a permutation is good?
Suppose we have a permutation p, p, …, p[n]. We erase progressively elements p, p, …, p[n] and we obtain n new permutations. We need to check if those n permutations are the same permutations from q. One way to do this is to hash each permutation from q. Also, let’s hash each of n obtained permutations. We can sort both hashes of q and n hashes obtained. Now, both sets need to be equal. If they are, the permutation p can generate permutations from q. Otherwise, it can’t. We can construct hashes of our permutation p in O(N ^ 2). Sorting them takes O(N * log(N)) and comparing with q hashes takes O(N) time. Hence, we can check if a permutation is good in O(N ^ 2) time.
What can be the candidates for the solution?
A brute force algorithm appears: try each of n! permutations and check each of them as stated above. The solution idea is to reduce the number of checked permutations. In order the algorithm to pass the time limit, we need to check at most n permutations, which leads to O(N ^ 3) solution.
Let’s iterate each q[i]. We assume for a given q[i] that element n was deleted from this permutation. An O(N ^ 4) algorithm is obvious now: Let’s try each position from q[i] and assume element n was there. Now, let’s check each permutation, as above.
We can reduce the algorithm to O(N ^ 3) by doing the following observation: for a fixed q[i], element n can be at most at one position. We can use information from other q[j], j != i to determine the position of element n.
The first observation is the element n becomes n - 1 in all q[j], j != i. Let’s note by pos position of n in the original permutation. The position of element n - 1 is
- pos - 1 in q[j], if position of element deleted from q[j] is < pos
- pos in q[j], if position of element deleted from q[j] is > pos
Hence, if pos is a valid position of n, value n - 1 needs to appear pos - 1 times on position pos - 1 and n - pos times at position pos in all q[j], j != i. We can iterate pos. Let’s define cnt[i] = number of times value n - 1 appears on position i in all q[j], j != i. For a pos to be the answer, cnt[pos-1] = pos-1 and cnt[pos] = n - pos. Obviously, there can exist maximum one pos with this property, so this leads to O(N ^ 3) algorithm.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon
To be updated soon