## 10655 - Contemplation - Algebra

Moderator: Board moderators

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### Hmm!

Perhaps! I am the problem setter with highest number of problems . You participate in contests to enjoy and I also set problems for the same reason. Sometimes I have to do some experiments to enjoy. This problem was such a experiment with all those nasty tricks. For example:

a) Input is terminated by a line containing 0 0, not "0 0 0" and there were inputs like "0 0 3" so many were trapped.

b) a and b could be complex.

c) Still there were inputs like "1 0 200000000" or "2 1 200000000" so yes fast exponentiation was required or you had to handle this case expecially.

And still there are some more traps.

I was actually so worried, I had no time to set a difficult problem but somehow I had to keep you busy for five hours. Problem G was difficult but I knew few people will understand and try it.

Allmost all elite problem setters have some problems which only he can solve and with it a few others. As my number of problems is highest so is the no of nasty problems.

I should have been slammed for problem F (which was wrong) not problem E I guess .
Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
OK, that complex numbers are involved, maybe, very maybe some people could have thought of that during contest time (like Adrian Kuegel, but he needed a hint from you too!).

But that input contains lines like 0 0 3 that should be processed beats it all! What the heck does this have to do with programming skills or knowledge of algorithms?

Please, I beg you, next time make real problems without dumb traps to spoil all our time. After all, it's a PROGRAMMING contest and not a (mind)READING contest!
Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland
PS if you want to know wether you've been slammed for problem F, see the other thread '22.05.04 Contest Problem F'. It's not full of praise as well...
shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### Hmm

Well,
As I said my intension is to make problem solvers read problem statement carefully and think about all the traps.

It is a O-level math

If a+b=2 ab =7 find the value of a^5+b^5.

I set this problem from that math. And when I did this sort of Algebra I had no idea about complex numbers. may be the math culture of your country is different.

a^3+b^3=(a+b)^3-3ab*(a+b) and such forms can be found for higher powers using lower powers.
technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

### Re: Hmm!

shahriar_manzoor wrote:Sometimes I have to do some experiments to enjoy. This problem was such a experiment with all those nasty tricks. For example:

a) Input is terminated by a line containing 0 0, not "0 0 0" and there were inputs like "0 0 3" so many were trapped.
This is the nasty one..... all other tricks should have been expected if one is to solve a difficult problem....
And still there are some more traps.
wow....
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### indeed a nice one

After having solved it finally i feel that it is indeed a nice one, but then, may be some pity must have been shown on the solvers. Not too many traps on one problem that too in a contest.
abi
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

### 10655 - Contemplation! Algebra

Code: Select all

Input:

2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
0 0

Output:

2
0
-4
-8
-8
0

Are the above outputs for the respective inputs ok?
If yes please give some more inputs,
else if wrong then please give the right output.

-Dreamer
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
Marcin Kwiatkowski
New poster
Posts: 5
Joined: Thu Jan 01, 2004 10:43 pm
Location: Gdynia, Poland
Hi Dreamer!
In my opinion your input are wrong because there doesn't exist such integer that a+b=2 and a*b=2.

If you tried solving those equations you would be given:
a*(2-a)=2
-a^2 + 2a - 2 = 0

delta = 4-4*(-1)*2 = -4 <0 => there is no integer a.

Or maybe I misunderstood everything... Anyway, I had also some difficulties with that problem and I still dont know what tricky inputs had been made. Problem seems to be easy but... If anybody who have solved it could write some inputs I would be grateful.
"Imagination is more important than knowledge" Albert Einstein
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
The equation still has a solution. It's just not part of the real number line.

Read the other post concering this matter:
http://online-judge.uva.es/board/viewtopic.php?t=5688
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

### some test cases

you may want to try out some test cases like this

10 11 2
1 1 10000
2 2 11
0 0 3
0 0 4
12 13 5
1 1 0
1 1 1
0 0

my ac program gives

78
-1
-64
0
0
146652
2
1
The Class
New poster
Posts: 1
Joined: Sat May 29, 2004 8:50 pm

### Why make it so complex?!

What's wrong with this one, it gives WA!
[cpp]
#include <iostream>
#include <complex>
#include <cmath>
#include <stdio.h>

using namespace std;

int main() {
long pi = 0, qi = 0, ni = 0;

while (scanf("%d %d %d", &pi, &qi, &ni) > 2) {
double p = pi;
double q = qi;
double n = ni;

complex<double> temp = complex<double>(p * p - 4 * q, 0);
complex<double> a = (p + sqrt(temp)) / 2.0;
complex<double> b = (p - sqrt(temp)) / 2.0;
complex<double> d = pow(a, n) + pow(b, n);
cout << real(d) << endl;

}

return 0;
}

[/cpp]

I'm new here. what compiler does oj use, where can i get it? i get a lot ce, runs ok in my comp(vc++).
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
hi,
one hard lesson that i have learnt is never use doubles when the problem can be solved in integers.
try to do it only with integers.
abi
InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm
Try to solve this by DP.
Because test data must contain complex numbers.
(I originally used solve a+b, a*b individually)

After using DP, it still contains a prob....a large exp.
So u must find the iteration to simplify prob.
(eg: a+b = 0, a*b = 1. a= i^3, b=-i^3)

good luck
shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm
After countless tries, I finally got AC, it certainly has alot of traps, I ended up with a whole list of if statements to catch each of the traps in my program...

Need to catch the following
n==0
p==0 && q==0
p==1 && q==0
p==0 && q==1
p==2 && q==1

Input

Code: Select all

0 0 0
0 0 1
0 0 200000000
1 3 0
999999 999999 0
1 0 200000000
2 0 61
2 1 0
2 1 100
2 1 200000000
0 0 0
0 1 1
0 1 2
0 1 3
0 1 199999999
0 1 200000000
0 1 200000001
0 1 200000002
5 6 7
10 20 10
90 87 3
999 231 2
0 0
Output:

Code: Select all

2
0
0
2
2
1
2305843009213693952
2
2
2
2
0
-2
0
0
2
0
-2
2315
393600000
705510
997539
htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### 10655

I think it's not a hard one, and not finding out any mistake in my code. But I use Dev-C++ compiler and not getting the right result. I don't know the problem is syntax or type changing or something else.. Is there someone willing to run the prog for me and see what's wrong?
[c]
#include<stdio.h>
#include<math.h>
long long power(long long,long);
void main(void)
{
long p,q,c;
long long a,b;
while(1)
{
scanf("%ld %ld",&p,&q);
if(p==0 && q==0)
break;
scanf("%ld",&c);
a=(p+sqrt(p*p-4*q))/2,b=p-a;
printf("%lld\n",power(a,c)+power(b,c));
}
}
long long power(long long a,long c)
{
int x;
long long t,ans;
if(c==0 || a==1)
return 1;
if(a==0)
return 0;
if(c==1)
return a;
for(t=a,x=0,ans=1;x<64;x++)
{
if(t<64)
t*=t;
if(c%2==1)
ans*=t;
c/=2;
}
return ans;
}
[/c]