PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pranjali07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
There are N dials, each with a digit between 1 and 9.
The i-th dial currently displays A_i, and you’d like it to be B_i.
In one move, you can either increase or decrease a digit on one dial by 1, with the digit moving cyclically.
Is it possible to satisfy all the N dials in exactly K moves?
EXPLANATION:
Let’s forget about the exactly K moves constraint for now, and just try to make the dials equal to what we want.
To convert A_i to B_i, we can:
- Move from A_i to B_i directly, one at a time. This takes |A_i - B_i| moves.
For example, to go from 8 to 2, this is the number of moves needed to do 8\to 7\to 6\to\ldots\to 2. - Move from A_i to B_i cyclically, essentially going the other way. This takes 9 - |A_i - B_i| moves.
For example, to go from 8 to 2, this is the number of moves needed to do 8\to 9\to 1\to 2. - So, the minimum number of moves is just \min(|A_i - B_i|, 9 - |A_i - B_i|).
So, the absolute minimum number of moves we can use, is
Let this be S.
If S \gt K, then we definitely can’t use exactly K moves to achieve our goal, so the answer is No.
What if S \leq K?
Well, suppose we’ve reached our goal using S moves.
Then, we can always “waste” two moves, by increasing some dial and then decreasing it.
So, we’ll always be able to use S, S+2, S+4, S+6, \ldots moves.
If K is one of them, i.e. if K - S is even, then we know the answer is Yes again.
What if K - S is odd then?
Here, we can use the fact that 9 is odd.
To reach S, we used \min(|A_i - B_i|, 9 - |A_i - B_i|) moves for each i.
If we instead used the other value, its parity (even/odd-ness) would change (though we’d also use more moves).
Let’s make one such move that changes parity - since we can choose, we choose the one that causes the least increase to S.
Let S' be the new number of moves made, which is also the least number of moves needed of this parity.
We can now mimic the initial setup, where we repeatedly move a dial up and down, so that we can make S', S'+2, S'+4, \ldots moves.
So, if K - S' is even and K \geq S' then we can certainly use exactly K moves, otherwise we can’t.
If either check above (with S or with S') pass, the answer is Yes, otherwise it’s No.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int sumn = 0;
void Solve()
{
int n, k; cin >> n >> k;
sumn += n;
assert(sumn <= 200000);
vector <int> a(n), b(n);
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
int sum = 0;
int diff = INF;
for (int i = 0; i < n; i++){
int v = abs(a[i] - b[i]);
v = min(v, 9 - v);
diff = min(diff, abs(v - (9 - v)));
sum += v;
}
if (sum > k){
cout << "NO\n";
return;
}
if (sum % 2 == k % 2){
cout << "YES\n";
return;
}
if (sum + diff <= k){
cout << "YES\n";
return;
}
cout << "NO\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mnsm, mnch = 0, 10
for i in range(n):
x = abs(a[i] - b[i])
mnsm += min(x, 9-x)
mnch = min(mnch, max(x, 9-x) - min(x, 9-x))
if mnsm <= k and (k - mnsm)%2 == 0: print('Yes')
elif mnsm + mnch <= k and (k - mnsm - mnch)%2 == 0: print('Yes')
else: print('No')