11436 - Cubes - EXTREME!!!

Moderator: Board moderators

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

11436 - Cubes - EXTREME!!!

Hello world!
I have solved the easy version of this problem (11428 - Cubes), and now I am trying to solve harder version (11436 - Cubes - EXTREME!!!). My approach was to try all y variables in range [1 .. sqrt((n+1)/2) ] and for all of them to compute x. If x is integer (it's floor equals itself with some eps (1e-6) error), we found answer.
Of course, this solution gives TLE on the harder problem. Any hint on improving, people?

Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

11436 - Cubes - EXTREME!!!

Spoiler:

N = x^3 - y^3
= ( x-y ) ( x^2 + xy + y^2 )

We are sure that (x-y) is a divisor of N.
Say,
k = x-y
=> x = k + y

So,
N = k ( (k + y)^2 + (k+y) y + y^2 )
= k ( k^2 + 2ky + y^2 + ky + y^2 + y^2 )
= k ( k^2 + 3ky + 3y^2 )

Now for all divisors of N try to find y.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11436 - Cubes - EXTREME!!!

Jan, isn't the complexity of this algorithm about O (sqrt(n))? To factorize N (not prime factorization), it takes O (sqrt(n)) I guess.
I say it because sqrt(n) is about 5.000.000 and there are 2.500 lines in the input and TL is 4 seconds...
Last edited by andysoft on Sat Apr 05, 2008 3:33 pm, edited 1 time in total.
Now I lay me down to sleep...
my profile

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11436 - Cubes - EXTREME!!!

andysoft wrote:Jan, isn't the complexity of this algorithm about O (sqrt(n))? To factorize N (not prime factorization), it takes O (sqrt(n)) I guess.
I say it because sqrt(n) is about 5.000.000 and there 2.500 lines in the input and TL is 4 seconds...
I think you've missed the fact, that:
1<=k<=N^(1/3)

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11436 - Cubes - EXTREME!!!

Hello!
First of all, thank you for your help, Jan and Robert!
I followed logic:

Code: Select all

``````spoiler removed
``````
Am I wrong?
Last edited by andysoft on Sun Apr 06, 2008 11:27 pm, edited 1 time in total.
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: 11436 - Cubes - EXTREME!!!

Check your output for 8 or 1000. You may get wrong output according to the description.

P.S I think your message is a spoiler. So, edit your post as quickly as possible.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11436 - Cubes - EXTREME!!!

Seeing the keyword positive didn't make my solution AC.
I think nothig's left except showing my code.

Code: Select all

``````spoilers out
``````
Last edited by andysoft on Fri Apr 11, 2008 5:57 pm, edited 1 time in total.
Now I lay me down to sleep...
my profile

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11436 - Cubes - EXTREME!!!

andysoft wrote:Seeing the keyword positive didn't make my solution AC.
I think nothig's left except showing my code.
The computed discriminant is wrong.
And why are you using doubles? This can give some precision problems.
The problem is solvable by only integer arithmetic (you have to use long long int for some vaiables because
for example the discriminant can be >2^32).
To test if a given number is a square is also solvable by integer arithmetic:

Code: Select all

``````if u<0 then it isn't square
else {
w=sqrt(u)
if((w*w)!=u)   then  u isn't square
else  u is square
}
``````
The last lines are also complicated, you don't need cube root, for example if you know k=x-y and you've solved the
quadratric equation then you know y, but in this case x=k+y.
Last edited by Robert Gerbicz on Mon Apr 07, 2008 1:15 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: 11436 - Cubes - EXTREME!!!

I don't have any pascal compiler. But (If I understood your code correctly!!!) I can say that your code is not fully correct.

The reason is quite simple. When k is minimum it doesn't necessarily mean that y will be minimum. It mens that (x-y) is minimum. So, solutions can exist where k is not minimum but y is minimum.

And of course there is no need to take y1(check carefully!). And your code can be made simpler.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11436 - Cubes - EXTREME!!!

Robert Gerbicz, I cannot find my mistake with discriminant, I've re-calculated it two times, but it's still D = 12*k*N - 3*(k^4)...
Now I lay me down to sleep...
my profile

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Re: 11436 - Cubes - EXTREME!!!

andysoft wrote:Robert Gerbicz, I cannot find my mistake with discriminant, I've re-calculated it two times, but it's still D = 12*k*N - 3*(k^4)...

Code: Select all

``````k=x-y
N=k*(k^2+3ky+3y^2)
from this N/k=3*y^2+3*k*y+k^2 so:
3*y^2+(3*k)*y+(k^2-N/k)=0  this is a quadratric equation for y variable
discriminant=(3*k)^2-4*3*(k^2-N/k)=12*N/k-3*k^2
``````

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11436 - Cubes - EXTREME!!!

I think both variants of finding discriminants are correct as the difference is that we followed different ways to simplify the equation and get free of variable x.
but even with your way of finding discriminant and y, my solution gets WA. I don't know what to do, I already have 9 submissions which are all wrong.

Code: Select all

``````spoilers out
``````
Last edited by andysoft on Fri Apr 11, 2008 5:57 pm, edited 1 time in total.
Now I lay me down to sleep...
my profile

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: 11436 - Cubes - EXTREME!!!

Code: Select all

``y := (-3*k + floor(sqrt(d)+1e-6)) div 6; //compute y from quadratic equation``
What if (-3*k + floor(sqrt(d)+1e-6)) is not divisible by 6?
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11436 - Cubes - EXTREME!!!

Thank you guys, Rob and Jan very much! (Guess my result now

Removing my codes...
Now I lay me down to sleep...
my profile

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Contact:

11436 - Cubes - EXTREME!!!

Why WA?????

Code: Select all

``````#include<stdio.h>
#include<iostream.h>
#include<math.h>

long long Z,X,Y,n,t,p,k,sa,si;

double q;

int main()
{

Z=pow(10,15);

while(1)
{
cin>>n;

if(n==0)
break;
X=Z;
Y=Z;

t=sqrt(n);
if(t*t==n)
{
X=t;
Y=0;
}

for(t=1;;t++)
{
if(t*t*t>n)
break;
if((4*n-t*t*t)>=0)
{
p= 4*n-t*t*t;
p = p * t;
p=p*3;
q=p;
q=sqrt(q);
q=q+0.00001;
k=q;
if(k*k==p)
{
sa=k-3*t*t;
if(sa%(6*t)==0)
{
si=sa/(6*t);
if(Y>si)
{Y=si;X=si+t;}
}
}
}
}
if(Y==Z)
printf("No solution\n");
else
cout<<X<<" "<<Y<<endl;

}
return 0;
}

``````
SHAKIL