Page 2 of 2
I used STL map
Posted: Mon Jan 14, 2008 12:51 pm
by yjwoo14
I used STL map O(n^2) (or n^2lgn)
But I got TLE T_T
Is map too slow to solve this problem?
This is my code..
Code: Select all
#include<iostream>
#include<map>
using namespace std;
int main(){
int num, cnt;
long long input;
long long max, z;
map<long long, int> M;
while (cin >> num){
cnt = 0;
max = 0;
M.clear();
for (int i = 0 ; i < num ; i++){
cin >> input;
M[input]++;
if (input > max)
max = input;
}
map<long long, int>::iterator it1, it2, temp;
for (it1 = M.begin() ; it1 -> first * 2 <= max; it1++){
for (it2 = it1; it1 -> first + it2 -> first <= max ; it2++){
z = it1->first + it2->first;
temp = M.find(z);
if (temp -> first == z){
if (it1->first == it2->first){
cnt += it2->second * (it2->second - 1) / 2 * temp -> second;
}else{
cnt += it1->second * it2->second * temp -> second;
}
}
}
}
cout << cnt << endl;
}
}
Posted: Mon Jan 21, 2008 4:29 am
by sonyckson
Probably yes, map is too slow for this problem, it will pass the TL if you use sorted array's and binary search. gl!, Eric.
11386 - triples
Posted: Wed Apr 07, 2010 4:52 am
by atanu-cse
plz help- it's time limit exceeded,but I can't think of anything else yet
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
freopen("D://test.txt","r",stdin);
freopen("D://out.txt","w",stdout);
long long i,j,p[6000],t,n,sum,k;
while(scanf("%lld",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%lld",&p
);
t=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(j!=i)
{
sum=p+p[j];
for(k=0;k<n;k++)
{
if(sum==p[k])
t++;
}
}
}
}
printf("%lld\n",t/2);
}
return 0;
}
================================================
Re: 10386 - triples
Posted: Wed Apr 07, 2010 9:51 am
by sohel
Problem 10386 is "Circles in Triangle".
11386 - triples
Posted: Wed Apr 07, 2010 1:21 pm
by atanu-cse
plz help- it's time limit exceeded,but I can't think of anything else yet
Code: Select all
#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
freopen("D://test.txt","r",stdin);
freopen("D://out.txt","w",stdout);
long long i,j,p[5010],t,n,sum,k;
while(scanf("%lld",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%lld",&p[i]);
/*for(i=0;i<n;i++)
for(j=0;j<n-1;j++)
if(p[j]>p[j+1])
swap(p[j],p[j+1]);*/
t=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(j!=i)
{
sum=p[i]+p[j];
for(k=0;k<n;k++)
{
if(sum==p[k])
t++;
}
}
}
}
printf("%lld\n",t/2);
}
return 0;
}
Re: 11386 - triples
Posted: Tue Aug 24, 2010 5:30 am
by Nursoltan_h
Re: 11386 - Triples
Posted: Mon Jun 13, 2011 5:30 pm
by Shafaet_du
Try this:
Code: Select all
20
234
67
45
56
34
67
45
34
56
45
34
56
67
45
5
34
5
54
67
my output from accepted code: 56
uva toolkit output: 63
Current time limit is 8 sec,so n^2 will pass.
Re: 11386 - Triples
Posted: Wed Aug 17, 2011 10:34 pm
by Imti
I was Trying it with nlogn+n+n^2logn algorithm..but was getting TLE ..What I was doing is:
1)First,I sorted data
2)Then used Grouping Idea.By O(n) loop I made separate list of unique elements with their frequency
3)Then two nested loop:
Code: Select all
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
result+=Binary_search(a[i]+a[j])//It returns frequency If key found otherwise 0
But this results in TLE...is this method supposed to get TLE?
Then I used Hashing and gave me accepted..
Re: 11386 - Triples
Posted: Sat Dec 31, 2011 2:16 pm
by plamplam
I don't know why, but my O(n ^ 2) * log(n) algorithm gets Time Limit Exceeded. I used sort + grouping with frequency + binary search. I later got Accepted at 6.732 seconds after using STL map and changing everything to long long. And yeah, writing a hashing function would be much faster, probably that's how people got < 1s.
If you get Wrong Answer, it's most probably because you did a mistake somewhere in your implementation and not because of tricky cases. I got one because I was using int at first.
