SHFTPAL - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

You’re given an array of length 2N that includes every integer in [1, N] twice each.
You can do the following:

  • Choose an integer k and k indices i_1 \lt i_2 \lt\ldots\lt i_k
  • For each j in [1, k] in order, move the element at index i_j to the start of the array.

A is called balanced if it’s possible to perform this operation and turn A into a palindrome.
Is the given array balanced?

EXPLANATION:

Let’s analyze the result of the operation.

Suppose we pick indices i_1, \ldots, i_k.
For convenience, let B denote the array after we’ve applied the operation - while A will always denote the initial array.
Then, because i_1 \lt \ldots\lt i_k, observe that moving an element to the front doesn’t affect anything about larger indices.
So, the set of elements moved to the front will be exactly the initial values of A_{i_1}, A_{i_2}, \ldots, A_{i_k}.

Thus, we’re effectively just choosing a subsequence of the array A.

Further, due to the order of operations, these elements will all end up being the first k elements of B, but in reverse order.
So, B will start with [A_{i_k}, A_{i_{k-1}}, \ldots, A_{i_2}, A_{i_1}]

For B to be a palindrome, it must thus end with these values (in reverse) too, i.e. B must end with [A_{i_1}, A_{i_2}, \ldots, A_{i_k}].

So, if the sequence of values we chose is denoted S, B must look like \text{rev}(S) + X + S for some middle part X; where + denotes array concatenation.

Observe here that B can be a palindrome if and only if X itself is a palindrome.
This gives us one condition for the indices we must choose.

Next, observe that if S is a valid operations subsequence that results in a palindrome; then choosing the complement of this subsequence (i.e. every unchosen index) will also work.
This is because, if choosing S results in \text{rev}(S) + X + S, the complement of S is exactly (X+S), so choosing it will result in \text{rev}(X+S) + S.
However, \text{rev}(X+S) = \text{rev}(S) + \text{rev}(X) = \text{rev}(S) + X since we noted that X must be a palindrome.
Thus, we end up with \text{rev}(S) + X + S again.

This observation is useful because it allows us to exclude any one index we don’t want to use.

For example, consider index 2N.
We know from the above observation that if there’s a solution that picks 2N, there’s also a solution that doesn’t.
Let’s try to build the solution that doesn’t pick index 2N.

Since index 2N isn’t picked, A_{2N} will surely be the last element of the resulting array.
Thus, the last element of our chosen subsequence has to be the other occurrence of A_{2N}.
Let this index be i_1.

Now, observe that:

  • If i_1 \lt 2N-1, then all the indices i_1+1, i_1+2, \ldots, 2N-1 cannot appear in our chosen subsequence; because we established that i_1 is the last index.
    So, for each of these elements, we must pick their other occurrence into our subsequence in the corresponding order.
    • That is, we must pick the other occurrence of A_{2N-1} as the second-last index, the other occurrence of A_{2N-2} as the third-last index, and so on.
    • Note that this might not always be possible; so if we run into order issues at any point we can immediately say that no solution exists.
  • On the other hand, if i_1 = 2N-1, we can simply apply the exact same argument to the remaining prefix of the array, i.e. it can be shown that there will be a solution that doesn’t pick index 2N-2 and so the second-last index must be the other occurrence of A_{2N-2}, and so on.

More generally, the above algorithm can be thought of as follows:

  • Initially, all indices from 1 to 2N are not marked.
    Let S be the subsequence of operations we want to build.
    We will build S in reverse.
  • Repeatedly do the following:
    • Find the largest unmarked index.
      Let the element here be x.
    • Choose the other index containing x, and insert it to the front of S.
      However, this is allowed if and only if the new index is smaller than the previous first element of S.
    • If the extension to S was successful, mark both occurrences of x and continue the process.
    • If the extension was unsuccessful, stop the process - the S we have is final.

This will give us a candidate for S, so we can then check if operating using this results in a palindrome or not.

The correctness of this algorithm is established by the discussion above.

One way to implement this without too much code/casework, in linear time, is as follows.
Iterate over the array A in reverse, and maintain a queue Q.
Then, when processing A_i,

  • If A_i equals the front of the queue, pop the front of the queue.
  • Otherwise, push A_i to the back of the queue.

Then, the array is balanced if and only if in the end, Q is itself a palindrome.

It can be verified that this is equivalent to the greedy algorithm we had earlier, and it has the additional benefit of being very easy to implement.
In particular, the queue Q represents all the unmatched elements, i.e. the “middle part” X above (which must be a palindrome), while the elements popped from the queue represent the subsequence S.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    queue = []
    ptr = 0
    for x in reversed(a):
        if ptr >= len(queue) or queue[ptr] != x:
            queue.append(x) # push to back
        else:
            ptr += 1 # functionally, pop front
    rem = queue[ptr:]
    if rem == rem[::-1]: print('Yes')
    else: print('No')