10655 - Contemplation - Algebra

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

Moderator: Board moderators

Pupirev Sergei
New poster
Posts: 24
Joined: Mon Feb 24, 2003 5:08 pm

10655 - Contemplation - Algebra

Post by Pupirev Sergei » Sat May 22, 2004 4:14 pm

Dear Jury!
What is the tricky input tests of this problem?
Only 5 AC of almost 1000 submits!!!
Last edited by brianfry713 on Wed Sep 10, 2014 9:49 pm, edited 2 times in total.
Reason: thread title

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Sat May 22, 2004 5:09 pm

Yes, I'd really like to know too. Are we all so dumb is something wrong with the input or problem statement here?

At least I learned one thing: don't start on the Manzoor-problems before close to the end of the contest and if you then do, consider only the problems with a solved ratio > 10% :-?

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Sat May 22, 2004 5:22 pm

Thanks Mazoor, you remind us to be humble when we solve problems.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat May 22, 2004 5:48 pm

First I thought that input contains invalid numbers ( -> numbers for which no integers a, b exist with a+b, a*b equal to the numbers in the input).
Shariar Manzoor answered my clarification request and said that there is no line that says that a and b are integers, only a + b and a * b are integers.
So a and b can be imaginary numbers.

For example, if a = i and b = -i, then a+b = 0 and a*b = -i^2 = -(-1) = 1
You can check that whenever a+b, a*b are integers, there is an integer solution to a^n + b^n.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Sat May 22, 2004 6:09 pm

You must be kidding me right? Manzoor's idea was to let us guess that complex numbers are allowed?? What does this have to do with programming???

Just one sample test case where this is used would have been not too much to ask in my opinion. Or, the problem setters could have posted Adrians clarification request, since it seems of great general importance!

Really, does Mr Manzoor enjoy making problems only he can solve himself?

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Sat May 22, 2004 6:11 pm

and what would be the approach then?

to calculate delta (but not its square root).... and depending on the solution of the equation (D<0, D>=0) you shall calculate the whole thing?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat May 22, 2004 6:19 pm

I couldn't solve the problem in Time limit, since I only found a recursion that works in O(n).

a^n + b^n = (a^(n-1)+b^(n-1))*(a+b) - a*b*(a^(n-2)+b^(n-2))

a^0 + b^0 = 2
a^1 + b^1 is given in the input, and then you can calculate it bottom up with DP. But it is too slow.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Sat May 22, 2004 7:01 pm

I'm thinking of writing a letter:

Dear Mr Manzoor,

I have a great idea for your following contest problems. We'll state the problem like this:

'Given a number a. Determine a^2.'

Then, after having seen hundreds of rejected solutions, after the contest, after we've made clear that all input should have output zero, we just say: 'Hey. The problem nowhere states that the input doesn't contain Grassman numbers'.

Maybe that way we can improve your problem E-record of 0.5% AC solutions! What do you think?

Kind regards, Erik

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat May 22, 2004 7:14 pm

Well, I don't think that problem E was so bad. It was a difficult problem, although it seemed to be easy. And I think that it was more my problem that I didn't think of complex numbers; they are very common in math, so if nothing about a and b is said, it is not excluded that a and b might be complex. And the output was well defined, and would be always integer for all given a+b, a*b values.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug » Sat May 22, 2004 7:34 pm

i believe adrian is right.... but why wouldnt it be correct to use the following:

a + b = x
a * b = y

b = x - a
a * (x - a) = y

- a * a + ax - y = 0
a * a - ax + y = 0

delta = x * x - 4 * y

if delta = 0 then
a = b = x / 2
....
easy to finish
else if delta > 0 then
easy to calc a and b
...
easy to finish
else
// we know delta < 0
work it out with a negative delta...

if it works that would be a nice way to get it O(1)....

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Sat May 22, 2004 7:42 pm

Solution idea:

Code: Select all


 a^n + b^n = (a^(n-1)+b^(n-1))*(a+b) - a*b*(a^(n-2)+b^(n-2)) 
 
 Xn = a^n + b^n

 Xn = pXn-1 + qXn-2

 (p q)      (Xn-1)         (pXn-1 + qXn-2)         (Xn  )
        x               =                      =
 (1 0)      (Xn-2)         ( Xn-1 +  0  )          (Xn-1)

 from this 

    (p q)^(n-1)     (X1)     (Xn   )   
                x          = 
    (1 0)           (X0)     (Xn-1)

 Using fast exponentation you can solve this. X0 = 2 and X1 = p

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Sat May 22, 2004 7:48 pm

So E seems to be a cool task after all.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat May 22, 2004 8:07 pm

Xn = pXn-1 + qXn-2

(p q) (Xn-1) (pXn-1 + qXn-2) (Xn )
x = =
(1 0) (Xn-2) ( Xn-1 + 0 ) (Xn-1)
I am really ashamed that I didn't find this. I already solved similar problems, so this should have been easy for me :oops:

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Sat May 22, 2004 8:09 pm

I'm ashamed I didn't think about it in contest time when I knew that Xn = pXn-1 + qXn-2.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

using the O(n) idea

Post by abishek » Mon May 24, 2004 9:15 am

I used the O(n) idea in the problem
i.e a^n+b^n=(a+b)*(a^(n-1)+b^(n-1))-ab(a^(n-2)+b^(n-2))

but i assumed that for n>5000(a simple guess) no a and b exist for which a^n+b^n<2^63
so I tried to evaluate special cases only for n>5000
Am I wrong here
btw
should I assume that there may be inputs of the form
0 0 0
as the problem states that input is terminated by a line containing only two zeros.

Post Reply

Return to “Volume 106 (10600-10699)”