SPOJ SUMFOUR ..... TLE on Test Case 9
I am trying to solve SPOJ SUMFOUR problem .... I am getting TLE on Test Case 9 http://www.spoj.com/problems/SUMFOUR/
So which part of my code should be edited and how? Here N <= 4000
#include <iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
int main()
{
int a[4005][5],n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=4;j++)
scanf("%d",&a[i][j]);
int k=0;
for(int i=1;i<=n;i++)
{ int p=a[i][1];
for(int j=1;j<=n;j++)
{ b.push_back(p+a[j][2]);
k++;
}
}
k=0;
for(int i=1;i<=n;i++)
{ int p=a[i][3];
for(int j=1;j<=n;j++)
{ c.push_back(p+a[j][4]);
k++;
}
}
sort(b.begin(),b.end());
int cnt=0;
for(int j=0;j<k;j++)
if(find(b.begin(),b.end(),-c[j])!=b.end() )
cnt=cnt+count(b.begin(),b.end(),-c[j]) ;
printf("%d\n",cnt);
return 0;
}
source to share
The problem is here:
for(int j=0;j<k;j++)
if(find(b.begin(),b.end(),-c[j])!=b.end() )
cnt=cnt+count(b.begin(),b.end(),-c[j]) ;
for n = 4000, so there are 4000 ^ 2 elements in b and c. Thus, the time complexity of this cycle is equal to 4000 ^ 4 as find
and count
complexity time - is O (n), which, of course, would exceed the time limit.
So how can you shorten your time? You can use binary search to speed up the counting process, which reduces the complexity of the said loop time to O (n ^ 2 log n) as I noticed that you are already sorting b
.
Or you can use map to count and store the frequency of each element in b and c.
map<long long, int> b;
map<long long, int> c;
for(int i=1;i<=n;i++)
{ long long p=a[i][1];
for(int j=1;j<=n;j++)
{
long long tmp =p + a[j][2];
b[tmp] = b[tmp] + 1;
}
}
// Similar for c
map <long long, int>::iterator it;
long long result;
for (it = c.begin(); it != c.end(); ++it)
result += c[it->first]*b[-(it->first)];
For your new update, please change this:
for(int j=1;j<=n;j++)
{ if( b.count(a[i][1]+a[j][2]) )
{ b[a[i][1]+a[j][2]]+=1;
c[a[i][3]+a[j][4]]+=1;
}
else
{ b[a[i][1]+a[j][2]]=1;
c[a[i][3]+a[j][4]]=1;
}
}
in it:
for(int j=1;j<=n;j++)
{
b[a[i][1]+a[j][2]]+=1;
c[a[i][3]+a[j][4]]+=1;
}
Condition checking is if( b.count(a[i][1]+a[j][2]) )
for b
, and you are using it for c
, which makes it c
wrong.
Refresh . After trying to accept in SPOJ, it turns out that the map is not fast enough, so I modify the binary search and accept.
source to share
Please don't use a map as its worst complexity might be O (log (n)).
SO instead you can just use two sorted arrays and for each element, as in
first array, binary search for its agent -ve in the second cumulative array.
Just change the search method in the last lines to binary search (c.begin (), c.end (), key) and search for repititons all the way down with that index, as it gives the lower_bound index.
What Total Sum provides the answer and its expected complexity
O (n ^ 2log (n)).
source to share