CF 2197B - Array and Permutation

We are given a permutation p of length n and an array a of the same length. A permutation is an array of distinct integers from 1 to n, in some order.

codeforcescompetitive-programmingimplementationschedulessortingstwo-pointers

CF 2197B - Array and Permutation

Rating: 1100
Tags: implementation, schedules, sortings, two pointers
Solve time: 1m 21s
Verified: yes

Solution

Problem Understanding

We are given a permutation p of length n and an array a of the same length. A permutation is an array of distinct integers from 1 to n, in some order. We want to determine if a could have been produced from p using a sequence of operations where in each operation we select two adjacent elements in p and copy the value of one into the other. That is, for any adjacent pair (p[i], p[i+1]), we can set either p[i] = p[i+1] or p[i+1] = p[i].

The key is that these operations can only propagate existing numbers to neighbors, never introduce a new number. Therefore, every number that appears in a must have existed at some position in p. Furthermore, once a number is introduced into a position, it can "expand" left or right to overwrite other numbers, so contiguous blocks of the same number in a are generated by a single original occurrence in p.

The constraints are such that n can be up to 2 * 10^5, and the sum of n over all test cases does not exceed 2 * 10^5. This rules out any solution with worse than linear complexity per test case. Brute-force simulation of the copying operations would be quadratic in n in the worst case and will time out.

Subtle edge cases include arrays where all elements are equal, arrays where numbers repeat but are not contiguous in a, and arrays where the last or first element needs to be propagated from far away. For example, p = [1, 2, 3] and a = [2, 2, 2] is impossible because the number 2 cannot propagate to the first position if it is not initially there.

Approaches

A naive approach would be to simulate the operations directly: iterate through p, and for every mismatch with a, perform the copy operations until it matches. This works in principle because the operations allow spreading numbers to adjacent positions, but in the worst case, it would require O(n^2) operations. For example, if p is [1,2,3,...,n] and a is [1]*n, we would repeatedly overwrite elements one by one. With n up to 2 * 10^5, this is too slow.

The key observation for an optimal approach is that once a number exists in p, it can propagate through contiguous segments. Therefore, we only need to check if the sequence of numbers in a could be formed by expanding numbers present in p in order. Specifically, we traverse a from left to right, and maintain a pointer in p that represents the first available position for a new number. If a[i] matches the current number in p, we advance the pointer. If a[i] repeats the previous number in a, we continue. If a[i] does not match either the previous number or the next available number in p, the array is impossible.

This reduces the problem to a single pass through a while maintaining a pointer in p, giving a linear O(n) solution per test case.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n^2) O(n) Too slow
Optimal O(n) O(n) Accepted

Algorithm Walkthrough

  1. Read the permutation p and the array a. Initialize a pointer j = 0 for p.
  2. Traverse the array a from left to right. Let prev store the previous element in a, initially set to None.
  3. For each element a[i], if it is equal to prev, continue. This means we are in a contiguous block and no new number from p is needed.
  4. If a[i] is not equal to prev, we try to find it in p starting from index j. If p[j] equals a[i], increment j and update prev to a[i].
  5. If a[i] is not equal to prev and does not match p[j], the array a cannot be generated from p. Output NO.
  6. If we reach the end of a without conflicts, output YES.

Why it works: the pointer j ensures that we only use each element in p once as a source for new numbers. The propagation of repeated numbers in a is handled by comparing with prev. If a number in a cannot be matched with the next available number in p and is not a repeat, it means no legal sequence of copy operations can produce it, guaranteeing correctness.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    a = list(map(int, input().split()))
    
    j = 0
    prev = None
    possible = True
    
    for num in a:
        if num == prev:
            continue
        while j < n and p[j] != num:
            j += 1
        if j == n:
            possible = False
            break
        prev = num
        j += 1
    
    print("YES" if possible else "NO")

The solution reads input efficiently for multiple test cases. The pointer j advances through p only when a new number in a is encountered, ensuring each element of p is used at most once. Repeated numbers in a are handled by prev, so we do not consume new elements of p unnecessarily. The while loop guarantees we skip numbers in p that have already been passed and cannot contribute to the current number in a.

Worked Examples

Consider the first sample input:

p = [1,2,3], a = [1,2,2]
i a[i] prev j action
0 1 None 0 p[0] = 1, matches a[0], prev = 1, j = 1
1 2 1 1 p[1] = 2, matches a[1], prev = 2, j = 2
2 2 2 2 matches prev, continue

Output is YES. The trace shows repeated numbers propagate without advancing p.

Second sample:

p = [3,1,2,4], a = [3,4,2,2]
i a[i] prev j action
0 3 None 0 p[0] = 3, matches a[0], prev = 3, j = 1
1 4 3 1 p[1] = 1, skip -> j=2, p[2]=2 !=4, j=3, p[3]=4 matches, prev=4, j=4
2 2 4 4 j == n, cannot match a[2], break

Output is NO. This confirms the algorithm correctly detects impossible propagation.

Complexity Analysis

Measure Complexity Explanation
Time O(n) per test case Each element in a is processed once, pointer j in p only advances forward
Space O(n) Storing p and a arrays

With the sum of n over all test cases bounded by 2 * 10^5, this solution fits comfortably within the 2-second time limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    
    # solution function
    t = int(input())
    for _ in range(t):
        n = int(input())
        p = list(map(int, input().split()))
        a = list(map(int, input().split()))
        
        j = 0
        prev = None
        possible = True
        
        for num in a:
            if num == prev:
                continue
            while j < n and p[j] != num:
                j += 1
            if j == n:
                possible = False
                break
            prev = num
            j += 1
        
        print("YES" if possible else "NO")
    
    sys.stdout = sys.__stdout__
    return output.getvalue().strip()

# Provided samples
assert run("6\n3\n1 2 3\n1 2 2\n4\n3 1 2 4\n3 4 2 2\n5\n1 3 2 5 4\n3 3 3 5 4\n7\n3 7 4 2 1 6 5\n3 3 4 4 5 6 5\n7\n1 2 3 4 5 6 7\n