DIGITOP - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: grayhathacker
Tester: abhidot
Editorialist: iceknight1093

DIFFICULTY:

1798

PREREQUISITES:

Observation

PROBLEM:

You’re given two integer arrays A and B of length N. In one move you can:

  • Pick 1 \leq i \lt j \leq N, and swap one digit of A_i with one digit of A_j. This operation is free.
  • Pick 1 \leq i \leq N, and replace some digit of A_i with some other digit. This operation has a cost of 1.

Find out whether you can make A = B with a cost of at most K.

EXPLANATION:

First, note that neither operation allows us to change the length of a string.
So, if len(A_i) \neq len(B_i) for some 1 \leq i \leq N, then making them equal is obviously impossible.

Now, note that the first operation allows us to freely rearrange the digits in A as we like, so our aim should be to just make sure that A and B have the same multiset of digits.

So, let \text{ct}_A[d] be the number of times digit d appears in A, and \text{ct}_B[d] be the same for B.

Let S = \sum_{d=0}^9 \max(0, \text{ct}_A[d] - \text{ct}_B[d]), i.e, S is the number of ‘extra’ digits that A has compared to B.
We need one operation to get rid of each of these digits, so we definitely need at least S operations of type 2.

It’s also not hard to see that we need exactly S operations of type 2 to make the multisets equal.

Proof

Recall that we ensured that A_i and B_i have equal lengths, right at the start.
So, the total number of digits in A equals the total number of digits in B.

In particular, for each digit that A has extra of, there will be some digit that it has a deficit of.
So, in one replace operation, we can turn an extra digit into one that we require.

This allows us to use exactly S operations so that A and B have the same multisets of digits, as required.

So, once S is computed, the answer is Yes if S \leq K and No otherwise.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (C++)
#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
typedef set<string> ss;
typedef vector<int> vs;
typedef map<int, char> msi;
typedef pair<int, int> pa;
typedef long long int ll;

ll n, k, i, j, val, ca[10], cb[10];
string a[100005], b[100005];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
	freopen("inputf.in", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int t;
	cin >> t;
	while (t--)
	{
		memset(ca, 0, sizeof(ca));
		memset(cb, 0, sizeof(cb));
		cin >> n >> k;
		for (i = 0; i < n; i++)
			cin >> a[i];
		for (i = 0; i < n; i++)
			cin >> b[i];
		for (i = 0; i < n; i++)
			if (a[i].length() != b[i].length())
				break;
		if (i != n)
			cout << "NO\n";
		else
		{
			for (i = 0; i < n; i++)
			{
				for (j = 0; j < a[i].length(); j++)
					ca[a[i][j] - '0']++;
				for (j = 0; j < b[i].length(); j++)
					cb[b[i][j] - '0']++;
			}
			val = 0;
			for (i = 0; i < 10; i++)
				val += max(0LL, cb[i] - ca[i]);
			if (val <= k)
				cout << "YES\n";
			else
				cout << "NO\n";
		}

	}

	return 0;
}
Tester's code (C++)


// Problem: Digit Operation
// Contest: CodeChef - STR84TST
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: abhidot

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ll long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mod 1000000007
#define mod2 998244353
#define lld long double
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define V vector
#define setbits(x) __builtin_popcountll(x)
#define w(x)  int x; cin>>x; while(x--)
using namespace std;
using namespace __gnu_pbds; 
template <typename num_t> using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;
const long long N=200005, INF=1000000000000000000, inf = 2e9+5, lim=1e18;
 
int power(int a, int b, int p){
	if(a==0)
	return 0;
	int res=1;
	a%=p;
	while(b>0)
	{
		if(b&1)
		res=(res*a)%p;
		b>>=1;
		a=(a*a)%p;
	}
	return res;
}
 
 
void print(bool n){
    if(n){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }
}

struct input_checker {
	string buffer;
	int pos;

	const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
	const string number = "0123456789";
	const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	const string lower = "abcdefghijklmnopqrstuvwxyz";

	input_checker() {
		pos = 0;
		while (true) {
			int c = cin.get();
			if (c == -1) {
				break;
			}
			buffer.push_back((char) c);
		}
	}

	int nextDelimiter() {
		int now = pos;
		while (now < (int) buffer.size() && buffer[now] != ' ' && buffer[now] != '\n') {
			now++;
		}
		return now;
	}

	string readOne() {
		assert(pos < (int) buffer.size());
		int nxt = nextDelimiter();
		string res;
		while (pos < nxt) {
			res += buffer[pos];
			pos++;
		}
		return res;
	}

	string readString(int minl, int maxl, const string &pattern = "") {
		assert(minl <= maxl);
		string res = readOne();
		assert(minl <= (int) res.size());
		assert((int) res.size() <= maxl);
		for (int i = 0; i < (int) res.size(); i++) {
			assert(pattern.empty() || pattern.find(res[i]) != string::npos);
		}
		return res;
	}

	int readInt(int minv, int maxv) {
		assert(minv <= maxv);
		int res = stoi(readOne());
		assert(minv <= res);
		assert(res <= maxv);
		return res;
	}

