GAMEH - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author, Tester & Editorialist: Ashish Prasad

DIFFICULTY:

MEDIUM

PREREQUISITES:

Bitwise-XOR, Connected Components

PROBLEM:

https://www.codechef.com/problems/GAMEH

EXPLANATION:

In this problem we have 2 types of query:

  • 1 i K : For this type of query we need to perform following operation:

If \bigl( \bigl( \bigl( A[i] + 2^{K-1} \bigr) & 2^{K-1} \bigr) == 0 \bigr) then change A[i] to A[i] - 2^{K-1} else change to A[i] + 2^{K-1}

On careful observation we can see that it’s just an XOR operation. So we need to perform XOR on the given value at index i with 2^{K-1} and thus we need to perform the same operation on all the indexes which are linked with the index i.

So to do this we will use the concept of connected components. We will give an integer number or hash the indexes with a certain connected component they belong to.

For example : If indexes [0, 1, 2, 5] belong to one component then they will be hashed with a certain integer, say 1. And then if indexes [3, 4] belong to one component then they will be hashed with an integer, say 2. And so on for other components. This technique will let us know which index belongs to which component.

  • 2 i : For this query we need to output the increase or decrease in value at index i which was caused by the recent type 1 query which has affected the index value w.r.t. current operation.

For this we need to make a prefix of type 1 operation that has occurred at each index which can be done with hashing. For each type 2 we must first find out in which component the given index i belongs to, after that we see the difference with the help of a prefix hash.

SOLUTIONS:

Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#pragma GCC optimize("Ofast")  
#pragma GCC target("avx,avx2,fma") 
#define int long long
static auto _ = [] ()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
int c;
int vis[100000];
vector<int> v[100000];
void dfs(int a)
{
	vis[a] = c;
	for(auto j : v[a])
	{
		if(vis[j] == 0)
			dfs(j);
	}
}
int32_t main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n, l, q;
		cin >> n >> l >> q;
		int a[n];
		for(int i = 0; i < n; i++)
		{
			cin >> a[i];
		}
		map<int, int> m, previ;
		c = 0;
		int a1, b1;
		while(l--)
		{
			cin >> a1 >> b1;	
			v[a1].push_back(b1);
			v[b1].push_back(a1);
		}
		memset(vis, 0, sizeof(vis));
		for(int i = 0; i < n; i++)
		{
			if(vis[i] == 0)
			{
				c++;
				dfs(i); 
			}
		}
		int pre[n];
		memset(pre, 0, sizeof(pre));
		while(q--)
		{
			int in, i, k;
			cin >> in;
			if(in == 1)
			{
				cin >> i >> k;
				int power2 = pow(2, k - 1);
				previ[vis[i]] = m[vis[i]];
				m[vis[i]] = m[vis[i]] ^ power2;
			}
			else
			{
				cin >> i; 
				int prev = a[i] ^ previ[vis[i]];
				int curr = a[i] ^ m[vis[i]];
				if(prev > curr)
				{
					cout << "-" << prev - curr<< "\n";
				}
				else if(curr > prev)
					cout << "+" << curr - prev << "\n";
				else
					cout << 0 << "\n";
			}
		}
		cout << c << "\n";
		for(int i = 0; i < n; i++)
			v[i].clear();
	}
}

Well this was my approach, feel free to share your approach here. Suggestions are always welcomed.