codeforces-scrape

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

1696C.md (3032B)


      1 Source: https://codeforces.com/problemset/problem/1696/C
      2 
      3 C. Fishingprince Plays With Array
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Fishingprince is playing with an array $[a_1,a_2,\dots,a_n]$. He also has a magic number $m$.
     22 
     23 He can do the following two operations on it:
     24 
     25 * Select $1\le i\le n$ such that $a_i$ is divisible by $m$ (that is, there exists an integer $t$ such that $m \cdot t = a_i$). Replace $a_i$ with $m$ copies of $\frac{a_i}{m}$. The order of the other elements doesn't change. For example, when $m=2$ and $a=[2,3]$ and $i=1$, $a$ changes into $[1,1,3]$.
     26 * Select $1\le i\le n-m+1$ such that $a_i=a_{i+1}=\dots=a_{i+m-1}$. Replace these $m$ elements with a single $m \cdot a_i$. The order of the other elements doesn't change. For example, when $m=2$ and $a=[3,2,2,3]$ and $i=2$, $a$ changes into $[3,4,3]$.
     27 
     28 Note that the array length might change during the process. The value of $n$ above is defined as the current length of the array (might differ from the $n$ in the input).
     29 
     30 Fishingprince has another array $[b_1,b_2,\dots,b_k]$. Please determine if he can turn $a$ into $b$ using any number (possibly zero) of operations.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.
     35 
     36 The first line of each test case contains two integers $n$ and $m$ ($1\le n\le 5\cdot 10^4$, $2\le m\le 10^9$).
     37 
     38 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$).
     39 
     40 The third line of each test case contains one integer $k$ ($1\le k\le 5\cdot 10^4$).
     41 
     42 The fourth line of each test case contains $k$ integers $b_1,b_2,\ldots,b_k$ ($1\le b_i\le 10^9$).
     43 
     44 It is guaranteed that the sum of $n+k$ over all test cases does not exceed $2\cdot 10^5$.
     45 
     46 Output
     47 
     48 For each testcase, print Yes if it is possible to turn $a$ into $b$, and No otherwise. You can print each letter in any case (upper or lower).
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 5
     56 
     57 5 2
     58 
     59 1 2 2 4 2
     60 
     61 4
     62 
     63 1 4 4 2
     64 
     65 6 2
     66 
     67 1 2 2 8 2 2
     68 
     69 2
     70 
     71 1 16
     72 
     73 8 3
     74 
     75 3 3 3 3 3 3 3 3
     76 
     77 4
     78 
     79 6 6 6 6
     80 
     81 8 3
     82 
     83 3 9 6 3 12 12 36 12
     84 
     85 16
     86 
     87 9 3 2 2 2 3 4 12 4 12 4 12 4 12 4 4
     88 
     89 8 3
     90 
     91 3 9 6 3 12 12 36 12
     92 
     93 7
     94 
     95 12 2 4 3 4 12 56
     96 ```
     97 
     98 Output
     99 
    100 ```
    101 Yes
    102 Yes
    103 No
    104 Yes
    105 No
    106 ```
    107 
    108 Note
    109 
    110 In the first test case of the sample, we can do the second operation with $i=2$: $[1,\color{red}{2,2},4,2]\to [1,\color{red}{4},4,2]$.
    111 
    112 In the second testcase of the sample, we can:
    113 
    114 * do the second operation with $i=2$: $[1,\color{red}{2,2},8,2,2]\to [1,\color{red}{4},8,2,2]$.
    115 * do the second operation with $i=4$: $[1,4,8,\color{red}{2,2}]\to [1,4,8,\color{red}{4}]$.
    116 * do the first operation with $i=3$: $[1,4,\color{red}{8},4]\to [1,4,\color{red}{4,4},4]$.
    117 * do the second operation with $i=2$: $[1,\color{red}{4,4},4,4]\to [1,\color{red}{8},4,4]$.
    118 * do the second operation with $i=3$: $[1,8,\color{red}{4,4}]\to [1,8,\color{red}{8}]$.
    119 * do the second operation with $i=2$: $[1,\color{red}{8,8}]\to [1,\color{red}{16}]$.