10655 - Contemplation - Algebra
Moderator: Board moderators
-
- 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!!!
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
Reason: thread title
-
- 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.
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.
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?
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?
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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
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.
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)....
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)....
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
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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.
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.