10655 - Contemplation - Algebra

[shahriar_manzoor]

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]

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]

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]

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]

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]

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]

I got 5+ WA during contest in this problem, please help.

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.

Thanks in advance.
-Dreamer

[Marcin Kwiatkowski]

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.

[UFP2161]

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]

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]

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]

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]

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]

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]

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]