SEAPERM2 - Editorial

general
, , ,
1

PROBLEM LINK:

Author: Serj Nagin

Tester: Sergey Kulik

Editorialist: Florin Chirica

DIFFICULTY:

medium

PREREQUISITES:

hashing

PROBLEM:

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.

EXPLANATION

How to check if a permutation is good?

Suppose we have a permutation p[1], p[2], …, p[n]. We erase progressively elements p[1], p[2], …, 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

  1. pos - 1 in q[j], if position of element deleted from q[j] is < pos
  2. 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

2

I used a little different approach. For every given permutation, i assumed that this is the permutation without the number 1. What this did was gave me position of all other numbers except 1.

Now using any other permutation(i used just the next one, or prev if there was no next) i calculated the position of 1 in this. This gave me a possible ans.

Now assuming this is the actual ans i confirmed it by checking this with all given permutations(say ith) by deleting all numbers from this ans one by one and checking if any one matches with this given permutation(ith) and if it did i just moved on to next permutation(i+1th) and saved this number which i deleted from my ans so that i will not delete it while checking for next any permutation.

Complexity-> O(n^3) (forming a possible ans(n worst case) * (checking if this is valid)(n^2 worst case)).

My solution -> http://www.codechef.com/viewsolution/5370786

1 Like
3

Hmm, I think O(N^2 log N) solution is also possible.

Complexity of my code was O(N^3 log N) , but i had to check N^2 possible permutations,
so for each permutation i was checking it in O(N log N) if it was valid.

I had particularly same idea with hashing.
We can calculate each of N permutations without some removed number I in O(log N) time by using already calculated hashes of previous permutations without numbers that are less than I, and by using fenwick tree.

Here is my solution:
http://www.codechef.com/viewsolution/5419522

void solvep() is calculating hashes of permutation p[1…n] in may[1…n] and checks if it is same with initial hashes tmp[1…n].
I am pretty sure you will not understand anything in my code :smiley: :\ , but as you can see that this function is working in N log N time

4

My code is O(N^2)

Actually, when you figure the value in first position (which takes NN operations), you can figure out position 2, then position 3 and so on. Each additional step is done in O(N). Global is O(NN)

Explanation:

Let xi be the value at position i in original permutation.
In the derived permutations, what you have in position 1 is

either x1 // there are n-x1 such situations

either x1-1 // there are x1-1

either x2-1 // 0 or 1 situation

either x2 // 0 or 1 situation

For n large enough (>5), when you know x1, you also know x2.
And so on for x3…xn