11386 - Triples

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

I used STL map

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

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

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

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

11386 - triples

Post by atanu-cse »

plz help- it's time limit exceeded,but I can't think of anything else yet :evil:

#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

Post by sohel »

Problem 10386 is "Circles in Triangle".

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

11386 - triples

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


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

Re: 11386 - triples

Post by Nursoltan_h »

:(

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11386 - Triples

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

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

Re: 11386 - Triples

Post 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..:)

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

Re: 11386 - Triples

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

Post Reply

Return to “Volume 113 (11300-11399)”