11386 - Triples

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

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

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

[sohel]

Problem 10386 is "Circles in Triangle".

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

[Nursoltan_h]

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

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

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