11342 - Three-square

[armansuleimenov]

this is my function that given k returns the vector that contains a,b,c such that a*a+b*b+c*c = k, however it's too slow (TLE), what optimization will speed it up?

Code: Select all

got AC

[shakil]

You can optimize it by memorizing.1st you find all the value.Then only scan and print it's value.
0 < K <= 50000

so, loop1 0 to sqrt(50000)
loop2 loop1 to sqrt(50000)
loop3 loop2 to sqrt(50000)

because a <= b <= c and K = a2 + b2 + c2

[mrahman]

hi!

can anyone tell me what is the meaning of "If there is more than one possible answer, print the one that comes first lexicographically" in this problem?
P.S. I have solved the problem before getting a wrong answer because I had diverted by the line.

Thanks in advance

[Sorry for my poor english]

[shekhar]

My code is getting TLE....plz help
what kinda optimization can be done ???

Code: Select all

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int i,j,k,n,test;
    scanf("%d",&test);
    while(test--)
    {
                 scanf("%d",&n);
                 int flag=0;
                 int t=(int)sqrt(n);
                 
                 for(i=0;i<=t;i++)
                 {
                   for(j=i;j<=t;j++)
                   {
                       for(k=j;k<=t;k++)
                       {
                          if(i*i+j*j+k*k==n)
                          {
                            flag=1;                
                            break;
                          }
                       }
                       if(flag==1)
                       break;
                   }
                   if(flag==1)
                   break;
                 }
                 if(flag==1)
                 printf("%d %d %d\n",i,j,k);
                 else
                 printf("-1\n");
    }
    system("pause");
}                                                                         

[x140l31]

It can be optimized?

CODE REMOVED

Thanks to mukit.

If anyone want to know why any number (n mod 8 == 7) can't be the sum of 3 squares, see that any square mod 8 only can be 0, 1, 4

[mukit]

For any integer n if n mod 8 equals 7, then n cann't be the sum of three integer squares.
mukit.

[Obaida]

Thanks mukit. It's a grate hint to get ACC.

[sazzadcsedu]

can anyone tell me how to optimize it.i got tle.
my code

Code: Select all

/*
problem no:11342
problem title:three squre
*/
#include<stdio.h>
#include<math.h>
#include<string.h>

int num[60000][4];
int aa[60000];
int squre[100000];



int main()

{
	int i,j,k,a,b,c,n,ncase,flag,found;

	scanf("%d",&ncase);
	memset(aa,0,sizeof(aa));

	memset(squre,0,sizeof(squre));
	for(i=0;i<=sqrt(50001);i++)
	{
		squre[i*i]=1;
	}

	while(ncase>0){

		scanf("%d",&n);

		if(n%8==7){			//if (num%8==7) not possible.
			printf("-1\n");
			ncase--;
			continue;
		}

		if(squre[n]==1)    //checking whether  a squre number,
		{
			printf("0 0 %d\n",(int)sqrt(n));
			ncase--;
			continue;
		}

		if(aa[n]==1){		//checking whether calculated previously(memoization)
			printf("%d %d %d\n",num[n][0],num[n][1],num[n][2]);
			ncase--;
			continue;
		}
							//else
		
		flag=0;
		found=0;
		for(i=0;i<=sqrt(n);i++)
		{
			for(j=i;j<=sqrt(n);j++)
			{
				for(k=j;k<=sqrt(n);k++)
				{
					a=i*i;
					b=j*j;
					c=k*k;

					if(n==a+b+c){
					printf("%d %d %d\n",i,j,k);
					flag=1;
					aa[n]=1;
					num[n][0]=i;
					num[n][1]=j;
					num[n][2]=k;
					found=1;
					break;
					}
				}
				if(flag==1)
					break;
			}
			if(flag==1)
				break;
		}
		if(found==0)
			printf("-1\n");
		
		ncase--;
	}
	return 0;
}

[x140l31]

can anyone tell me how to optimize it.i got tle.

try comparing the sum i*i+j*j don't exceed n

[sazzadcsedu]

I changed some portion but still TLE.Can anyone help??

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>

int num[60000][4];
int aa[60000];
int squre[100000];



int main()

{
	int i,j,k,a,b,c,n,ncase,flag,found;

	scanf("%d",&ncase);
	memset(aa,0,sizeof(aa));

	memset(squre,0,sizeof(squre));
	for(i=0;i<=sqrt(50001);i++)
	{
		squre[i*i]=1;
	}

	while(ncase>0){

		scanf("%d",&n);

		if(n%8==7){			//if (num%8==7) not possible.
			printf("-1\n");
			ncase--;
			continue;
		}

		if(squre[n]==1)    //checking whether  a squre number,
		{
			printf("0 0 %d\n",(int)sqrt(n));
			ncase--;
			continue;
		}

		if(aa[n]==1){		//checking whether calculated previously(memoization)
			printf("%d %d %d\n",num[n][0],num[n][1],num[n][2]);
			ncase--;
			continue;
		}
							//else
		
		flag=0;
		found=0;
		for(i=0;i<=sqrt(n);i++)
		{
			for(j=i;j<=sqrt(n);j++)
			{
				if(i*i+j*j>n)
				{
					flag=1;
					break;
				}
				for(k=j;k<=sqrt(n);k++)
				{
					a=i*i;
					b=j*j;
					c=k*k;

					if(a+b+c==n){
					printf("%d %d %d\n",i,j,k);
					flag=1;
					aa[n]=1;
					num[n][0]=i;
					num[n][1]=j;
					num[n][2]=k;
					found=1;
					break;
					}
					if(a+b+c>n){
						//flag=1;
						break;
					}

				}
				if(flag==1)
					break;
			}
			if(flag==1)
				break;
		}
		if(found==0)
			printf("-1\n");
		
		ncase--;
	}
	return 0;
}

[helloneo]

I changed some portion but still TLE.Can anyone help??

sqrt() takes a lot of time..
How about this way..?

for (i = 0; i * i <= n; i++)

instead of

for (i = 0; i <= sqrt(n); i++)

[hasan3050]

smart pre-calculation can save ur time

[plamplam]

I solved it without utilizing Mukit's hint in 0.068 seconds. (In fact most of the times I only check the board after solving a problem). However thanks to mukit my runtime decreased to 0.032 after considering the hint given away.

For those getting TLE, it is a brute force problem. Your approach is correct but you have to think smarter.

[lighted]

I solved it by precalculating with DP in 0.076.

[IbrahimSharaf]

this is my code: http://codepad.org/S05IoyBJ, and I am getting TLE, any help?