10655 - Contemplation - Algebra

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Hmm!

Post by shahriar_manzoor » Mon May 24, 2004 11:57 am

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

Post by Maniac » Mon May 24, 2004 12:21 pm

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

Post by Maniac » Mon May 24, 2004 12:27 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Hmm

Post by shahriar_manzoor » Mon May 24, 2004 1:07 pm

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!

Post by technobug » Mon May 24, 2004 2:15 pm

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....

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

indeed a nice one

Post by abishek » Tue May 25, 2004 9:40 pm

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

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

10655 - Contemplation! Algebra

Post by Dreamer#1 » Tue May 25, 2004 10:26 pm

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? :o
If yes please give some more inputs,
else if wrong then please give the right output.

Thanks in advance.
-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

Post by Marcin Kwiatkowski » Tue May 25, 2004 10:46 pm

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

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue May 25, 2004 11:39 pm

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

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

some test cases

Post by abishek » Wed May 26, 2004 7:06 am

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?!

Post by The Class » Mon May 31, 2004 2:06 pm

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++).

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

Post by abishek » Mon May 31, 2004 3:40 pm

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

Post by InOutMoTo » Wed Jun 02, 2004 8:43 am

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 :D

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu » Tue Jun 08, 2004 7:09 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

Post by htl » Tue Jun 15, 2004 5:57 pm

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]

Post Reply

Return to “Volume 106 (10600-10699)”