BF21JA - Editorial

codechef_ciem · February 3, 2021, 1:49pm

PROBLEM LINK

DIFFICULTY

MEDIUM

PREREQUISITES

PROBLEM

You are given a Jam Board with R rows and C columns. A row of the jambaord contains a group of 5 points arranged vertically, which are connected with the same metal plate. So you have a grid of 5*R rows and C columns.

You are to simulate the following 4 operations

Add a wire connecting two grid points.
Give potential to a grid point.
Remove potential from a grid point.
Check if there is potential difference between two grid points. (Since potential difference leads to LED being on)

QUICK EXPLANATION

This would be an entirely different problem if we were to allow for removal of a wire that connects two grid points. Since that is not allowed, the problem reduces to maintaining disjoint sets of groups. Also known as Union Find. We have to make a tiny modification though - to maintain the number of sources providing potential to each group.

The number of sources are easy to maintain.

Augment the Join method in your Disjoing Sets data structure to add and store the potential on the root for the whole group.
Addition and Removal of a source of potential for a group are simply performed at the root of the group.

SOLUTION (in C++) :

#include <bits/stdc++.h>

using namespace std;

#define ll long long int
const int mod = 1e9 + 7;

int n, row, cols;

int getValue(int x, int y) {
    return ((y - 1) / 5) * cols + x - 1;
}

int parent[1250010];
int mrank[1250010];
int voltage[1250010];

int decrypt(char s[]) {
int a = 0, b = 0;
if (s[0] & 32)a += s[0] - 'a' + 26;
else a += s[0] - 'A';
a = a * 52;
if (s[1] & 32)a += s[1] - 'a' + 26;
else a += s[1] - 'A';
if (s[2] & 32)b += s[2] - 'a' + 26;
else b += s[2] - 'A';
b = b * 52;
if (s[3] & 32)b += s[3] - 'a' + 26;
else b += s[3] - 'A';
return getValue(a, b);
}

int findParent(int x) {
if (parent[x] == x)return x;
else return parent[x] = findParent(parent[x]);
}

void addSource(int x) {
voltage[x]++;
}

void removeSource(int x) {
voltage[x]--;
assert(voltage[x] >= 0);
}

bool getVoltage(int x) {
return voltage[x] != 0;
}

void merge(int x, int y) {
int px = findParent(x);
int py = findParent(y);
if (px != py) {
    if (mrank[px] >= mrank[py]) {
        parent[py] = px;
        mrank[px]++;
        voltage[px] += voltage[py];
    } else {
        parent[px] = py;
        mrank[py]++;
        voltage[py] += voltage[px];
    }
}
}

int main() {
//code
char st[16];
scanf("%d%d%d", &n, &row, &cols);
for (int i = 0; i <= (row * cols); i++) {
    parent[i] = i;
    mrank[i] = 0;
    voltage[i] = 0;
}
while (n--) {
    scanf("%s", st);
    switch (st[0]) {
        case 'W': {
            int s1 = decrypt(st + 1);
            int s2 = decrypt(st + 5);
            //cout<<s1<<" "<<s2<<endl;
            merge(s1, s2);
        }
            break;
        case 'V': {
            int s1 = decrypt(st + 1);
            //cout<<s1<<endl;
            addSource(findParent(s1));
        }
            break;
        case 'R': {
            int s1 = decrypt(st + 1);
            //cout<<s1<<endl;
            removeSource(findParent(s1));
        }
            break;
        case 'L': {

            int s1 = decrypt(st + 1);
            int s2 = decrypt(st + 5);
            //cout<<s1<<" "<<s2<<endl;
            if (getVoltage(findParent(s1)) != getVoltage(findParent(s2))) {
                printf("ON \n");
            } else {
                printf("OFF \n");
            }
        }
            break;
    }
}

return 0;
}