	long long readLong(long long minv, long long maxv) {
		assert(minv <= maxv);
		long long res = stoll(readOne());
		assert(minv <= res);
		assert(res <= maxv);
		return res;
	}

	auto readIntVec(int n, int minv, int maxv) {
		assert(n >= 0);
		vector<int> v(n);
		for (int i = 0; i < n; ++i) {
			v[i] = readInt(minv, maxv);
			if (i+1 < n) readSpace();
			else readEoln();
		}
		return v;
	}

	auto readLongVec(int n, long long minv, long long maxv) {
		assert(n >= 0);
		vector<long long> v(n);
		for (int i = 0; i < n; ++i) {
			v[i] = readLong(minv, maxv);
			if (i+1 < n) readSpace();
			else readEoln();
		}
		return v;
	}

	void readSpace() {
		assert((int) buffer.size() > pos);
		assert(buffer[pos] == ' ');
		pos++;
	}

	void readEoln() {
		assert((int) buffer.size() > pos);
		assert(buffer[pos] == '\n');
		pos++;
	}

	void readEof() {
		assert((int) buffer.size() == pos);
	}
};

input_checker inp;
 
 
int32_t main()
{
    IOS;
    int sm=0;
		int T=inp.readInt(1, 1000);
		inp.readEoln();
		while(T--){
			int n=inp.readInt(2, 100000);
			inp.readSpace();
			int k=inp.readLong(1, INF);
			inp.readEoln();
			vector<int> a = inp.readLongVec(n, 1, INF);
			vector<int> b = inp.readLongVec(n, 1, INF);
			sm+=n;
			assert(sm<=100000);
			int f[10]={0};
			int ok=1;
			for(int i=0;i<n;i++){
				string s = to_string(a[i]);
				for(auto c: s){
					f[c-'0']--;
				}
				string ss = to_string(b[i]);
				for(auto c: ss){
					f[c-'0']++;
				}
				ok&=(s.size()==ss.size());
			}
			
			int cnt=0;
			for(int i=0;i<10;i++) cnt+=max(f[i], 0LL);
			ok&=(cnt<=k);
			print(ok);
		}
		
		inp.readEof();
}
Editorialist's code (Python)
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 'Yes'
    for i in range(n):
        if len(str(a[i])) != len(str(b[i])): ans = 'No'
    
    dif = [0]*10
    for x in a:
        for d in str(x): dif[ord(d) - ord('0')] += 1
    for x in b:
        for d in str(x): dif[ord(d) - ord('0')] -= 1
    reqd = sum(x for x in dif if x > 0)
    if reqd > k: ans = 'No'
    print(ans)
2 Likes

Let’s say the test case is something like -:

1
2 1
123 4567
321 7654

What should be the minimum cost of making them equal?
6 right? Because of this statement “Choose 2 indices i and j * (i != j) * and swap any character of A[i] with any character of A[j]” So we can’t choose i and j both to be equal

and btw this is my AC submission which prints NO (which should be correct answer) -: CodeChef: Practical coding for everyone

and setter’s solution is printing “YES” (which should be wrong answer)

So was it some typo or wrong question or have I misunderstood something??

Please reread the statement, the swap operation has a cost of zero so you can do it as many times as you like.

For example you can do

[123, 4567] -> [423, 1567] -> [421, 3567] -> [321, 4567]

to swap 1 and 3 in the first string without any cost.

This is also why the constraints have N \geq 2 :slightly_smiling_face:

Oh yes right right my bad
Thanks for clarifying

what will be the answer in this case??
1
2 1
38 45
83 45
I think NO? as we cannot swap 3 with 8 as (i!=j) so the cost will be 2 as we have to change first 3 to 8 and second 8 to 3.
but setter’s solution giving YES
please clarify

[38, 45] -> [48, 35] -> [43, 85] -> [83, 45]

understood thanx

If I am not wrong, setter’s solutions counts, the number of extra digits that “B” has as compared to A.

Bcz of :

	for (i = 0; i < 10; i++)
				val += max(0LL, cb[i] - ca[i]);

Those values are the same.

Since we ensured that A_i and B_i have the same length, the total number of digits across A and B is the same.
So, sum(\text{freq}_A[d]) = sum(\text{freq}_B[d]), which means sum(\text{freq}_A[d] - \text{freq}_B[d]) = 0.
This means the sum of positives equals the (absolute) sum of negatives, so it doesn’t really matter which one you count.

1 Like

Thanks for the clarification.

I got AC even when my code had typing errors, i went ahead and removed the entire logic just to test it out and still got AC is the judge broken? Even when i thought i submitted the correct code i had 1 written instead of i while accessing map so technically all my answers are wrong

S = ∑ digit =0 to 9 sum(ct A[d]−ct B[d])
I had calculated S as above mentioned and i divided S by 2 and checked whether S <= K. I got os as wrong could anyone explain why?

3 1
1 9 6
2 8 7
Setter code - No
other accepted submission - Yes
More Testcase needed???