11436 - Cubes - EXTREME!!!

[andysoft]

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!

[Jan]

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.

[andysoft]

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...

[Robert Gerbicz]

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]

Hello!
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

Am I wrong?

[Jan]

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.

[andysoft]

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

Code: Select all

spoilers out

[Robert Gerbicz]

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.

[Jan]

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.

[andysoft]

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

[Robert Gerbicz]

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

Let's see your problem:

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]

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

[Jan]

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?

[andysoft]

Thank you guys, Rob and Jan very much! (Guess my result now
I hope I will have chance to help you some day.

Removing my codes...

[shakil]

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