hanoi11minh_nh's blog

I need help solving problems about Binary Search
By hanoi11minh_nh, history, 7 hours ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Oh yeah! n<=5000 and each stick's length is <= 1e9. Also the space complexity limit is 256mb. Thanks anyway!

    → Reply
    • »
      »
      »
      7 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it cannot be possible in less than O(n^2) according to my knowledge.

      → Reply
      • »
        »
        »
        »
        7 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for helping anyway!

        → Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hanoi11minh_nh (previous revision, new revision, compare).

→ Reply
»
6 hours ago, # |
← Rev. 4   Vote: I like it +2 Vote: I do not like it

Problem source? Also $$$O(N^2)$$$ should pass since $$$N < 5000$$$

→ Reply