10655 - Contemplation - Algebra

[Pupirev Sergei]

Dear Jury!
What is the tricky input tests of this problem?
Only 5 AC of almost 1000 submits!!!

[Maniac]

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]

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

[Adrian Kuegel]

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]

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]

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]

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]

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]

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]

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]

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]

So E seems to be a cool task after all.

[Adrian Kuegel]

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]

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

[abishek]

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.