1 - Sort the input in non-decreasing order into num
2 - nt = 0
3 - Iterate from i=3..n
j = 0
k = i - 1
While (j < k)
sum = num[j] + num[k]
if (sum < num[i])
++j // discard the element from the left end
else if (sum > num[i])
--k // discard the element from the right end
else // new triple
if (num[j] == num[k]) // e.g.: 1 1 1 1 1 2
nt += c(k-j+1, 2) // binomial coefficient (e.g.: c(5, 2) = 10)
j = k // stop here
else
j2 = first element != num[j] && > j
k2 = first element != num[k] && < k
assert(j2 <= k2)
nt += (j2-j) * (k-k2)
j = j2
k = k2
4 - Print nt as result
Any hints?
Last edited by mpi on Sat Jan 12, 2008 7:14 pm, edited 1 time in total.
Sorry. I was only talking about my own algorithm. I use for loop only for smallest and largest number in the tuple. It is also good to "group" the repeated numbers.
7th Contest of Newbies Date: December 31st, 2011 (Saturday) Time: 12:00 - 16:00 (UTC) URL: http://uva.onlinejudge.org
Hi!
Firstly, I did simple O(n^2*logn) program, but it didn't pass. Then I used my own hash table and after some troubles with RE I got AC! (3.470s). Can anyone tell me how to solve it with O(n^2) but without hashing?
The O(n^2) algorithm doesn't need any hashing mecanishm. All you have to do is, at each step i, iterate over the elements in the range j=1,..,k=i-1. Depending on the sum of the elements of both ends you will have to update j and k properly (incrementing j and/or decreasing k). The loop ends with j >= k (with no grouping) and with j > k (with grouping).