PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: sushil2006
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given an array A.
You can perform the following operation:
- Choose an integer X (1 \leq X \lt 2^{30}) and a subarray of A.
Then, either XOR every element of the subarray with X, or replace every element with its GCD with X.
Find the minimum number of moves to make every element of A equal to K.
EXPLANATION:
Observe that it’s always possible to use two operations to achieve our goal:
- First, choose L = 1, R = N (i.e the entire array) and X = 1, and replace every element with \gcd(A_i, X).
Since X = 1, this will set every element to 1. - Then, choose L = 1, R = N and X = 1\oplus K, and replace every element with A_i \oplus X.
Since 1 \oplus (1 \oplus K) = K (note that 1\oplus 1 = 0), and all A_i are 1, this will set every element to K.
We want to find the minimum number of operations, which as we now know is certainly \leq 2.
That means we only need to check whether it can be 0 or 1.
Checking whether 0 operations are required is trivial: the entire array should already be equal to K.
That leaves us with checking for whether a single operation is enough.
We now have two possibilities: we can use either a GCD operation, or a XOR operation.
Let’s look at each of them separately.
GCD
Suppose we perform a GCD operation on the subarray [L, R] with X, and all the elements are equal to K afterward.
Then,
- For i \lt L or i \gt R, A_i = K should already hold; since their values don’t change.
- For L \leq i \leq R, we have \gcd(A_i, X) = K.
That tells us that:- A_i is a multiple of K.
- X is a multiple of K.
In particular, observe that every element of A must be a multiple of K: the elements inside the chosen subarray are themselves multiples of K due to the GCD condition; and the elements outside it are all K anyway.
If every element is a multiple of K, choosing X = K and using the GCD operation on the entire array will turn every element into K.
So, all we need to do here is check whether every element of A is a multiple of A, which only requires a simple loop.
XOR
Similarly, suppose we perform a XOR operation on [L, R] with X.
All elements outside this subarray should already be K, of course.
Then, for each L \leq i \leq R, we want A_i \oplus X = K.
This in turn means that A_i = K \oplus X.
In other words, all the elements of the subarray from L to R must be equal.
So, if a single XOR operation is to suffice, all the elements of A that are not equal to K should be equal, and also form a single subarray.
Every necessary check can be performed in linear time quite easily, so perform them to decide if the answer is 0 or 1, otherwise print 2.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case)
{
ll n,k; cin >> n >> k;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
ll first_bad = inf2, last_bad = -inf2;
rep1(i,n){
if(a[i] != k){
amin(first_bad,(ll)i);
last_bad = i;
}
}
if(first_bad == inf2){
cout << 0 << endl;
return;
}
bool ok = true;
for(int i = first_bad+1; i <= last_bad; ++i){
if(a[i] != a[first_bad]){
ok = false;
break;
}
}
if(ok){
cout << 1 << endl;
return;
}
ok = true;
rep1(i,n){
if(gcd(a[i],k) != k){
ok = false;
break;
}
}
if(ok){
cout << 1 << endl;
return;
}
cout << 2 << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
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());
void Solve()
{
int n, k; cin >> n >> k;
vector <int> a(n);
for (auto &x : a) cin >> x;
bool solved = true;
for (auto x : a){
solved &= (x == k);
}
if (solved){
cout << 0 << "\n";
return;
}
int p = 0;
int q = n - 1;
while (a[p] == k){
p++;
}
while (a[q] == k){
q--;
}
int g = 0;
int mn = a[p], mx = a[p];
for (int i = p; i <= q; i++){
g = __gcd(g, a[i]);
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
if (g % k == 0 || mn == mx) cout << 1 << "\n";
else cout << 2 << "\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)
import math
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
if min(a) == max(a) == k: print(0)
else:
ans = 2
L, R = n, 0
g = a[0]
for i in range(n):
g = math.gcd(g, a[i])
if a[i] != k: L, R = min(L, i), max(R, i)
x = a[L] ^ k
for i in range(L, R+1): a[i] ^= x
if g%k == 0 or min(a) == max(a) == k: ans = 1
print(ans)