10732 - The Strange Research

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

Moderator: Board moderators

Post Reply
miquel
New poster
Posts: 2
Joined: Thu Oct 14, 2004 8:58 pm

10732 - The Strange Research

Post by miquel »

Although I think I have solved this problem, I am always having WA.

I have generated random inputs and checked the number of solutions with the slow n^2 algorithm. I have tried with large inputs and get the same answer with both methods.

Is there any trick with repeated numbers or comparing to 10^-15?
Can you give me other inputs?

Thanks!
Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Check out 0?

Post by Miguel Angel »

Well, the problem is quiet easy, though some tricky..I thought I have solved the problem too but then I realized I missed some case..You first check the combinations of signs and get the good ones..I missed one case a = 0, b = +.
:D Miguel & Marina :D
miquel
New poster
Posts: 2
Joined: Thu Oct 14, 2004 8:58 pm

Post by miquel »

Ok!
It was just an stupid mistake with the computation of one of the cases.
Now I got AC!
Thanks a lot.
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Any hints for solving this problem under O(N^2) ?! :)
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

From the Problem Statistics of this problem it is obvious that very
few people have solved it. But the huge part of those who solved
it, seem to have solved it with quite an efficient algorithm.
I am wondering if it is linear O(N) or maybe O(N*logN).

I devised an algorithm which in the worst case has O(N^2)
time complexity. This worst case for my algorithm comes when
all numbers are positive or when all numbers are negative. In the
other cases my algorithm does some small tricks which make
the running time better. But this algorithm gives me a running time
of about 6.5 sec. Which is quite bad.

I sill can not find the right idea for an O(N) or an O(N*logN) solution ...
I guess it is quite a tricky one... Any hints ( even tiny ones )
are highly welcome.
mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Sorting and binary search will solve it in O(n log n).

The condition (a+b)(1-ab)>0 is equivalent to the system: (a+b>0 and 1-ab>0) or (a+b<0 and 1-ab<0).
For a fixed `a', each part of this system is just two linear inequalities which give bounds on the value of b.
Two binary searches can give you the indices of the smallest and the largest numbers from the input, which satisfy them. After that you can find the total number of possible b's in O(1).
Post Reply

Return to “Volume 107 (10700-10799)”