Page 1 of 2
11386 - Triples
Posted: Sat Jan 12, 2008 5:19 pm
Something hidden in the statement?
Posted: Sat Jan 12, 2008 5:45 pm
My algorithm is very simple and yet i'm getting WA all the time. Here it goes:
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
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
Posted: Sat Jan 12, 2008 6:06 pm
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.
Posted: Sat Jan 12, 2008 7:17 pm
Are you saying that my approach is right? When I have to use 64-bit integers: output (of course) AND input?? unsigned, signed?
Posted: Sat Jan 12, 2008 8:02 pm
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.
Posted: Sat Jan 12, 2008 8:25 pm
OK. Then, what's the output for the following input:
Posted: Sat Jan 12, 2008 8:28 pm
Your output is correct.
Posted: Sat Jan 12, 2008 9:02 pm
I did an O((n^2)log(n)) solution, and i didnt have problems with the Time Limit. gl! Eric.
Posted: Sat Jan 12, 2008 10:31 pm
Somebody got any tricky input?? This problem is definitely driving me crazy, it's not so hard even with a naive O(n^2) algorithm like mine!
[Edited] Finally, I got ACC. Besides grouping the numbers after sorting, I changed 'int' to 'unsigned int' and all worked OK!
Posted: Sun Jan 13, 2008 3:41 am
Posted: Sun Jan 13, 2008 1:45 pm
why im getting TLE ..............
Code: Select all
using namespace std;
unsigned int arr,n,m,count;
Posted: Sun Jan 13, 2008 1:57 pm
Use long long int. The grouping idea is:
Anyway, your code and algorithm is beautiful
O(n^3) is too slow. Try O(n^2logn) or O(n^2).
Posted: Sun Jan 13, 2008 6:22 pm
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?
Posted: Sun Jan 13, 2008 6:35 pm
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.
Posted: Sun Jan 13, 2008 10:52 pm
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).