PROBLEM LINK:
Author & Editorialist: Saurabh Yadav
DIFFICULTY:
Easy
PREREQUISITES:
Bitwise operation, DSU, or BFS/DFS on graph
PROBLEM:
Given a graph with N nodes(represented by cities) where i^{th} node has weight of w_{i} and M bidirectional edges(represented by roads between cities).
You are given Q queries, each query can be of two types:
- 1 K - print the size of largest connected group of cities in which parity of each city is odd after XOR with K.
- 2 K - print the size of largest connected group of cities in which parity of each city is even after XOR with K.
Let the parity of a city c_{i} be even if the number of set bits in its binary representation of w_{i} is even and odd otherwise.
QUICK EXPLANATION:
- We only have to initially precompute the size of the largest connected group having an odd parity and vice-versa.
A group of cities is said to be connected if we can go from one city of the group to any other city of the group without passing through any city that is not in the group. A group with one city is considered as connected.
EXPLANATION:
There is a very important observation:
- Bitwise XOR of odd parity and odd parity is an even parity.
- Bitwise XOR of odd parity and even parity is an odd parity, vice-versa.
- Bitwise XOR of even parity and even parity is an even parity.
How can we prove this?
Suppose N is the number of set bits in the first number and M is set bits in the second number.
Then set bits in XOR of these two numbers is N+M - 2 (Δ) where is delta is the total number of bit positions where both of numbers have set bit. Now this expression explains everything.
even + odd - even = odd
odd + odd - even = even
even + even - even = even
Let’s first find the answer for query of type 1:
- For query of type 1, given K we have to find the size of the largest connected group of cities in which the parity of each city is Odd after XOR with K.
- So let’s first consider that K's parity is odd then the size of the largest connected group having odd parity after XOR with K would be the size of the largest connected group of even parity because Odd parity \oplus Even parity = Odd parity.
- Now when K's parity is even then the size of the largest connected group having odd parity after XOR with K, would be the size of the largest connected group of odd parity, because Even parity \oplus Odd parity = Odd parity.
Now similarly we can find the answer for query of type 2:
- For query of type 2, given K we have to find the size of the largest connected group of cities in which the parity of each city is even after XOR with K.
- So let’s first consider K's parity is odd then the size of the largest connected group having even parity after XOR with K would be the size of the largest connected group of odd parity because, Odd parity \oplus Odd parity = Even parity.
- Now when K’s parity is even then the size of the largest connected group having even parity after XOR with K would be the size of the largest connected group of even parity because, Even parity \oplus Even parity = Even parity.
Now we are left with the problem to select the largest number of cities such that parity of each node is either odd/even and the selected subset is reachable from each other. We can use either DFS or Disjoint Set Union, to find the size of the largest connected group having all the node’s parity either as odd or even.
How to find the number of set bits in an integer?
As for finding the number of set bits in an integer, we can use the standard algorithm for finding the digits for a number in any base (in this case the base is 2). The code is below:
def countSetBits(n):
count = 0
while (n):
count += n & 1
n >>= 1
return count
}
-
Library Functions for C++:
- _builtin_popcount() : This function is used to count the number of one’s(set bits) in an integer
- _builtin_parity(x): This function is used to check the parity of a number. This function returns true(1) if the number has odd parity else it returns false(0) for even parity.
-
Library functions for Java:
- Integer.bitCount(x) - The bitCount() method of Integer class of java.lang package returns the count of the number of one-bits in the two’s complement binary representation of an int value. This function is sometimes referred to as the population count.
-
Inbuilt List comprehension in Python :
- bin(x)[2:].count(‘1’) - Counts the total number of set bits.
TIME COMPLEXITY:
Time: O(N+M) per test case
Space: O(N+M)
SOLUTIONS:
Setter's solution(Uses DFS approach)
#include <bits/stdc++.h>
using namespace std;
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loopb(i,a,b) for(int i=a;i>=b;i--)
#define fore(name) for(auto it=name.begin();it!=name.end();it++)
#define w int t;cin>>t;while(t--)
#define pb(x) push_back(x)
#define in(y) insert(y)
#define bitscount 32
#define make(x,y) make_pair(x,y)
#define LOAD_FACTOR_set(name) name.reserve(32768);name.max_load_factor(0.25);
#define LOAD_FACTOR_map(name) name.reserve(1024);name.max_load_factor(0.25);
#define lcm(a,b) ((a*b))/(__gcd(a,b))
#define int long long int
#define REDBULL ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define MAX 200001
vector<int> graph[MAX];
bool visited[MAX];
int weight[MAX];
int ans;
void dfs(int u, int check)
{
visited[u] = true;
for (auto it : graph[u])
{
if (!visited[it] && __builtin_parity(weight[it]) == check)
{
ans++;
dfs(it, check);
}
}
}
int32_t main()
{
REDBULL
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
visited[i] = false;
graph[i].clear();
}
for (int i = 1; i <= n; i++ )
cin >> weight[i];
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
graph[u].pb(v);
graph[v].pb(u);
}
// evenP stores the size of the largest connected
// group having the parity of all nodes as even
// oddP stores the size of largest connected
// group having the parity of all nodes as odd
int evenP = 0, oddP = 0;
for (int i = 1; i <= n; i++)
{
if (!visited[i])
{
if ( __builtin_parity(weight[i]) == false)
{
ans = 1;
dfs(i, 0);
evenP = max(evenP, ans);
}
else {
ans = 1;
dfs(i, 1);
oddP = max(oddP, ans);
}
}
}
int q;
cin >> q;
while (q--)
{
int c, k;
cin >> c >> k;
if (c == 1)
{
if (__builtin_parity(k))
cout << evenP << endl;
else
cout << oddP << endl;
}
else
{
if (__builtin_parity(k))
cout << oddP << endl;
else
cout << evenP << endl;
}
}
}
return 0;
}
Tester's solution(Uses DSU approach)
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define MP make_pair
#define PB push_back
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
#define ld long double
const int mod = 1000000007;
const int INF = 1e18;
int n, m;
int b[2];
#define SZ 200005
int A[SZ], sz[SZ];
void init(int n)
{
f(i, 0, n + 1)
{
sz[i] = 1;
A[i] = i;
}
}
int find(int i)
{
while (A[i] != i)
{
A[i] = A[A[i]];
i = A[i];
}
return i;
}
int _union(int xr, int yr)
{
xr = find(xr), yr = find(yr);
if (xr == yr)
return -1;
if (sz[xr] < sz[yr])
{
A[xr] = A[yr];
sz[yr] += sz[xr];
}
else
{
A[yr] = A[xr];
sz[xr] += sz[yr];
}
return 0;
}
int w[200005];
int par(int i) {
int cnt = 0;
f(j, 0, 31)
if ((1ll << j)&i)
cnt ^= 1;
return cnt;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
cin >> n >> m;
init(n + 2);
b[0] = b[1] = 0;
f(i, 1, n + 1)
{
cin >> w[i];
w[i] = par(w[i]);
}
f(i, 0, m) {
int u, v;
cin >> u >> v;
if (w[u] == w[v])
{
_union(u, v);
b[w[u]] = max(b[w[u]], sz[find(u)]);
}
}
int q;
cin >> q;
while (q--) {
int type, k;
cin >> type >> k;
k = par(k);
type--;
while (k > 1)
k = k % 2 + k / 2;
cout << b[type ^ k ^ 1] << '\n';
}
}
return 0;
}