## 10655 - Contemplation - Algebra

Moderator: Board moderators

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

### 10655 - Contemplation - Algebra

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.

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
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
Thanks Mazoor, you remind us to be humble when we solve problems.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
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:
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?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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:
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
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
So E seems to be a cool task after all.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
I'm ashamed I didn't think about it in contest time when I knew that Xn = pXn-1 + qXn-2.

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

### using the O(n) idea

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.