 # PROBLEM LINK:

Author & Editorialist: Saurabh Yadav

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;

#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;
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 = b = 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;
}
``````
6 Likes

There is a typo in the contest link.

1 Like

Thanks for pointing out!

https://www.codechef.com/viewsolution/37002426
i think i did almost same way…but i got WA. what’s wrong in my code ? please help me to find out…thanks

in the explanation of the problem in second query - The size of the largest connected group of cities in which parity of each city is odd after XOR with 8 is equal to 4 because, after XOR with 8, cities 2,1,5,3,6 have odd parity. Since 2 is not connected with either 1,5,3, or 6, therefore answer is equal to 4. weight of city 2 is 4 . 4 XOR 8 =12 (1100) how is this parity odd
@sau

correct during contest too I was thinking about this statement. I spent a lot of time on this.

in dfs function why you have written
if (!visited[it] && __builtin_parity(weight[it]) == check)
won’t you make your ans 0 otherwise ,i mean if we have encountered some mismatching parity wont the ans be 0 in that case

ya they should have a ask ques during contest thing in Codechef like in CF

2 Likes

the concept of odd even parity and its xor operation takes my whole day to find that formula in lon g challenge.
Even parity xor Even parity = Even parity .
odd parity xor odd parity = Even parity.
odd parity xor Even parity = odd parity
Even parity xor odd parity = odd parity

Can someone please see where i did wrong here ?
https://www.codechef.com/viewsolution/36993607

First i found values of largest even and odd connected parity nodes using dfs(respectively in variables e and o).
Then answered queries using same method.

the way u are counting connected components is wrong.
try this
1
5 4
4 6 9 10 2
1 2
1 3
1 4
2 5
0(queries-let it be any value)
ur even value is 2 (it should be 1)
ur odd value is 3(it shoud be also 1)
consider connected components only not all

3 Likes

why ans is coming wrong using the editorial ans

Thank you bro.
Now i got it where i did mistake.

Can anyone point out where am going wrong.

https://www.codechef.com/viewsolution/37058335

Thanks

Dry run your DFS, to make sure it’s correct.

1 Like

Thanks ,
This really helped what i was missing.

Thanks . Figured out what i was missing.

Anytime you are stuck with WA then just write a code which generates input randomly.
Pass that input to your program, and the one written by author.
compare the results
Ofcourse doing it manually is a very tedious job, so writing a script to perform above task is recommended.
Here is my script (for linux / wsl on windows)

#!/bin/bash
while((1))
do
python3 tmp.py > /dev/shm/testcase
a=\$(diff <(./my < /dev/shm/testcase) <(./chef < /dev/shm/testcase) | wc -l)
if((\$a!=0))
then
cat /dev/shm/testcase
read p
fi
done

I am using Python3 , i did similair approach using BFS , i first find connect components and max odd and even size then wrt parity of input K , i print either odd or even. but i my solutin says Run Time error. I am new to competative programming., can someone help please!!!

https://www.codechef.com/viewsolution/37212495

sir, in the question they said Bidirectional so the graph is non directed so entire [1,2,3,4,5] are connected component only. so even value is 2 odd value is 3 , I don’t know how it will be 1 for both??? I am new to Competitive programming could you please Help!!!

I use Python3
https://www.codechef.com/viewsolution/37212495