WeirdSort (Codeforces 1311B)
Tags: Others, dfs and similar

You are given an array $$$a$$$ of length $$$n$$$.You are also given a set of distinct positions $$$p_1, p_2, \dots, p_m$$$, where $$$1 \le p_i < n$$$. The position $$$p_i$$$ means that you can swap elements $$$a[p_i]$$$ and $$$a[p_i + 1]$$$. You can apply this operation any number of times for each of the given positions.Your task is to determine if it is possible to sort the initial array in non-decreasing order ($$$a_1 \le a_2 \le \dots \le a_n$$$) using only allowed swaps.For example, if $$$a = [3, 2, 1]$$$ and $$$p = [1, 2]$$$, then we can first swap elements $$$a[2]$$$ and $$$a[3]$$$ (because position $$$2$$$ is contained in the given set $$$p$$$). We get the array $$$a = [3, 1, 2]$$$. Then we swap $$$a[1]$$$ and $$$a[2]$$$ (position $$$1$$$ is also contained in $$$p$$$). We get the array $$$a = [1, 3, 2]$$$. Finally, we swap $$$a[2]$$$ and $$$a[3]$$$ again and get the array $$$a = [1, 2, 3]$$$, sorted in non-decreasing order.You can see that if $$$a = [4, 1, 2, 3]$$$ and $$$p = [3, 2]$$$ then you cannot sort the array.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.Then $$$t$$$ test cases follow. The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m < n \le 100$$$) — the number of elements in $$$a$$$ and the number of elements in $$$p$$$. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$). The third line of the test case contains $$$m$$$ integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i < n$$$, all $$$p_i$$$ are distinct) — the set of positions described in the problem statement.

Output: For each test case, print the answer — "YES" (without quotes) if you can sort the initial array in non-decreasing order ($$$a_1 \le a_2 \le \dots \le a_n$$$) using only allowed swaps. Otherwise, print "NO".


Sample Inputs:
6
3 2
3 2 1
1 2
4 2
4 1 2 3
3 2
5 1
1 2 3 4 5
1
4 2
2 1 4 3
1 3
4 2
4 3 2 1
1 3
5 2
2 1 2 3 3
1 4

Sample Outputs:
YES
NO
YES
YES
NO
YES

Solution (Python):
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    arr = [int(x) for x in input().split()]
    p = set([int(x) - 1 for x in input().split()])
    right = [0] * n
    for i in range(n - 2, -1, -1):
        if i in p:
            right[i] += right[i + 1] + 1
    left = [0] * n
    for i in range(1, n):
        if i - 1 in p:
            left[i] += left[i - 1] + 1
    arr_sorted = arr.copy()
    arr_sorted.sort()
    positions = {}
    for i in range(n):
        positions.setdefault(arr_sorted[i], set())
        positions[arr_sorted[i]].add(i)
    for i in range(n):
        ele = arr[i]
        for p in positions[ele]:
            if p >= i - left[i] and p <= i + right[i]:
                break
        else:
            print('NO')
            break
    else:
        print('YES')

Solution (Python):
def sort_by_first(element):
    return element[0]
n_tests = int(input())
swaps = []
for i in range(102):
    swaps.append(0)
for t in range(n_tests):
    values = input().split()
    n_nums = int(values[0])
    n_swaps = int(values[1])
    nums = []
    values = input().split()
    for i in range(n_nums):
        nums.append([int(values[i]), i])
    nums.sort(key=sort_by_first)
    values = input().split()
    for i in range(n_swaps):
        index = int(values[i])
        swaps[index] = 1
    flag = 0
    lowest_index_moved = 102
    for i in range(n_nums - 1, -1, -1):
        current_num_pos = nums[i][1]
        if current_num_pos < lowest_index_moved:
            if current_num_pos < i:
                for j in range(current_num_pos + 1, i + 1):
                    if swaps[j] == 0:
                        flag = 1
            lowest_index_moved = current_num_pos
        if flag == 1:
            break
    for i in range(n_swaps):
        index = int(values[i])
        swaps[index] = 0
    if flag == 0:
        print('YES')
    else:
        print('NO')

Solution (Python):
import sys
import math

def mp():
    return map(int, sys.stdin.readline().split())

def rs():
    return sys.stdin.readline().rstrip()

def ri():
    return int(sys.stdin.readline())

def ria():
    return list(map(int, sys.stdin.readline().split()))

def ws(s):
    sys.stdout.write(s + '\n')

def wi(n):
    sys.stdout.write(str(n) + '\n')

def wia(a):
    sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def main(tc: int):
    (n, m) = mp()
    a = ria()
    p = ria()
    c = [0] * n
    l = 0
    for i in p:
        c[i - 1] = 1
    for i in range(n):
        if c[i] == 0:
            a[l:i + 1] = sorted(a[l:i + 1])
            l = i + 1
    for i in range(1, n):
        if a[i - 1] > a[i]:
            ws('NO')
            return
    ws('YES')
if __name__ == '__main__':
    t = ri()
    for tc in range(1, t + 1):
        main(tc)