Fishingprince Plays With Array (Codeforces 1696C)
Tags: Greedy, implementation

Fishingprince is playing with an array $$$[a_1,a_2,\dots,a_n]$$$. He also has a magic number $$$m$$$.He can do the following two operations on it:  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]$$$.  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]$$$. 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).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.

Input: 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.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$$$).The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$).The third line of each test case contains one integer $$$k$$$ ($$$1\le k\le 5\cdot 10^4$$$).The fourth line of each test case contains $$$k$$$ integers $$$b_1,b_2,\ldots,b_k$$$ ($$$1\le b_i\le 10^9$$$).It is guaranteed that the sum of $$$n+k$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output: 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).

Note: 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]$$$.In the second testcase of the sample, we can:  do the second operation with $$$i=2$$$: $$$[1,\color{red}{2,2},8,2,2]\to [1,\color{red}{4},8,2,2]$$$.  do the second operation with $$$i=4$$$: $$$[1,4,8,\color{red}{2,2}]\to [1,4,8,\color{red}{4}]$$$.  do the first operation with $$$i=3$$$: $$$[1,4,\color{red}{8},4]\to [1,4,\color{red}{4,4},4]$$$.  do the second operation with $$$i=2$$$: $$$[1,\color{red}{4,4},4,4]\to [1,\color{red}{8},4,4]$$$.  do the second operation with $$$i=3$$$: $$$[1,8,\color{red}{4,4}]\to [1,8,\color{red}{8}]$$$.  do the second operation with $$$i=2$$$: $$$[1,\color{red}{8,8}]\to [1,\color{red}{16}]$$$.

Sample Inputs:
5
5 2
1 2 2 4 2
4
1 4 4 2
6 2
1 2 2 8 2 2
2
1 16
8 3
3 3 3 3 3 3 3 3
4
6 6 6 6
8 3
3 9 6 3 12 12 36 12
16
9 3 2 2 2 3 4 12 4 12 4 12 4 12 4 4
8 3
3 9 6 3 12 12 36 12
7
12 2 4 3 4 12 56

Sample Outputs:
Yes
Yes
No
Yes
No

Solution (Python):
def int_input():
    a = int(input())
    return a

def int_list_input():
    a = list(map(int, input().split()))
    return a

def expand(a, m):
    b = []
    for i in a:
        x = i
        while x % m == 0:
            x = x // m
        if b and b[-1][0] == x:
            b[-1][1] += i // x
        else:
            b.append([x, i // x])
    return b

def solve():
    (n, m) = int_list_input()
    a = int_list_input()
    k = int_input()
    b = int_list_input()
    print('Yes' if expand(a, m) == expand(b, m) else 'No')
if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

Solution (Python):
from collections import defaultdict
r = []

def cut(d, a, m):
    n_a = []
    for e in a:
        t = e
        while e % m == 0:
            e //= m
        if n_a and n_a[-1][0] == e:
            n_a[-1][1] += t // e
        else:
            n_a.append([e, t // e])
    return n_a
for _ in range(int(input())):
    (n, m) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    k = int(input())
    b = list(map(int, input().split()))
    d_a = []
    y_b = []
    if cut(d_a, a, m) == cut(y_b, b, m):
        r.append('YES')
    else:
        r.append('NO')
for e in r:
    print(e)

Solution (Python):
def expand(a, m):
    b = []
    for x in a:
        t = x
        while t % m == 0:
            t //= m
        if b and b[-1][0] == t:
            b[-1][1] += x // t
        else:
            b.append([t, x // t])
    return b
for _ in range(int(input())):
    (_, m) = map(int, input().split())
    a = map(int, input().split())
    input()
    b = map(int, input().split())
    print('Yes' if expand(a, m) == expand(b, m) else 'No')