# CENS20E - Editorial

**URL:** <https://discuss.codechef.com/t/cens20e-editorial/75412>\
**Category:** editorial\
**Tags:** editorial, cens2020, saurabhshadow\
**Created:** [August 19, 2020, 6:06pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412 "2020-08-19T18:06:09Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![saurabhshadow](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabhshadow/32/347886_2.png) [@saurabhshadow](https://discuss.codechef.com/u/saurabhshadow)\
**Post date:** [August 19, 2020, 6:06pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/1 "2020-08-19T18:06:09Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/CENS20E)  
[Contest](https://www.codechef.com/CENS2020/problems/CENS20E)

_Author & Editorialist:_ [Saurabh Yadav](https://www.codechef.com/users/saurabhshadow)

# 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](https://en.wikipedia.org/wiki/Bitwise_operation#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**](https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/) or [**Disjoint Set Union**](https://cp-algorithms.com/data_structures/disjoint_set_union.html), 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:
> 
> ```auto
> def countSetBits(n): 
> count = 0
> while (n): 
> count += n & 1
> n >>= 1
> return count 
> }
> 
> ```
> 
> - Library Functions for _C++_:
> 
> - Library functions for _Java_:
> 
> - Inbuilt List comprehension in _Python_ :
> 
> ```auto
> 
> ```

# TIME COMPLEXITY:

**Time** : O(N+M) per test case  
**Space** : O(N+M)

# SOLUTIONS:

> **Setter's solution(Uses DFS approach)**
>
> ```auto
> #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)**
>
> ```auto
> #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;
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![therealnishuz](https://discuss.codechef.com/user_avatar/discuss.codechef.com/therealnishuz/32/169792_2.png) [@therealnishuz](https://discuss.codechef.com/u/therealnishuz)\
**Post date:** [August 19, 2020, 6:24pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/2 "2020-08-19T18:24:11Z")

</div>

There is a typo in the contest link.

---

<div class="post-metadata">

**Author:** ![saurabhshadow](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabhshadow/32/347886_2.png) [@saurabhshadow](https://discuss.codechef.com/u/saurabhshadow)\
**Post date:** [August 19, 2020, 6:27pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/3 "2020-08-19T18:27:00Z")

</div>

Thanks for pointing out!

---

<div class="post-metadata">

**Author:** ![naeem4265](https://discuss.codechef.com/user_avatar/discuss.codechef.com/naeem4265/32/3653_2.png) [@naeem4265](https://discuss.codechef.com/u/naeem4265)\
**Post date:** [August 19, 2020, 6:42pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/4 "2020-08-19T18:42:30Z")

</div>

[https://www.codechef.com/viewsolution/37002426](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

---

<div class="post-metadata">

**Author:** ![ishanmay8](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ishanmay8/32/3653_2.png) [@ishanmay8](https://discuss.codechef.com/u/ishanmay8)\
**Post date:** [August 20, 2020, 3:13am UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/5 "2020-08-20T03:13:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![askswaraj](https://discuss.codechef.com/user_avatar/discuss.codechef.com/askswaraj/32/15568_2.png) [@askswaraj](https://discuss.codechef.com/u/askswaraj)\
**Post date:** [August 20, 2020, 4:22am UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/6 "2020-08-20T04:22:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![adnanshamsi](https://discuss.codechef.com/user_avatar/discuss.codechef.com/adnanshamsi/32/212311_2.png) [@adnanshamsi](https://discuss.codechef.com/u/adnanshamsi)\
**Post date:** [August 20, 2020, 7:38am UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/7 "2020-08-20T07:38:00Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ishanmay8](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ishanmay8/32/3653_2.png) [@ishanmay8](https://discuss.codechef.com/u/ishanmay8)\
**Post date:** [August 20, 2020, 9:21am UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/8 "2020-08-20T09:21:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![tanujyadav007](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tanujyadav007/32/33005_2.png) [@tanujyadav007](https://discuss.codechef.com/u/tanujyadav007)\
**Post date:** [August 20, 2020, 10:06am UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/9 "2020-08-20T10:06:01Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![taipon12](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taipon12/32/26382_2.png) [@taipon12](https://discuss.codechef.com/u/taipon12)\
**Post date:** [August 20, 2020, 3:54pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/11 "2020-08-20T15:54:12Z")

</div>

Can someone please see where i did wrong here ?  
[https://www.codechef.com/viewsolution/36993607](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.

---

<div class="post-metadata">

**Author:** ![deadman\_002](https://discuss.codechef.com/user_avatar/discuss.codechef.com/deadman_002/32/208155_2.png) [@deadman\_002](https://discuss.codechef.com/u/deadman_002)\
**Post date:** [August 20, 2020, 4:50pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/12 "2020-08-20T16:50:26Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ronit2018](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ronit2018](https://discuss.codechef.com/u/ronit2018)\
**Post date:** [August 20, 2020, 8:56pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/13 "2020-08-20T20:56:12Z")

</div>

why ans is coming wrong using the editorial ans

---

<div class="post-metadata">

**Author:** ![taipon12](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taipon12/32/26382_2.png) [@taipon12](https://discuss.codechef.com/u/taipon12)\
**Post date:** [August 21, 2020, 12:29pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/14 "2020-08-21T12:29:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![partha2717](https://discuss.codechef.com/user_avatar/discuss.codechef.com/partha2717/32/20510_2.png) [@partha2717](https://discuss.codechef.com/u/partha2717)\
**Post date:** [August 22, 2020, 5:20pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/15 "2020-08-22T17:20:30Z")

</div>

Can anyone point out where am going wrong.

[https://www.codechef.com/viewsolution/37058335](https://www.codechef.com/viewsolution/37058335)

Thanks

---

<div class="post-metadata">

**Author:** ![saurabhshadow](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabhshadow/32/347886_2.png) [@saurabhshadow](https://discuss.codechef.com/u/saurabhshadow)\
**Post date:** [August 22, 2020, 5:47pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/16 "2020-08-22T17:47:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![partha2717](https://discuss.codechef.com/user_avatar/discuss.codechef.com/partha2717/32/20510_2.png) [@partha2717](https://discuss.codechef.com/u/partha2717)\
**Post date:** [August 22, 2020, 5:54pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/17 "2020-08-22T17:54:54Z")

</div>

Thanks ,  
This really helped what i was missing.

---

<div class="post-metadata">

**Author:** ![partha2717](https://discuss.codechef.com/user_avatar/discuss.codechef.com/partha2717/32/20510_2.png) [@partha2717](https://discuss.codechef.com/u/partha2717)\
**Post date:** [August 22, 2020, 6:02pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/18 "2020-08-22T18:02:22Z")

</div>

Thanks . Figured out what i was missing.

---

<div class="post-metadata">

**Author:** ![zaidrpm](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@zaidrpm](https://discuss.codechef.com/u/zaidrpm)\
**Post date:** [August 24, 2020, 5:49pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/19 "2020-08-24T17:49:27Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mr\_mechanical](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mr_mechanical/32/200959_2.png) [@mr\_mechanical](https://discuss.codechef.com/u/mr_mechanical)\
**Post date:** [August 28, 2020, 7:46pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/20 "2020-08-28T19:46:01Z")

</div>

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](https://www.codechef.com/viewsolution/37212495)

---

<div class="post-metadata">

**Author:** ![mr\_mechanical](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mr_mechanical/32/200959_2.png) [@mr\_mechanical](https://discuss.codechef.com/u/mr_mechanical)\
**Post date:** [August 28, 2020, 8:03pm UTC](https://discuss.codechef.com/t/cens20e-editorial/75412/21 "2020-08-28T20:03:52Z")

</div>

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](https://www.codechef.com/viewsolution/37212495)

[Next page](https://discuss.codechef.com/t/cens20e-editorial/75412.md?page=2)