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!
10732 - The Strange Research
Moderator: Board moderators
-
Miguel Angel
- Learning poster
- Posts: 60
- Joined: Tue Aug 13, 2002 2:39 am
- Location: Mexico
Check out 0?
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 = +.
Miguel & Marina 
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.
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.
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).
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).