11436 - Cubes - EXTREME!!!

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11436 - Cubes - EXTREME!!!

Post by andysoft » Fri Apr 04, 2008 11:34 pm

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!
Now I lay me down to sleep...
my profile

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

11436 - Cubes - EXTREME!!!

Post by Jan » Sat Apr 05, 2008 12:27 am

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

Post by andysoft » Sat Apr 05, 2008 3:12 pm

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

Post by Robert Gerbicz » Sat Apr 05, 2008 3:26 pm

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

Post by andysoft » Sun Apr 06, 2008 5:09 pm

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?
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
Location: Dhaka, Bangladesh
Contact:

Re: 11436 - Cubes - EXTREME!!!

Post by Jan » Sun Apr 06, 2008 9:05 pm

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

Post by andysoft » Sun Apr 06, 2008 11:51 pm

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

Post by Robert Gerbicz » Mon Apr 07, 2008 1:13 am

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
Location: Dhaka, Bangladesh
Contact:

Re: 11436 - Cubes - EXTREME!!!

Post by Jan » Mon Apr 07, 2008 1:15 am

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

Post by andysoft » Wed Apr 09, 2008 8:12 pm

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

Post by Robert Gerbicz » Wed Apr 09, 2008 11:31 pm

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)...
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
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11436 - Cubes - EXTREME!!!

Post by andysoft » Thu Apr 10, 2008 8:08 pm

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
Location: Dhaka, Bangladesh
Contact:

Re: 11436 - Cubes - EXTREME!!!

Post by Jan » Fri Apr 11, 2008 12:51 am

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

Post by andysoft » Fri Apr 11, 2008 5:56 pm

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... :)
Now I lay me down to sleep...
my profile

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

11436 - Cubes - EXTREME!!!

Post by shakil » Fri Sep 19, 2008 8:46 pm

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

Post Reply

Return to “Volume 114 (11400-11499)”