Page 1 of 1

### 11342 - Three-square

Posted: Tue Nov 13, 2007 7:17 am
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
``````

Posted: Tue Nov 13, 2007 7:31 am
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

### Re: 11342 - Three-square

Posted: Tue Jun 10, 2008 8:53 am
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.

[Sorry for my poor english]

### 11342 - Three-square

Posted: Fri Jul 11, 2008 6:57 pm
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");
}
``````

### Re: 11342 - Three-square

Posted: Sat Aug 23, 2008 2:31 am
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

### Re: 11342 - Three-square

Posted: Fri Jan 23, 2009 5:22 pm
For any integer n if n mod 8 equals 7, then n cann't be the sum of three integer squares.
mukit.

### Re: 11342 - Three-square

Posted: Thu Jan 29, 2009 10:34 am
Thanks mukit. It's a grate hint to get ACC.

### 11342 - Three-square

Posted: Fri Jun 26, 2009 11:46 pm
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;
}

``````

### Re: 11342 - Three-square

Posted: Tue Jun 30, 2009 1:16 am
sazzadcsedu wrote:can anyone tell me how to optimize it.i got tle.
try comparing the sum i*i+j*j don't exceed n

### Re: 11342 - Three-square

Posted: Wed Aug 12, 2009 11:46 pm
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;
}

``````

### Re: 11342 - Three-square

Posted: Thu Aug 13, 2009 3:32 pm
sazzadcsedu wrote:I changed some portion but still TLE.Can anyone help??
sqrt() takes a lot of time..

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

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

### Re: 11342 - Three-square

Posted: Sat Oct 17, 2009 2:35 pm
smart pre-calculation can save ur time

### Re: 11342 - Three-square

Posted: Fri Aug 05, 2011 6:46 am
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.

### Re: 11342 - Three-square

Posted: Sun Dec 14, 2014 12:33 pm
I solved it by precalculating with DP in 0.076.

### Re: 11342 - Three-square

Posted: Mon Aug 03, 2015 4:03 am
this is my code: http://codepad.org/S05IoyBJ, and I am getting TLE, any help?