RSLN2205 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Subsequence and Bitwise &

Setter, Tester & Editorialist: Tushar Gupta

DIFFICULTY

Easy-Medium

PREREQUISITES

Dynamic Programming, Bitwise Operations

PROBLEM

You are given a list A of length N of non-negative integers. You need to find the length of the longest subsequence of A such that the binary representation of bitwise and of all of its elements contains at least K set bits.

EXPLANATION

First, we use dynamic programming to find out the maximum possible length of all such subsequences that the bitwise & of all its elements contain at least K set bits. Then, we just need to calculate the maximum among all such lengths.

TIME COMPLEXITY

The worst-case time complexity is O(N*128) per test case.

SOLUTION

Tushar Gupta 
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	while ( t-- ) {
		int n, k;
		cin >> n >> k;
		int x;
		int ans[128];
		memset ( ans, 0, sizeof ( ans ) );
		while ( n-- ) {
			cin >> x;
			for ( int i = 0; i < 128; i++ ) {
				if ( ans[i] > 0 ) {
					int nd = x & i;
					ans[nd] = max ( ans[nd], ans[i] + 1 );
				}
			}
			ans[x] = max ( ans[x], 1 );
		}
		int mx = 0;
		int kk = 0;
		while ( kk < 128 ) {
			if ( __builtin_popcount ( kk ) >= k ) {
				mx = max ( ans[kk], mx );
			}
			kk++;
		}
		cout << mx << '\n';
	}
}