ohh, sorry. wrong copy-paste lol. this one should be 4. The one that should be 2 is this one:
4
0111
1011
1100
1100
is there any solution(solved) using the other method using matrix multiplication??
well, I guess this problem has a strict time limit for python (but then again, I’m no expert in python). this is the optimized code that is equivalent to what I’ve done in C++:
http://www.codechef.com/viewsolution/4362878
i’ve seen one solution that uses python and got AC, here it is:
http://www.codechef.com/viewsolution/4360214
from this AC sol in python, it seems your issue is in slow I/O
Can be solved using binary search . Complexity nnlog(n*n)
http://www.codechef.com/viewsolution/4360176
i have used distance 2 in this ques.
I am getting WA in this.
alphaparticle: No, your solution is O(N^3 log(N)) - for each disconnected pair, you can end up checking all edges from one of them before breaking, and there can be a lot of them. It just has a really good constant and it’s hard to make testcases where it runs worst-case.
No, your solution is O(N^3 log(N)) - for each disconnected pair, you can end up checking all edges from one of them (you’re not doing one binseatch, you’re doing up to degree(u) binsearches) before breaking, and there can be a lot of them. It just has a really good constant and it’s hard to make testcases where it runs worst-case.
1 Like
Yes; that was the problem.
However, this problem was quite biased against Python users IMO; did users in other languages experience the same problem?
brilliantly done!
1 Like
is Strassen algorithm really fast enough to solve this? http://discuss.codechef.com/questions/48384/strassen-algorithm-not-fast-enough
The editorials of codechef are a lot more exhaustive and easier to understand than that of codeforces.
1 Like
It seems my optimisations were correct!! Cuts the runtime by HALF 
Here is my submission. I’ll leave it to you to understand why this works :). Common sense actually 
Here’s a similar SPOJ question I had solved. It’s easier than this. I just used HashMaps there. SPOJ.com - Problem FACEFRND
Can someone explain why am i getting runtime error and whether my approach is correct or not?
https://www.codechef.com/submit/complete/25290158
ans += UF.sz[UF.root(i)] - 1 - cnt[i];
How are you using the size of the node? It is used for optimisation…
Awesome problem and an equally nice editorial.
if any one looking for solution time - 0.01 sec
void go()
{
int N ;
cin>>N ;
vector<vector<bool>>A(N,vector<bool>(N,0) );
vector<int>g[N];
for( int i = 0 ; i < N ; i++ )
{
string S ;
cin>>S ;
for( int j = 0 ; j < N ; j++ )
if( S[j] == '1' )A[i][j] = 1 ;
for( int j = 0 ; j < N ; j++ )
{
if( S[j] == '1' )
{
g[i].push_back(j);
g[j].push_back(i);
}
}
}
int cnt = 0 ;
vector<vector<bool>>mark(N,vector<bool>(N,0));
for( int i = 0 ; i < N ; i++ )
for( int j = i ; j < N ; j++ )
{
if( i == j )continue;
if( A[i][j] == 0 && mark[i][j] == 0 )
{
for( auto k : g[i] )
{
if( A[i][k] == 1 && A[j][k] == 1 )
{
mark[i][j] = 1;
cnt++;
break;
}
}
}
}
cout<<2*cnt<<endl;
}
int32_t main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int test = 1 ;
// cin>>test;
while(test--)
{
go();
}
return 0 ;
}