Best Subsequence
Contest: Educational Codeforces Round 171 (Rated for Div. 2)
Difficulty rating: 2500
Tags: bitmasks, dfs and similar, flows, graph matchings, graphs

Given an integer array $$$a$$$ of size $$$n$$$.

Let's define the value of the array as its size minus the number of set bits in the bitwise OR of all elements of the array.

For example, for the array $$$[1, 0, 1, 2]$$$, the bitwise OR is $$$3$$$ (which contains $$$2$$$ set bits), and the value of the array is $$$4-2=2$$$.

Your task is to calculate the maximum possible value of some subsequence of the given array.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 2^{60}$$$).

Output format:
For each test case, print the maximum possible value of some subsequence of the given array.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
3
0 0 0
4
1 0 1 2
1
5
8
7 1 48 14 13 8 7 6

Example output:
3
2
0
3

Editorial:
Let the number of chosen elements be $$$k$$$, and their bitwise OR be $$$x$$$. The answer is equal to $$$k - popcount(x)$$$, where $$$popcount(x)$$$ is the number of bits equal to $$$1$$$ in $$$x$$$.
However, we can rewrite $$$popcount(x)$$$ as $$$60 - zeroes(x)$$$, where $$$zeroes(x)$$$ is equal to the number of bits equal to $$$0$$$ among the first $$$60$$$ bits in $$$x$$$. So, we have to maximize the value of $$$k + zeroes(x)$$$.
Consider the following bipartite graph: the left part consists of elements of the given array, the right part consists of bits. An edge between vertex $$$i$$$ from the left part and vertex $$$j$$$ from the right part means that the $$$j$$$-th bit in $$$a_i$$$ is set to $$$1$$$.
Suppose we've chosen a set of vertices in the left part (the elements of our subsequence). The bits which are equal to $$$0$$$ in the bitwise OR are represented by such vertices $$$j$$$ such that no chosen vertex from the left part is connected to $$$j$$$. So, if we unite the chosen vertices from the left part with the vertices in the right part representing bits equal to $$$0$$$, this will be an independent subset of vertices.
Thus, our problem is reduced to finding the maximum size of the independent subset of vertices. Usually, this problem is NP-complete. However, our graph is bipartite. So, we can use the following:
• by Konig's theorem, in a bipartite graph, the size of the minimum vertex cover is equal to the size of the maximum matching;
• and in every graph, independent subsets and vertex covers are complements of each other (if $$$S$$$ is a vertex cover, then the set of all vertices not belonging to $$$S$$$ is an independent subset, and vice versa). So, the maximum independent subset is the complement of the minimum vertex cover.
It means that we can calculate the size of the maximum independent subset as $$$V - MM$$$, where $$$V$$$ is the number of vertices in the graph, and $$$MM$$$ is the size of the maximum matching. We can compute $$$MM$$$ using any maximum matching algorithm or network flow.