11342 - Three-square

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

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

11342 - Three-square

Post by armansuleimenov » 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
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
Location: CUET , bangladesh
Contact:

Post by shakil » 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
SHAKIL

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

Re: 11342 - Three-square

Post by mrahman » 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.

Thanks in advance

[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

Post by shekhar » 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");
}                                                                         

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

Re: 11342 - Three-square

Post by x140l31 » 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 :wink:
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
Location: Dhaka , Bangladesh
Contact:

Re: 11342 - Three-square

Post by mukit » 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. :wink:
mukit.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11342 - Three-square

Post by Obaida » Thu Jan 29, 2009 10:34 am

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

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

11342 - Three-square

Post by sazzadcsedu » 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;
}


Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

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

Re: 11342 - Three-square

Post by x140l31 » 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

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 11342 - Three-square

Post by sazzadcsedu » 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;
}


Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

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

Re: 11342 - Three-square

Post by helloneo » 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..
How about this way..?

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

instead of

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

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

Re: 11342 - Three-square

Post by hasan3050 » Sat Oct 17, 2009 2:35 pm

smart pre-calculation can save ur time ;)

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

Re: 11342 - Three-square

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

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

Re: 11342 - Three-square

Post by lighted » Sun Dec 14, 2014 12:33 pm

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

Post by IbrahimSharaf » Mon Aug 03, 2015 4:03 am

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

Post Reply

Return to “Volume 113 (11300-11399)”