clex's blog

I need help solving problems about Binary Search
By clex, history, 2 weeks 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.

Note: I can solve it know, thanks.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
2 weeks 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
  • »
    »
    2 weeks 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
    • »
      »
      »
      2 weeks 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
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for helping anyway!

        → Reply
»
2 weeks 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
»
2 weeks 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
»
2 weeks 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
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")//Comment optimisations for interactive problems (use endl)
#pragma GCC optimization ("unroll-loops")


#define SPED                          \
        ios_base::sync_with_stdio(false); \
        cin.tie(0);                       \
        cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long

const lint INF = 1e15;

using namespace std;

struct Data
{
    lint maxi, fi, se;
};

int n, ans;
lint a[100005];
Data seg[400005];

Data combine(Data x, Data y)
{
    lint tempa[] = { x.fi,x.se,y.fi,y.se };
    sort(tempa, tempa + 4);
    return { max(x.maxi,y.maxi),tempa[0],tempa[1] };
}

void build(int node, int l, int r)
{
    if (l == r)
    {
        seg[node] = { a[l],a[l],INF };
        return;
    }
    int mid = l + r >> 1;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    seg[node] = combine(seg[node << 1], seg[node << 1 | 1]);
}

Data get(int node, int l, int r, int templ, int tempr)
{
    if (templ <= l and r <= tempr)
        return seg[node];
    if (r < templ or tempr < l)
        return { -INF, INF,INF };
    int mid = l + r >> 1;
    return combine(get(node << 1, l, mid, templ, tempr), get(node << 1 | 1, mid + 1, r, templ, tempr));
}

lint binaryu(int now)
{
    int l = now + 2, r = n, mid, ans = -1;
    while (l <= r)
    {
        mid = l + r >> 1;
        auto temp = get(1, 1, n, now, mid);
        if (temp.fi + temp.se > temp.maxi)
        {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return ans;
}

int main()
{
    SPED;
    cin >> n;
    for (int i = 1;i <= n;i++)
        cin >> a[i];
    build(1, 1, n);
    int l = 1;
    for (int r = 3;r <= n;r++)
    {
        auto temp = get(1, 1, n, l, r);
        while (temp.maxi >= temp.fi + temp.se and l <= r - 2)
        {
            ++l;
            temp = get(1, 1, n, l, r);
        }
        if (temp.maxi < temp.fi + temp.se)
            ans = max(ans, r - l + 1);
    }
    cout << ans;
}
→ Reply