ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1880. Psych Up's Eigenvalues

Time limit exceeded
Posted by Kanatbek 12 Jun 2012 08:18
po4emu u menia Time Limit Exceeded? (

Edited by author 12.06.2012 08:19
#include <iostream>
using namespace std;
int main()
{
int a[4000],a2[4000],a3[4000],i,j,l,n,n2,n3,k=0;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
cin>>n2;
for(j=1;j<=n2;j++)
cin>>a2[j];
cin>>n3;
for(l=1;l<=n3;l++)
cin>>a3[l];
for(i=1;i<=n;i++)
{
for(j=1;j<=n2;j++)
{
for(l=1;l<=n3;l++)
{
if(a[i]==a2[j] && a[i]==a3[l]) k++;
}
}
}
cout<<k;
return 0;
}

Edited by author 12.06.2012 08:25
Re: Time limit exceeded
Posted by Smilodon_am [Obninsk INPE] 13 Jun 2012 12:40
Your algorithm has complexity O(N^3) while N = 4000. It is very long. Try to use binary search, then you will find solution with complexity O(N * logN * logN).
Re: Time limit exceeded
Posted by Andrew Sboev [USU] 25 Mar 2013 22:19
This problem can be solved by O(N) time... If you have a good hash function, of course
And O(N * log N) instead of yours O(N * log N * log N) using map.

Edited by author 25.03.2013 22:24