PROBLEM LINK
DIFFICULTY
MEDIUM
PREREQUISITES
Disjoint Sets, Simple Math
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.
EXPLANATION
Let us assume U is a disjoint set data structure.
- U.init(N) creates a node N and assigns it an independent group.
- U.Root(N) returns a unique identifier for the group to which N belongs.
-
U.join(A,B) joins the groups which contain A, an which contain B respectively.
- After calling U.join(A,B), U.Root(A) will be equal to U.Root(B)
We know that the amortized complexity of performing T operations of U is O(U * iA(N)), where iA is the inverse of the Ackermann function (and practivally very very small for very large values of N as well).
We use U and build aU, which helps us maintain the number of sources without any additional complexity.
procedure: aU.init(N) // O(1)
U.init(N) // O(1)
sources[N] = 0 // O(1)
aU.Root(N) simply returns U.Root(N). Of course, we do not have to do any additional calculations for maintaining the number of sources while finding the Root.
We add the number of sources of potential in the Join method.
procedure: aU.join(A,B)
U.join(A,B)
if U.Root(A) has become parent of U.Root(B)
sources[ U.Root(A) ] += sources[ U.Root(B) ]
else
sources[ U.Root(B) ] += sources[ U.Root(A) ]
Now, addition / deletion and lookup of the number of sources of potential on a grid node N can be done by incrementing / decrementing and lookup of sources[ aU.Root(N) ]
It remains to mention that considering all grid nodes as separate groups - and joining groups of 5 initially - may create massive blobs of in-memory arrays that might cause thrashing (and slow code). Thus, you can optimize your code by calculating the row-number that a given grid point belongs to and working on the that number. Now, there can be at most 500*2500 sets.
SETTERS SOLUTION
Can be found here.
TESTERS SOLUTION
Can be found here.