[Solution] Equate Multisets solution codeforces

Equate Multisets solution codeforces – Multiset —is a set of numbers in which there can be equal elements, and the order of the numbers does not matter. Two multisets are equal when each value occurs the same number of times. For example, the multisets {2,2,4}{2,2,4} and {2,4,2}{2,4,2} are equal, but the multisets {1,2,2}{1,2,2} and {1,1,2}{1,1,2} — are not.

Table of Contents

[Solution] Equate Multisets solution codeforces

You are given two multisets 𝑎a and 𝑏b, each consisting of 𝑛n integers.

In a single operation, any element of the 𝑏b multiset can be doubled or halved (rounded down). In other words, you have one of the following operations available for an element 𝑥x of the 𝑏b multiset:

  • or replace 𝑥x with 𝑥2x⋅2,
  • or replace 𝑥x with 𝑥2⌊x2⌋ (round down).

Note that you cannot change the elements of the 𝑎a multiset.

See if you can make the multiset 𝑏b become equal to the multiset 𝑎a in an arbitrary number of operations (maybe 00).

For example, if 𝑛=4n=4𝑎={4,24,5,2}a={4,24,5,2}𝑏={4,1,6,11}b={4,1,6,11}, then the answer is yes. We can proceed as follows:

  • Replace 11 with 12=21⋅2=2. We get 𝑏={4,2,6,11}b={4,2,6,11}.
  • Replace 1111 with 112=5⌊112⌋=5. We get 𝑏={4,2,6,5}b={4,2,6,5}.
  • Replace 66 with 62=126⋅2=12. We get 𝑏={4,2,12,5}b={4,2,12,5}.
  • Replace 1212 with 122=2412⋅2=24. We get 𝑏={4,2,24,5}b={4,2,24,5}.
  • Got equal multisets 𝑎={4,24,5,2}a={4,24,5,2} and 𝑏={4,2,24,5}b={4,2,24,5}.

[Solution] Equate Multisets solution codeforces

The first line of input data contains a single integer 𝑡t (1𝑡1041≤t≤104) —the number of test cases.

Each test case consists of three lines.

The first line of the test case contains an integer 𝑛n (1𝑛21051≤n≤2⋅105) —the number of elements in the multisets 𝑎a and 𝑏b.

The second line gives 𝑛n integers: 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎1𝑎2𝑎𝑛1091≤a1≤a2≤⋯≤an≤109) —the elements of the multiset 𝑎a. Note that the elements may be equal.

The third line contains 𝑛n integers: 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏1𝑏2𝑏𝑛1091≤b1≤b2≤⋯≤bn≤109) — elements of the multiset 𝑏b. Note that the elements may be equal.

It is guaranteed that the sum of 𝑛n values over all test cases does not exceed 21052⋅105.

[Solution] Equate Multisets solution codeforces

For each test case, print on a separate line:

  • YES if you can make the multiset 𝑏b become equal to 𝑎a,
  • NO otherwise.

You can output YES and NO in any case (for example, strings yEsyesYes and YES will be recognized as positive answer).

Example
input

Copy
5
4
2 4 5 24
1 4 6 11
3
1 4 17
4 5 31
5
4 7 10 13 14
2 14 14 26 42
5
2 2 4 4 4
28 46 62 71 98
6
1 2 10 16 64 80
20 43 60 74 85 99
output

Copy
YES
NO
YES
YES
YES

[Solution] Equate Multisets solution codeforces

The first example is explained in the statement.

In the second example, it is impossible to get the value 3131 from the numbers of the multiset 𝑏b by available operations.

In the third example, we can proceed as follows:

  • Replace 22 with 22=42⋅2=4. We get 𝑏={4,14,14,26,42}b={4,14,14,26,42}.
  • Replace 1414 with 142=7⌊142⌋=7. We get 𝑏={4,7,14,26,42}b={4,7,14,26,42}.
  • Replace 2626 with 262=13⌊262⌋=13. We get 𝑏={4,7,14,13,42}b={4,7,14,13,42}.
  • Replace 4242 with 422=21⌊422⌋=21. We get 𝑏={4,7,14,13,21}b={4,7,14,13,21}.
  • Replace 2121 with 212=10⌊212⌋=10. We get 𝑏={4,7,14,13,10}b={4,7,14,13,10}.
  • Got equal multisets 𝑎={4,7,10,13,14}a={4,7,10,13,14} and 𝑏={4,7,14,13,10}b={4,7,14,13,10}.

For Solution

Click Here

Leave a Comment