Tle in abcdef

[simple_sof]

i was trying to solve the problem ABCDEF https://www.spoj.pl/problems/ABCDEF/
and am getting TLE can u please help how can i optimize my code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int n;
	vector<int> vl;
	vector<int> vh;
	int a1,b,c,d,e,f;
	int count1=0;
	scanf("%d",&n);
	int a[n];
	int size=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++)
	{
		a1=a[i];
		d=a[i];
		for(int j=0;j<n;j++)
		{
			b=a[j];
			e=a[j];
			for(int k=0;k<n;k++)
			{
				c=a[k];
				f=a[k];
				int x=a1*b+c;
				int y=d*(e+f);
				int bit=-1;
				vl.push_back(x);
				size++;
				int i;
				for( i=size-1;i>=0;i--)
				{	
					if(vl[i]<x)
					{
						vl[i+1]=x;
						  bit=0;
						break;
					}
					else
					{
						vl[i+1]=vl[i];
					}
				}
				if(i==-1)
				{
					vl[0]=x;
				}
				vh.push_back(y);
			}
		}
	}
    for(int i=0;i<size;i++)
{
	int find=vh[i];
	int high=size-1;
	int low=0;
	int mid=(low+high)/2;
	while(low<=high)
	{
       		mid = (low+high) / 2; 
       		if (find > vl[mid]) 
	   		low = mid + 1;  // repeat search in top half.
       		else if (find < vl[mid]) 
	   		high = mid - 1; // repeat search in bottom half.
       		else
       		{
       			int mycount = (int) count (vl.begin(), vl.end(), find);
	   		count1=count1+mycount;
	   		break;
	   	}     
	 }
}

printf("%d\n",count1);
return 0;
}

[leppyr64]

Why are you using i inside a loop that has already defined i?

[simple_sof]

srry

[michi]

i wonder why it compiles at all

you still have a for-loop for k INSIDE a for-loop for k

[simple_sof]

still tle

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
	int n;
	vector<int> vl;
	vector<int> vh;
	int a1,b,c,d,e,f;
	int count1=0;
	scanf("%d",&n);
	int a[n];
	int size=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++)
	{
		a1=a[i];
		d=a[i];
		for(int j=0;j<n;j++)
		{
			b=a[j];
			e=a[j];
			for(int k=0;k<n;k++)
			{
				c=a[k];
				f=a[k];
				int x=a1*b+c;
				int y=d*(e+f);
				int bit=-1;
				vl.push_back(x);
				size++;
				int sd;
				for( sd=size-1;sd>=0;sd--)
				{	
					if(vl[sd]<x)
					{
						vl[sd+1]=x;
						  bit=0;
						break;
					}
					else
					{
						vl[sd+1]=vl[sd];
					}
				}
				if(sd==-1)
				{
					vl[0]=x;
				}
				vh.push_back(y);
			}
		}
	}
    for(int i=0;i<size;i++)
{
	int find=vh[i];
	int high=size-1;
	int low=0;
	int mid=(low+high)/2;
	while(low<=high)
	{
       		mid = (low+high) / 2; 
       		if (find > vl[mid]) 
	   		low = mid + 1;  // repeat search in top half.
       		else if (find < vl[mid]) 
	   		high = mid - 1; // repeat search in bottom half.
       		else
       		{
       			int mycount = (int) count (vl.begin(), vl.end(), find);
	   		count1=count1+mycount;
	   		break;
	   	}     
	 }
}

printf("%d\n",count1);
return 0;
}

[leppyr64]

The complexity of your code is O(n^6)! That's much too large.

[anuragkataria_sof]

hi this is probably the neatest code i have written. its giving a tle. i tried making long long int to int to int and long int but that gave a wa probably due to overflow plz help

thanks got ac :-)

[leppyr64]

Certainly not due to overflow. 30000*30000+30000 < 2^31

Read the problem statement carefully, you've omitted a very important detail.

