# DIGITOP - Editorial

Author: grayhathacker
Tester: abhidot
Editorialist: iceknight1093

1798

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;
}

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);
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);
assert(minv <= res);
assert(res <= maxv);
return res;
}

long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
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) {
}
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) {
}
return v;
}

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

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

assert((int) buffer.size() == pos);
}
};

input_checker inp;

int32_t main()
{
IOS;
int sm=0;
while(T--){
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);
}

}

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

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

[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???