GS OA – Two Flowers

Problem Link – Link

The question asks us to find the length of the maximum connected component under the constraint that we can merge at max two different numbers. We are going to apply the Disjoint Set Union to solve this problem.

Initially, we will store all the connected components and label them. The visited array stores the component number of each cell. The sizes store the size of the connected component against the component number. We can apply simple BFS to get this data.

for (int i = 1; i <= n; ++i) {
    		for (int j = 1; j <= m; ++j) {
    			if (visited[i][j] != 0) {
    				continue;
    			}
    			queue < pair < int, int > > q;
    			q.push(make_pair(i, j));
    			visited[i][j] = ++ptr;
    			int qt = 1;
    			while (!q.empty()) {
    				int x = q.front().first, y = q.front().second;
    				q.pop();
    				for (int k = 0; k < 4; ++k) {
    					int nx = x + dx[k], ny = y + dy[k];
    					if (!visited[nx][ny] &amp;&amp; a[nx][ny] == a[x][y]) {
    						visited[nx][ny] = ptr;
    						q.push(make_pair(nx, ny));
    						qt++;
    					}
    				}
    			}
    			sizes[ptr] = qt;
    		}
    	}

Now, the BFS part is done. We will consider all those edges where component is changing. For each cell, we will look at all it’s neighbours and add an edge from current cell to that cell if they are not equal. To avoid duplication, we will consider pairing {i,j} where i> j. In this manner, only one instance of each edge will be taken into account.

We will create a map, where we will store all edges and for each edge, we will store a vector to it’s component number. For eg, in above image for pair {1,2} we will store all occurances of {1,2} in map[{1,2}] and the value will be their component number (stored in visited array). In this way we can get all links between {1,2} in map[{1,2}].

map < pair < int, int >, vector < pair < int, int > > > ed;
for (int x = 1; x <= n; ++x) {
    		for (int y = 1; y <= m; ++y) {
    			for (int k = 0; k < 4; ++k) {
    				int nx = x + dx[k], ny = y + dy[k];
    				if (a[nx][ny] <= a[x][y]) {
    					continue;
    				}
    				ed[make_pair(a[x][y], a[nx][ny])].push_back(make_pair(visited[x][y], visited[nx][ny]));
    			}
    		}
    	}

Applying DSU:

Now, we will start to combine each possible edges. Since we can merge atmost 2 different components, we will consider merging the components which are keys in our map. So iterate over keys, use DSU to group up the connected components together, update the ans and revert back the changes you perform.

int ans = 0;
    	for (int i = 1; i <= ptr; ++i) {
    		who[i] = i;
    		sz[i] = sizes[i];
    		ans = max(ans, sz[i]);
    	}

for (auto &amp;vec : ed) {
    		vector < int > changed;
    		for (auto &amp;it : vec.second) {
    			int x = it.first, y = it.second;
    			changed.push_back(x);
    			changed.push_back(y);
    			int xx = getWho(x), yy = getWho(y);
    			if (xx == yy) {
    				continue;
    			}
    			if (rand() &amp; 1) {
    				swap(xx, yy);
    			}
    			who[xx] = yy;
    			sz[yy] += sz[xx];
    			ans = max(ans, sz[yy]);
    		}
    		for (auto &amp;it : changed) {
    			sz[it] = sizes[it];
    			who[it] = it;
    		}
    	}

Complete Code :

    #include <bits/stdc++.h>
     
    using namespace std;
     
    const int MaxN = (int)2e3 + 10;
    const int MOD = (int)1e9 + 7;
    const int INF = 1e9;
     
    int m, n;
    int a[MaxN][MaxN], ptr;
    int visited[MaxN][MaxN];
    int sizes[MaxN * MaxN];
    int who[MaxN * MaxN], sz[MaxN * MaxN];
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
     
    int getWho(int v) {
    	return v == who[v] ? v : who[v] = getWho(who[v]);
    }
     
    int main() {
    //	freopen("input.txt", "r", stdin);
    //	ios::sync_with_stdio(false); cin.tie(NULL);
    	scanf("%d%d", &amp;n, &amp;m);
    	for (int i = 1; i <= n; ++i) {
    		for (int j = 1; j <= m; ++j) {
    			scanf("%d", &amp;a[i][j]);
    		}
    	}
    	for (int i = 1; i <= n; ++i) {
    		for (int j = 1; j <= m; ++j) {
    			if (visited[i][j] != 0) {
    				continue;
    			}
    			queue < pair < int, int > > q;
    			q.push(make_pair(i, j));
    			visited[i][j] = ++ptr;
    			int qt = 1;
    			while (!q.empty()) {
    				int x = q.front().first, y = q.front().second;
    				q.pop();
    				for (int k = 0; k < 4; ++k) {
    					int nx = x + dx[k], ny = y + dy[k];
    					if (!visited[nx][ny] &amp;&amp; a[nx][ny] == a[x][y]) {
    						visited[nx][ny] = ptr;
    						q.push(make_pair(nx, ny));
    						qt++;
    					}
    				}
    			}
    			sizes[ptr] = qt;
    		}
    	}
    	map < pair < int, int >, vector < pair < int, int > > > ed;
    	int ans = 0;
    	for (int i = 1; i <= ptr; ++i) {
    		who[i] = i;
    		sz[i] = sizes[i];
    		ans = max(ans, sz[i]);
    	}
    	for (int x = 1; x <= n; ++x) {
    		for (int y = 1; y <= m; ++y) {
    			for (int k = 0; k < 4; ++k) {
    				int nx = x + dx[k], ny = y + dy[k];
    				if (a[nx][ny] <= a[x][y]) {
    					continue;
    				}
    				ed[make_pair(a[x][y], a[nx][ny])].push_back(make_pair(visited[x][y], visited[nx][ny]));
    			}
    		}
    	}
    	for (auto &amp;vec : ed) {
    		vector < int > changed;
    		for (auto &amp;it : vec.second) {
    			int x = it.first, y = it.second;
    			changed.push_back(x);
    			changed.push_back(y);
    			int xx = getWho(x), yy = getWho(y);
    			if (xx == yy) {
    				continue;
    			}
    			if (rand() &amp; 1) {
    				swap(xx, yy);
    			}
    			who[xx] = yy;
    			sz[yy] += sz[xx];
    			ans = max(ans, sz[yy]);
    		}
    		for (auto &amp;it : changed) {
    			sz[it] = sizes[it];
    			who[it] = it;
    		}
    	}
    	printf("%d\n", ans);
    	return 0;
    }
     

Source –

https://s3.amazonaws.com/codechef_shared/download/Solutions/JUNE18/setter/TWOFL.cpp

Leave a Reply