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?

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?

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);
}
}
}
```

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 : Solution: 35559631 | CodeChef