Method of four russians

Can somebody please explain me “Method of Four Russian” algorithm to find Boolean product of matrices(implementation in particular)?

3 Likes

Its a long and comprehensive tutorial on it.

6 Likes

Mohit Menghnani : I like this one more.

Thanks @gkcs . Finally, I managed to get an ac to this question with a time of 0.61(fastest algorithm to this question).

http://www.codechef.com/viewsolution/4410273

1 Like

How do we store the preprocessed table of B in the implementation of the above algorithm?

Please reply to the above comment.

@rishavz_sagar, sorry for the late reply.In the contest, I used n^3 solution. What I can see from the videos is that the tables are nothing but data structures. So arrays should suffice.

Which data structure is preferable for storing binary values whose indices are themselves binary?

An 2D Integer array, or 2D long array. Internally, these are stored as binary by the computer.

You are welcome. :slight_smile: