About a month ago in Augest-Long-Challenge[2016] a question — "Funny — Genome" was asked in CodeChef. Although no Official Editorial was released for it , "wodahs_cc" suggested that we need to use "Four Russian Method" to solve for the problem in the forum. I've searched the Internet and also gone through the Video for it, but I could not find a proper implementation to it, So I've Implemented it with my own understanding of the algorithm but still got "Time-Limit-Exceeded" error for some test cases. I don't know what I did wrong. I request you people of Code-Forces community to kindly provide an Implementation for the Four-Russian-Method. I thank you all in advance.
P.S : A Link to my Implementation.
Auto comment: topic has been updated by rsampaths16 (previous revision, new revision, compare).
As far as speeding up boolean matrix multiplication is concerned, I feel using bitset is much more convenient and easier to write. According to me "method of four Russians" gives a speed upto (logn), but in most cases n <= 1000, when matrices are being considered. In such case, log(n) ~ 32, which is also the speed up due to using bitset.
If you implement the bitset, yourself using long long, you may also end up getting a speedup upto 64 times. I think in most cases, bitset suffices.
You can refer to my implementation using (self-written) bitset Code
Using the STL bitset, here is another small clean implementation Code 2
firstly , thank you for taking the time to help me out, the code you linked me was concise and much easy to understand. And also I'd try to approach the problem using bitset as you suggested. UPDATE :: I've got AC after converting my code from using Array to using Bitset. Thank you
Can you explain more clearly as how matrix multiplication of binary matrix is done using bitset ?
You may check this out — https://discuss.codechef.com/questions/47984/rrfrnds-editorial
likecs, thanks for the STL implementation! I would like to know why path lengths have been taken in powers of 2 upto 2^30. Even, how the idea struck you? Moreover, when a new query is seen, why do you take the highest set bit of k and use it? Thanks.
Hi hit023, the idea is simple. In general code for matrix multiplication, we multiply 2 matrices. The multiplication of base matrix is redundant when it is carried out many times (as here in each query). So, we pre-process the powers of base matrix in powers of 2. Then use these precomputed matrices to get the {n}th power of base matrix. (Since, this matrix is same is each query).
If the matrix was not same in each query, this idea could not have been used. This basically reduces the constant factor when number of queries are large as compared to precomputation part of 30 * {n}3. It is not always a useful method to do if matrices keep changing in each query or precomputation is large enough to leave time for answering the queries.
Hope this clears your doubt.
Thanks. It seems more intuitive now.