HINHTHOI
A four-sided polygon is a rhomb if and only if it has two perpendicular diagonals intersecting each other at their mid-points.
From this observation we have the following O(n^2logn) algorithm:
We maintain a list of segments, each segment is a diagonal formed by a pair of points in our set. In particular, for each pair (x1, y1) and (x2, y2) we store two segments with 3 information:
- Coordinates of mid-point: ((x1 + x2) / 2, (y1 + y2)/2) (we can store (x1+ x2, y1 + y2) instead to avoid floating-point numbers). These coordinates are the same for both segments.
- Gradient: one segment has gradient (x2 - x1) / (y2 - y1) while the other has gradient (y1 - y2) / (x2 - x1)
- Type: the former has type 1 while the latter has type 2
After that, we sort all segments according to their (mid-point coordinates , gradient). For each interval that has equal (mid-point coordinates , gradient) values in the list, the number of rhomb is number of type-1 segments * number of type-2 segments. Finally, we have to divide the result by 2 because each rhomb is counted twice in our algorithm.

DIGIT0
Let N be the length of our string and f[c] is the number of occurence of character c in our string. The number of different permutations is n! / (f['a']! * f['b]! * ... f['z']!). To count the number of trailing zeroes, we have to count the number of divisor 2 and divisor 5 of the above number. The number of divisor d of k! is:
divisor(k, d) = floor(k / d) + floor(k / (d^2)) + floor(k / (d^3)) + ...
The number of trailing zeroes is:
min(divisor(n, 2) - divisor(f['a'], 2) - ... - divisor(f['z'], 2), divisor(n, 5) - divisor(f['a'], 5) - ... - divisor(f['z'], 5))

Regarding the problem DIGIT0, can you please check if there is an endline character at the end of the input string? I think that this is common practice and it should be there, even if it is not mentioned in the problem statement.
The way it is now, my solution gets 0 points.

minhduc wrote:

QUOTE:

HINHTHOI...
From this observation we have the following O(n^2logn) algorithm:

There is also an O(n^2+bound^2) algorithm for the problem if for all (x,y) points |x|,|y|<=bound is true (bound=50 in our problem).

@supo: The test cases have been added with endline character and the submissions are rejudged.
@gerrob: Could you describe your algorithm?

Somewhat it is similar to the sample solution.
First observe that if the midpoint of two points is (xd,yd), then (2*xy,2*yd) is a grid point and |2*xd|,|2*yd|<=2*bound. Let the gradient is (mx,my) (where mx and my is an integer) and normalize it, say gcd(mx,my)=1 and mx>=0 (if mx=0 then my>0), here also |mx|,|my|<=2*bound. So store the (midpoint,gradient) in a linked list, where in each list the midpoints are same. If you've done this for each pair of points then you can now go through on each possible midpoint and count the equal gradients. (mx,my) is perpendicular to (nx,ny) if and only if:
1. if my>=0 then nx=my and ny=-mx
2. if my<0 then nx=-my and ny=mx
[the reason for this that the gradients are normalized].
In O(1) time it is possible to check if the other gradient is already used at this midpoint and if yes, then we add the number of these gradients to the total number of rhombs. [for this I'm using also a check array, it's size (4*bound+1)^2, the same as the count array, (obviously (4*bound+1)^2 is the number of grid points in the larger grid |x|,|y|<=2*bound)].

I'm also counting the number of perpendicular gradients, just one example: if:
(ax,ay) and (bx,by) is perpendicular to (cx,cy) and (dx,dy) and (ex,ey) and say the order in the list is a,c,b,d,e then
1. at "a" we don't find a collision
2. at "c" we find one collision, and 1 to the number of rhombs
3. at "b" we find one collision, add 1
4. at "d" we find two collisions, add 2
5. at "e" we find two collisions, add 2
So we've added 1+1+2+2=6 this is the same number in your method, but you've used multiplication for this 2*3=6.

I guess the first part of your algorithm should be O(n^2log(bound)) since we have to call GCD to normalize the fraction. Memory requirement is O(bound^2). For small bound it is faster than the solution. At first I generated the points in [-10^9, 10^9] range but the number of rhombs is so small so I reduced it to 50.

No. You can precompute all possible gcd(x,y) values for |x|,|y|<=2*bound in O(bound^2*log(bound)) time by 3 loops, or optimize it to reach O(bound^2*loglog(bound)). But I think this can be done also in O(bound^2) using Farey sequence or Stern Brocot tree.

thanks