Triplets | HackerRank

Triplets | HackerRank
There is an integer array d which does not contain more than two elements of the same value. How many distinct ascending triples (d[i] < d[j] < d[k], i < j < k) are present?

Sample input:
6
1 1 2 2 3 4

Explanation:
The distinct triplets are
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)

Instead of counting the number of distinct ascending triples, let's count the number of ascending tuples first.

So the problem here is very easy. For each number a[i], we only need to know how many numbers before a[i] are smaller than this number. Many data structures can support this type of query but for this problem I would recommend Fenwick tree. You may also check this TopCoder tutorial page to learn more about this data structure.

In short, a Fenwick tree can support two types of operations in logarithmic time complexity. One is to add a number x to a particular number a[i]. The other is to query the sum of numbers from a[1] to a[i].

Therefore, the number of integers smaller than a[i] is equal to a query operation in the Fenwick tree for the range [1..i-1]. So we've solved the "simplified version" within O(NlogN) time.

How should we extend this solution to the original problem? We now create three Fenwick trees. For the first Fenwick tree T1, T1[i] == 1 indicates there exists a number i in the array; for the second tree T2, T2[i] indicates the number of ascending tuples ending with i; for the third tree T3, T3[i] indicates the number of ascending triplets ending with i. Now we can see there are connections between T1 and T2 and T3. The value of T2[i] equals to the sum of T1[1] to T1[i]. Similarly, the value of T3[i] equals to the sum of T2[1] to T2[i].

http://www.cnblogs.com/tonix/p/4518738.html
https://github.com/derekhh/HackerRank/blob/master/triplets.cpp
Read full article from Triplets | HackerRank