PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Yahor Dubovik
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
1945
PREREQUISITES:
None
PROBLEM:
You are given an array A = [A_1, A_2, \ldots, A_N], consisting of N integers. In one move, you can take two adjacent numbers A_i and A_{i+1}, delete them, and then insert the number A_i \land A_{i+1} at the deleted position. Here, \land denotes bitwise AND. Note that after this operation, the length of the array decreases by one.
Formally, as long as |A| \gt 1 (where |A| denotes the current length of A), you can pick an index 1 \leq i \lt |A| and transform A into [A_1, A_2, \ldots, A_{i-1}, A_i \land A_{i+1}, A_{i+2}, \ldots, A_{|A|}].
Find the minimum number of moves required to make all numbers in the resulting array equal.
EXPLANATION:
Let S = A_1 \land A_2 \land \dots \land A_N. Notice that after some operation that make all elements equal, it must be that each of these elements is equal of S. Our problem now is to find the minimum number of moves such that every element is equal to S. Stated differently, we need to divide A into as many partitions as possible, such that the AND of each partition is equal to S.
Observe that the following greedy strategy works:
- Repeatedly take the shortest prefix of A such that the AND of this prefix is equal to S, and partition this prefix out of A.
- We will be left with some elements such that their AND is not S. Simply merge them with the last partition created.
For example, on sample test case 3 with A = 1, 2, 3, 4, 5, 6, we have S = 0. Then the greedy strategy becomes the following:
- Smallest prefix with 0 AND is 1, 2, so we have the current partition [1, 2], 3, 4, 5, 6.
- Smallest next prefix with 0 AND is 3, 4, so we have the current partition [1, 2], [3, 4], 5, 6.
- Since we cannot make another good prefix, merge 5, 6 into the last partition, getting [1, 2], [3, 4, 5, 6].
We have 2 partitions, corresponding to 6 - 2 = 4 operations.
Intuitively, this greedy strategy works because whenever we get a prefix with AND S, adding more elements into this prefix will not change the AND at all (remember, S is AND of all elements). Therefore, we want to cut off early and leave more elements for later partitions.
TIME COMPLEXITY:
Time complexity is O(N) per test case.
SOLUTION:
Setter's Solution
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = 1e6 + 10;
int a[maxN];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("input.txt", "r", stdin);
int tst;
cin >> tst;
while (tst--) {
cin >> n;
int tot_and = (1 << 30) - 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
tot_and &= a[i];
}
int tot = (1 << 30) - 1;
int op = n - 1;
bool last = false;
for (int i = 1; i <= n; i++) {
tot &= a[i];
if (tot == tot_and && i != n) {
tot = (1 << 30) - 1;
op--;
}
}
if (tot != tot_and) {
op++;
}
cout << op << '\n';
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n;
ll m;
ll a[2000001];
void solve(){
cin >> n;
ll king=(1<<30)-1;
for(int i=1; i<=n ;i++){
cin >> a[i];king&=a[i];
}
int ptr=0;
int ans=0;
while(ptr<n){
ptr++;
ll cur=a[ptr];
while(ptr<n && cur!=king){
ptr++;cur&=a[ptr];
}
//cout<< ptr << ' ' << cur << endl;
if(cur==king) ans++;
else break;
}
cout << n-ans << '\n';
}
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
int tot = -1;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
tot &= a[i];
}
int ans = 0;
for (int i = 0, cur = -1; i < n; i++) {
cur &= a[i];
if (cur == tot) {
cur = -1;
ans++;
}
}
cout << n - ans << '\n';
}
}