1658C - Shinju and the lost permutation

#codeforces

Question link : https://codeforces.com/problemset/problem/1658/C

Pre-requisite : Relationship between \(p\) and \(c\)

In the question, we are given that: > \(c_i\) is the power of the (i - 1)th cyclic-shift of the permutation \(p\)

This means that \(c_1\) is the 0th shift : Which means that is, for that case, the permutation remains as is => \(p_1, p_2, p_3,...,p_n\)

\(c_2\) is the 1st shift : \(p_n, p_1, p_2, ..., p_{n-1}\) \(c_3\) is the 2nd shift : \(p_{n-1}, p_n, p1, p2, ..., p_{n-2}\)

So as you see items in \(c\) from 1st index to nth index, you start with the first item being at the start, then you suddenly go \(p_n\) and come back until \(p_2\)

So: \(c_1 \rightarrow p_1\) \(c_2 \rightarrow p_n\) \(c_3 \rightarrow p_{n-1}\) … \(c_n \rightarrow p_2\)

Where does \(c_i + 1 \geq c_{i+1}\) come from?

Case 1 : \(p_1 > p_n\)

Note that \(p_1\) corresponds to \(c_1\) and \(p_n\) corresponds to \(c_2\)

In this case, the next item that is coming at the start (\(p_n\)) is smaller than the current item. When \(p_n\) was at the last point, it didn’t contribute to \(c_1\) as \(p_n < p_1\), therefore it’s removal from the last point doesn’t affect the \(c\) value of \(p_1\). But now that it has come to the start of the permutation, we can see that the c-value increases by 1. Therefore in this case \(c_i + 1 =c_{i+1}\)

Case 2 : \(p_1 < p_n\)

Note that \(p_1\) corresponds to \(c_1\) and \(p_n\) corresponds to \(c_2\)

Now at the start we are bringing a bigger element.

When \(p_n\) was at the end of the array, it was more than \(p_1\) so it might be contributing to the c-value in that case (this will happen when \(p_n\) is the largest number in \(p\)). So removing it from the last position might decrease the c-value.

Also, when \(p_n\) comes at the start of the array, then it will shadow \(p_1\) and other items smaller than \(p_n\). This means, that the c-value could further decrease.

So we can see that in this case \(c_i \geq c_{i+1}\) (There are cases where the c-value remains the same. Example : 1, 3, 2 has c-value of 2, and 2, 1, 3 also has a c-value of 2)

So by combining \(c_i \geq c_{i+1}\) and \(c_i + 1 = c_{i+1}\) we can say that \(c_i + 1 \geq c_{i+1}\)

How is this condition enough to check whether a valid permutation can be formed?

Let’s first think about what a permutation would look like, when following the condition \(c_i + 1 \geq c_{i+1}\)

This, simply, means that we can have drastic reductions, but increments can only be done in 1s.

Case 1 : Maximum value in \(c\) is \(n\)

In this case, we will have a simple incremental array from 1 to n in \(c\). That is, it will look like : \(1, 2, ..., n\) because we NEED to have a single one, to represent the biggest element in \(p_n\), and we need to reach \(n\) from this value, and we can only increase by 1.

This would generate the simple permutation : \(n, 1, 2, ..., n-1\)

Case 2 : Maximum value in \(c\) is less than \(n\)

In this case, we would have repetitions of numbers in \(c\). Note that we can not have more than one 1 in \(c\). Other numbers can repeat.

So we need to reach this max number (let’s say \(m\)) from 1, and we can increase by one only.

So this can look like : \(1, 2, 3, 4, ..., m, m - 2, m - 1, ...\) Basically an increasing phase, followed by random drops and increases. The increasing phase can also have repetitions, and drops.

In order to construct the array, this construction method : https://codeforces.com/blog/entry/101302?#comment-899615

When the c value increases, then we can simply put a smaller number at the curr position. That will ensure that a correct permutation is being generated.

When the c-value decreases, note that this value would be a repetition - We already would have seen this value atleast once. Why? Because we started from 1, and in order to decrease, we must have reached the current value by increments of 1. That means we have seen all numbers between 1 and the current number. Therefore, all drops / decrements would generate a number, which already has been seen.

Another point to note : Between the previous instance of this number, and the current instance of this number, we either: - Decreased and increased - This would be handled by the “c-value increase” case. - Increased and decreased - This would mean that c-value increased, and decreased to come back at the same point. An “increase” in c-value means a decrease in absolute value in \(p\). Therefore, all numbers between the same instances would be smaller. This simply means that we can indeed have a correct permutation in this case too.

I think these inferences are enough to see that the condition is enough to check whether a valid permutation can be created from the given c-values.