I have solved this question to O(n^3) and cant further optimize it.so please explain the algo

qstn http://www.codechef.com/problems/RRFRNDS

mysoltn http://www.codechef.com/viewsolution/4529248

thank you

I have solved this question to O(n^3) and cant further optimize it.so please explain the algo

qstn http://www.codechef.com/problems/RRFRNDS

mysoltn http://www.codechef.com/viewsolution/4529248

thank you

Actuallly, there is no “better” algorithm. The best algorithm is O((1/30)*N^3). Just implement the brute force one with the incidency matrix kept on bits.

My solution on this idea: http://www.codechef.com/viewsolution/4360653

2 Likes

can u please see my code where i should i have optimized…so that i can learn how to optimize code

Thank you

common_element function can be done in O(N/30) complexity. Keep the incidency matrix on bits. Check the editorial if you don’t know how.

1 Like

thank you.

But no tutorial for this problem. and i can’t find how to do it so can u plz share some link