Code: Select all

```
cut
```

**Moderator:** Board moderators

Code: Select all

```
cut
```

Last edited by DP on Sat Jan 12, 2008 7:19 pm, edited 1 time in total.

My algorithm is very simple and yet i'm getting WA all the time. Here it goes:

Any hints?

Code: Select all

```
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
```

Last edited by mpi on Sat Jan 12, 2008 7:14 pm, edited 1 time in total.

So does the obvious O(n^2) solution work? And how big can the input integers be? Just less than 2^31?

[EDIT] Accepted. Let me answer my questions: O(n^2) works. Have to use 64-bit ints in the code.

[EDIT] Accepted. Let me answer my questions: O(n^2) works. Have to use 64-bit ints in the code.

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.

Code: Select all

```
7
3 3 3 5 5 8 8
```

Code: Select all

```
12
```

Code: Select all

```
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int i,j,k;
unsigned int arr[5000],n,m,count;
while(cin>>n){
for(i=0;i<n;i++) cin>>arr[i];
sort(arr,arr+n);
count=0;
for(i=0;i<n-2;i++){
for(j=i+1;j<n-1;j++){
m=arr[i]+arr[j];
for(k=j+1;k<n;k++){
if(arr[k]>=m){
if(arr[k]>m) break;
count++;
}
}
}
}
cout<<count<<endl;
}
return 0;
}
```

Use long long int. The grouping idea is:

Code: Select all

```
1 1 1 2 3 3 --> (1,3) (2,1) (3,2)
```

>>Ron

O(n^3) is too slow. Try O(n^2logn) or O(n^2).

-----

Rio

If you have grouped the numbers, then the O(n^2) is very obvious.

Hint: suppose we are to find tuples (X, y, z), where X is fixed. Think of how to do so in O(n).

There are many other ways to get O(n^2) solutions for this task.

Hint: suppose we are to find tuples (X, y, z), where X is fixed. Think of how to do so in O(n).

There are many other ways to get O(n^2) solutions for this task.

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).