JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
SWERC-2010 Problem C - Comparing Answers | Reply
Problem statement is here.

My idea is let the adjacency matrix for the given graph be A and the second matrix in the input be B. The answer is YES if A2==B otherwise NO.

But this solution gives TLE as the input is large and I used naive matrix multiplication. Should I use any faster matrix multiplication algorithm or other faster solution exists. Anyone help. Thanks in advance.
Re: SWERC-2010 Problem C - Comparing Answers (response to post by f.nasim) | Reply
I don't know if this is the intended solution, but there is a randomized algorithm to verify matrix multiplication in O(n^2). See this thread for some references.
Re: SWERC-2010 Problem C - Comparing Answers (response to post by MauricioC) | Reply
Yes, the intended solution is randomized (Freivalds's algorithm).
Re: SWERC-2010 Problem C - Comparing Answers (response to post by MauricioC) | Reply
Yes. I got accepted. I used 10 iterations and it took 14.720s. Thanks a lot.
RSS