11436 - Cubes - EXTREME!!!
Moderator: Board moderators
-
- 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?
Thank you in advance!
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?
Thank you in advance!
Now I lay me down to sleep...
my profile
my profile
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.
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
HomePage
-
- 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...
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
my profile
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
Re: 11436 - Cubes - EXTREME!!!
I think you've missed the fact, that: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...
1<=k<=N^(1/3)
-
- 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!
But I constantly receive Wrong Answer verdicts from Judge.
I followed logic:
Am I wrong?
First of all, thank you for your help, Jan and Robert!
But I constantly receive Wrong Answer verdicts from Judge.
I followed logic:
Code: Select all
spoiler removed
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
my profile
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.
P.S I think your message is a spoiler. So, edit your post as quickly as possible.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- 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.
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
my profile
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
Re: 11436 - Cubes - EXTREME!!!
The computed discriminant is wrong.andysoft wrote:Seeing the keyword positive didn't make my solution AC.
I think nothig's left except showing my code.
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
}
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.
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.
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
HomePage
-
- 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
my profile
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
Re: 11436 - Cubes - EXTREME!!!
Let's see your problem: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
-
- 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.
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
my profile
Re: 11436 - Cubes - EXTREME!!!
Code: Select all
y := (-3*k + floor(sqrt(d)+1e-6)) div 6; //compute y from quadratic equation
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- 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 ![:)](./images/smilies/icon_smile.gif)
I hope I will have chance to help you some day.
Removing my codes...![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
I hope I will have chance to help you some day.
Removing my codes...
![:)](./images/smilies/icon_smile.gif)
Now I lay me down to sleep...
my profile
my profile
-
- Learning poster
- Posts: 74
- Joined: Sat Jul 15, 2006 6:28 am
- Location: CUET , bangladesh
- 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