TLE in Sequence Land

general
, , ,
1

I was solving Sequence Land
My code : https://www.codechef.com/viewsolution/42883002
(Optimised one : https://www.codechef.com/viewsolution/42883374

Both my submissions give TLE on last test case. Can anyone please help me optimise it?

2

You can improve your check() function.

This is your code:

bool check(int u, int v){
    int c = 0;
    for (auto x : id[u]){
        for (auto y : id[v]){
            if (x == y)
                c++;
        }
    }
    if (c >= k)
        return true;
    return false;
}

This is O(n^2). It can be improved to O(n) if you use unordered_map:

for (int i = 1; i < n; ++i)
{
    for (int j = i+1; j <= n; ++j)
    {
        unordered_map <int, int> m;
        int cnt = 0;
        for (int e : a[i]) ++m[e];
        for (int e : a[j])
        {
            ++m[e];
            if (m[e] == 2) ++cnt;
        }
        if (cnt >= k)
        {
            adj[i].emplace_back(j);
            adj[j].emplace_back(i);
        }
    }
}
3

You have a nested for loop that takes O(n^2) time, and an additional O(n^2) for the check function. This is an overall complexity of O(n^4), which will give a TLE. You can optimize the check() function by using a set, map or an unordered map. Thus reducing it to O(n^3 log n) which will pass.
Check my solution : CodeChef: Practical coding for everyone