JABO - Editorial

PROBLEM LINK

Practice
Contest

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.

2 Likes

I’m interested - if we can remove wires is there elegant solution for this?

3 Likes

This might help.

1 Like

http://www.codechef.com/viewsolution/1554901
Can anyone help me why i am getting run time error with this code?
Thanks in advance

[This doesn’t fits in comment so I am posting it as answer]

@saikrishna173 : You are getting run time error (SIGSEGV to be exact), because you are allocating too much memory on stack.

set B[500][2500];

This line of yours is the source of error.

Solutions -

  1. Allocate this 2D array on heap. Just move this line out of main()
  2. You can also use ‘new’ operator to allocate on heap. Be sure to deallocate using ‘delete’.
  3. Use std::vector. It is the best solution, as it is the most C++ish way of doing it.

Some might ask why did it compile in first place. I think, that’s because compiler doesn’t know how much stack memory would be available.

And don’t think the reason of error was using too much memory, you didn’t.

2 Likes

@vinayak garg still getting run time error.Can you change my submission and check the submission??

i have done exactly the same thing. Can you point out the error in this solution. http://www.codechef.com/viewsolution/1547245

I think, that correct output for

2 2 2
VABAE
LABAFACAF

is ON, what returns your code? On ideone it fails on TLE - http://ideone.com/I799ER .

@betlista My code returns ON. And by the way i am unable to open the url u posted.

@saikrishna173 that’s because there was dot at the end…

on my PC your code is not running, without input it fails on SIGSEGV too

@betlista
how much memory can we allocate
because in a tutorial of lucky9 it’s been said that we could allocate int[5000][5000] memory

1 Like

You are absolutely correct, that’s the problem with @saikrishna173’s code, when I moved set B[500][2500]; before main it is without RE

I do not know exact size of stack, here is written, that default is 8MB (on linux) - http://www.cs.nyu.edu/exact/core/doc/stackOverflow.txt

1 Like

see @pankajb23’s answer, you have problem with memory, move set before main

@belista can u give the url of the specified code

@betlista Sorry check this submission. Even then I am getting TLE,i tried moving set before main also.http://www.codechef.com/viewsolution/1555068

@saikrishna173 I checked your code. It is giving SIGSEGV in set* head(set& A) function. I couldn’t fix it, because it is related to your logic. I suggest you review your logic, and rewrite a simpler code this time. Your code is rather difficult to read.

2 Likes

@vinayak garg Thanks a lot sir…!! Is it the case with every test case or few test cases

Yet again it doesn’t fit in comment.

@saikrishna173: I tested it against one test file only. The SIGSEGV you are getting is not because of corner case. It is failing on average case.

One reason I can think of error - You are using vector (as suggested by me), and you are storing the pointers of its elements. Don’t assume anything about underlying implementation of vectors. You should use iterators to access its elements, not pointers.

As I have said before, you need to simplify. To store “parent”, instead of using pointer, you should use a integer offset.

Some general comments (not related to RE)-

  1. Use scanf instead of your own input function.
  2. Macros - Never use them.
  3. Indentation- Please indent using A-Style or K&R style.
  4. Avoid unnecessary usage of pointers
1 Like

Thanks a lot…!!!