Exciting Arrays (Editorial)

Solution

Fact 1 : since we can apply the operation any number of times , we can rearrange both arrays as we want.

The condition [a_1 , a_2 , ... , a_n] = [b_1 , b_2 , ... , b_i] for each $i$ (1 \le i \le \text{min}(n,m)) means that the length of the longest common prefix between $a$ and $b$ should be equal to \text{min}(n,m).

Now , let $len$ be the length of the longest common prefix , freq[x][0] be the frequency of the number $x$ in the array $a$ and freq[x][1] be the frequency of the number $x$ in the array $b$.

Now if we want to increase $len$ by $y$ using a value $x$ , we should take $y$ elements with value $x$ from array $a$ , and $y$ elements with value $x$ from array $b$ , the maximum $y$ we can obtain is \text{min}(freq[x][0] , freq[x][1]) , so each number $x$ will increase $len$ by \text{min}(freq[x][0] , freq[x][1]).

After using all numbers $x$ where (1 \le x \le n+m) , if $len$ is equal to \text{min}(n,m) , answer is "YES" otherwise "NO".

Time complexity : \mathcal{O}(n+m).

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define F first
#define S second
using namespace std;
const int N = 2e5 + 1;
const int M = 1e9 + 7;
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int tc = 1;
    cin>>tc;
    while(tc--)
    {
        int n,m;
        cin>>n>>m;
        int freq[n+m+1][2] , len = 0;
        memset(freq , 0 , sizeof freq);
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            freq[x][0]++;
        }
        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            freq[x][1]++;
        }
        for(int i=1;i<=n+m;i++)
        {
            len += min(freq[i][0] , freq[i][1]);
        }
        cout<<(len == min(n , m) ? "YES" : "NO")<<endl;
    }
}