## 11386 - Triples

Moderator: Board moderators

yjwoo14
New poster
Posts: 7
Joined: Wed Jan 09, 2008 5:58 am

### I used STL map

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;
}
}
``````

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
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.

atanu-cse
New poster
Posts: 3
Joined: Fri Dec 18, 2009 12:09 pm

### 11386 - triples

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;
}
================================================
Last edited by atanu-cse on Wed Apr 07, 2010 1:21 pm, edited 2 times in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 10386 - triples

Problem 10386 is "Circles in Triangle".

atanu-cse
New poster
Posts: 3
Joined: Fri Dec 18, 2009 12:09 pm

### 11386 - triples

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;
}

``````

Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

### Re: 11386 - triples

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11386 - Triples

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.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 11386 - Triples

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..

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11386 - Triples

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.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson