JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Round Tables External Competitions SWERC-2010 Problem C - Comparing Answers
 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.