[anuragkataria_sof]

thanks

[thechamp]

my this code O(n^3 logn) gives TLE too. someone help me find bug

edited

[leppyr64]

Your solution is O(n^6)

[thechamp]

right it was O(n^6). i amended my binary search accordingly, but still TLE

edited

[leppyr64]

Recursion is slow. Use an iterative search.

[thechamp]

changed approach. TLE yet again

removed. changed qsort() to std::sort() and got AC!

[logic_king]

Hello guys...plz help me in optimizing i am getting TLE in ABCDEF...
here is my code..

#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
    int num,ans=0,value,i,j,k,t,a,b,c,d,e,f;
    scanf("%d",&num);
    vector<int> val,a1,a2;
    for(i=0;i<num;i++)
    {
        scanf("%d",&t);
        val.push_back(t);
    }
    for(i=0;i<num;i++)
    {
        a=val[i];
        for(j=0;j<num;j++)
        {
                b=val[j];
                for(k=0;k<num;k++)
                {
                        c=val[k];
                        t=a*b+c;
                        a1.push_back(t);
                }
        }
    }
    for(i=0;i<num;i++)
    {
        d=val[i];
        for(j=0;j<num;j++)
        {
                e=val[j];
                for(k=0;k<num;k++)
                {
                        f=val[k];
                        t=(f+e)*d;
                        a2.push_back(t);
                }
        }
    }
    vector<int>::iterator itr;
    for(itr=a1.begin();itr!=a1.end();itr++)
    {
         value=*itr;
         ans+=count(a2.begin(),a2.end(),value);
    }
    printf("%d\n",ans);
    return 0;
}

[saurabhcc]

WHy my code is getting sigsegv?

#include<stdio.h>
#include<algorithm>
#include<utility>
using namespace std;
int compareints (const void * a, const void * b)
{
  return ( *(long*)a - *(long*)b );
}
int main()
	{
	int n,s[101],a,b,c,d,e,f;
	long p1[100009],p2[100009];
	int i,j,k;
	scanf("%d",&n);
	for(i=0;i<n;i++) scanf("%d",&s[i]);
	//sort(s,s+i);
	 k=0;
	for(i=0;i<n;i++)
		{
		for(j=0;j<n;j++)
		{
		for(int l=0;l<n;l++)
			{
			if(s[l])
		p1[k++]=(s[i]+s[j])*s[l];
		}
		}
		}
		//sort(p1,p1+k);
		int x=0;
		for(i=0;i<n;i++)
		{
		for(j=0;j<n;j++)
		{
		for(int l=0;l<n;l++)
			{
			//if(s[l]!=0)
		p2[x++]=(s[i]*s[j])+s[l];
		}
		}
		}
		sort(p2,p2+x);
		long *pItem;
		long count=0;
		for(i=0;i<k;i++)
			{
			pItem = (long*) bsearch (&p1[i], p2, x, sizeof (long), compareints);
			if(pItem){
			long *tmp=pItem;
                        if(pItem==p2)while(*(tmp)==p1[i]&&tmp<p2+x){ count++;tmp++;}
			else
                            if(pItem==(p2+(x-1))) { while(pItem>=p2&&*(pItem)==p1[i]){count++;pItem--;}}
				else{
                                tmp++;
                                while(*(tmp)==p1[i]&&tmp<p2+x){ count++;tmp++;}
                                while(pItem>=p2&&*(pItem)==p1[i]){count++;pItem--;}
				}
			}
			}
			printf("%ld\n",count);
    	
return 0;
}

[leppyr64]

You exceed array bounds.

[leppyr64]

@logic_king:

You should use fixed memory instead of vectors. You have to reallocate memory every time you push_back and that is costly.

More importantly, your algorithm is O(n^6) which is far too slow. You need to find a faster way to do the last portion of your code.

[logic_king]

i got it AC....just by replacing that count function with the upper,lower bound funcn's of binary search in STL