codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1311B.md (2150B)


      1 Source: https://codeforces.com/problemset/problem/1311/B
      2 
      3 B. WeirdSort
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $a$ of length $n$.
     22 
     23 You are also given a set of distinct positions $p_1, p_2, \dots, p_m$, where $1 \le p_i \lt 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.
     24 
     25 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.
     26 
     27 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.
     28 
     29 You can see that if $a = [4, 1, 2, 3]$ and $p = [3, 2]$ then you cannot sort the array.
     30 
     31 You have to answer $t$ independent test cases.
     32 
     33 Input
     34 
     35 The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.
     36 
     37 Then $t$ test cases follow. The first line of each test case contains two integers $n$ and $m$ ($1 \le m \lt 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 \lt n$, all $p_i$ are distinct) — the set of positions described in the problem statement.
     38 
     39 Output
     40 
     41 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".
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 6
     49 3 2
     50 3 2 1
     51 1 2
     52 4 2
     53 4 1 2 3
     54 3 2
     55 5 1
     56 1 2 3 4 5
     57 1
     58 4 2
     59 2 1 4 3
     60 1 3
     61 4 2
     62 4 3 2 1
     63 1 3
     64 5 2
     65 2 1 2 3 3
     66 1 4
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 YES
     73 NO
     74 YES
     75 YES
     76 NO
     77 YES
     78 ```