## 11342 - Three-square

Moderator: Board moderators

armansuleimenov
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan
Contact:

### 11342 - Three-square

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
``````
Last edited by armansuleimenov on Tue Nov 13, 2007 8:40 am, edited 1 time in total.

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:
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
SHAKIL

mrahman
New poster
Posts: 25
Joined: Mon Oct 24, 2005 9:45 am
Contact:

### Re: 11342 - Three-square

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]
Practice Makes a man perfect

shekhar
New poster
Posts: 6
Joined: Wed Jul 09, 2008 12:34 pm

### 11342 - Three-square

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
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: 11342 - Three-square

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
Last edited by x140l31 on Tue Jun 30, 2009 1:17 am, edited 1 time in total.

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Contact:

### Re: 11342 - Three-square

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

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11342 - Three-square

Thanks mukit. It's a grate hint to get ACC.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### 11342 - Three-square

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

``````
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: 11342 - Three-square

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

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 11342 - Three-square

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

``````
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11342 - Three-square

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++)

hasan3050
New poster
Posts: 8
Joined: Wed Sep 09, 2009 2:46 am

### Re: 11342 - Three-square

smart pre-calculation can save ur time

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

### Re: 11342 - Three-square

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

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 11342 - Three-square

I solved it by precalculating with DP in 0.076.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

IbrahimSharaf
New poster
Posts: 1
Joined: Mon Aug 03, 2015 3:58 am

### Re: 11342 - Three-square

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