Hello Codeforces!
I am facing this problem and don't know how to avoid TLE. Can someone please give me an algorithm hint for this problem? I already know the O(n^2) way.
Here is the problem:
We have n numbers which are the lengths of the sticks. Find the number of unique triangles that can be formed from the given n sticks. Unique triangles are understood as triangles that do not have a pair of 3 identical sides. Note that n<=5000 and each stick's length is <= 1e9
Thank you.
Note: I can solve it know, thanks.
Need to know more information about the problem. what is the maximum length of the sticks can be a valuable information and what is the expected time and space complexity?
Oh yeah! n<=5000 and each stick's length is <= 1e9. Also the space complexity limit is 256mb. Thanks anyway!
it cannot be possible in less than O(n^2) according to my knowledge.
Problem source? Also $$$O(N^2)$$$ should pass since $$$N \lt 5000$$$
That's also a valid point