ANDEQ - Editorial

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';
    }
}
9 Likes

Any one who is unable to understand why we assumed S as the Bitwise And of all the elements in the array like me , below is the explanation of the query :

A property of bitwise and is c & c = c

Lets say we have a array of 6 elements a1,a2,a3,a4,a5 and a6

Let the equal value to be reached is X

Let a1 & a2 = X , a3 = X and a4 & a5 & a6 = X

So , a1 & a2 & a3 & a4 & a5 & a6 =X

9 Likes

Because in the final state of array , only those bits will be set which will be on in n numbers and that is essentially AND of the array.

Can anyone please provide an strong test case for this problem?

I don’t think you should try to approach the problem by using different test cases, cause it will increase the overall complexity for you to come up with a solution. Problems like this should be solved by assuming variables and assuming that these 2 variables will give an & as a third variable which will be equal to S. You can assume all the possibilities and I guess this helps us to come up with intuition faster. Hope this helps!!

1 Like

can anyone please elaborate the editorial more , I am not getting understand …

A property of bitwise and is c & c = c

Lets say we have a array of 6 elements a1,a2,a3,a4,a5 and a6

Let the equal value to be reached is X

Let a1 & a2 = X , a3 = X and a4 & a5 & a6 = X

So , a1 & a2 & a3 & a4 & a5 & a6 =X

So now all we need to check how many consecutive partitions we will end up with to come to the value X . Here with the example of a1,a2,…,a6 there are 3 partitions .

So the total no of bitwise and to be done is 5 - 2 = 3 . ( n - 1 - partitions -1 ) β€” (1)

How to come up with the formula in statement 1 - The maximum bitwise and we could have done to end up with exactly 1 element is n-1 . The no of bitwise and we are going to skip because of the partition is partition - 1 . So the total no of bitwise operations to be done is ( n -1 - partition -1 )

2 Likes

On merging elements to the last set of elements it will not necessarily make AND = X if s!=0. then??

Why my code is give ac for all test cases. I brute forced for all values i from 0 to 255 and tried to divide the given array into segments such that all the segments have the AND value as i and took minimum of all cases.
Submission link: Solution: 64911508 | CodeChef

β€˜β€™β€™#include<bits/stdc++.h>

using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 1000000007
#define MOD1 998244353
#define INF 1e18
#define nline β€œ\n”
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template void _print(vector v);
template void _print(set v);
template <class T, class V> void _print(map <T, V> v);
template void _print(multiset v);
template <class T, class V> void _print(pair <T, V> p) {cerr << β€œ{”; _print(p.ff); cerr << β€œ,”; _print(p.ss); cerr << β€œ}”;}
template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << β€œ]”;}
template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << β€œ]”;}
template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << β€œ]”;}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << β€œ]”;}

ll i, t, n;
void solve()
{
fastio();
cin >> n;
vectorv(n);
ll a = (1LL<<31)-1;
for (i = 0; i < n; i++)
{
cin >> v[i];
a = a & v[i];
}
if (n == 2)
{
if (v[0] == a && v[1] == a)
cout << 0 << endl;
else
cout << 1 << endl;
return;
}
ll prev_N = v[0];
ll sum=0;
i = 0;
ll count = 0;
debug(a);
while (i < n) {
if (prev_N == a)
{
sum+=count;
count = 0;
if (i + 1 < n && v[i] == a)
{
prev_N = v[i + 1];
i++;
}
else
{
prev_N = v[i];

		}

	}
	else {
		prev_N = prev_N & v[i];
		if(i)
			count++;
	}
	cerr << "count :: " << count << "  i :: " << i << endl;
	i++;
}

if (prev_N == a)
	sum+=count;
else
	sum+=count+1;
debug(sum);
cout << sum<< endl;

}

int main() {
#ifndef ONLINE_JUDGE
freopen(β€œError.txt”, β€œw”, stderr);
#endif

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
while (t--)
{
	solve();
}
return 0;

}’’'pls help me . my code is giving tle in subtask 3.

1 Like

Weak test cases nothing else…

1 Like

How to understand this statement β€œIntuitively, this greedy strategy works because whenever we get a prefix with AND SS, adding more elements into this prefix will not change the AND at all (remember, SS is AND of all elements). Therefore, we want to cut off early and leave more elements for later partitions.”??
I do not get it.

2 Likes