Digit Operation Solution


Problem

You are given arrays � and �, each consisting of � strings, and a positive integer �.
For all 1≤�≤�, both �� and �� consist of characters from 0 to 9 (both inclusive).

You can perform the following types of operations on array �:

  • Type 1: Choose two indices � and � (�≠�) and swap any character of �� with any character of ��. The cost of this operation is 0.
  • Type 2: Choose an index � and replace one character of �� with any character from 0 to 9 (both inclusive). The cost of this operation is 1.

For example, let �=[24,30,51]. A valid sequence of operations can be:

  • Swap 4 in �1=24 with 0 in �2=30 to obtain [20,34,51].
  • Swap 0 in �1=20 with 5 in �3=51 to obtain [25,34,01].
  • Replace 0 in �3=01 with 1 to obtain [25,34,11].
    The cost of the above sequence of operations is 1.

Find whether we can convert the array � to array � using any (possibly zero) number of operations with cost ≤�.

Input Format

  • The first line of input will contain a single integer �, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains two space-separated integers � and �, the size of array and the maximum cost of operations.
    • The second line of each test case contains � space-separated strings �1,�2,…,��.
    • The third line of each test case contains � space-separated strings �1,�2,…,��.

Output Format

For each test case, print YES if it is possible to convert array � to � using any (possibly zero) number of operations with cost ≤�. Else, print NO.

You may print each character of the string in uppercase or lowercase (for example, the strings yEs, yes, Yes, and YES will all be treated as identical).

Constraints

  • 1≤�≤1000
  • 2≤�≤105
  • 1≤�≤1018
  • 1≤∣��∣,∣��∣≤19
  • �� and �� consist of characters from 0 to 9 (both inclusive).
  • The sum of � over all test cases won't exceed 105.

Sample 1:

Input
Output
3
2 2
1 9
9 1
2 2
1 11
11 1
4 1
22 13 12 89
28 98 21 31
YES
NO
YES

Explanation:

Test case 1: We can use one operation of type 1 to swap 1 in �1 with 9 in �2. Thus, � becomes [9,1], which is equal to �. We are able to do this with 0 cost, which is ≤2.

Test case 2: It is impossible to convert � to � with at most 2 cost.



#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
#define scanit(a,n) for(ll indexaa=0; indexaa<n; indexaa++) cin>>a[indexaa];

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve() {

int n,k;
cin>>n>>k;

vector<string>v(n),b(n);

for (int i = 0; i < n; i++)
{
    cin>>v[i];
}

for (int i = 0; i < n; i++)
{
    cin>>b[i];
}



map<char,map<char,int>>m;

for (int i = 0; i < n; i++)
{
    if(v[i].length()!=b[i].length()){
        cout<<"NO\n";
        return;
    }
    for (int j = 0; j < v[i].size(); j++)
    {
        if(v[i][j]!=b[i][j])m[v[i][j]][b[i][j]]++;
    }
}

for (int i = 0; i < n; i++)
{
    for (int j = 0; j < v[i].size(); j++)
    {
        if(v[i][j]!=b[i][j]){
            if(m[b[i][j]][v[i][j]]>0){
                m[b[i][j]][v[i][j]]--;
            }
            else k--;
        }
    }
    
}


if(k<0)cout<<"NO\n";
else cout<<"YES\n";




}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
  cin >> t; 
  while (t--) solve();



  return 0;
}