# TLE even when having the required time complexity

## Problem Info

USACO 2017 US Open Contest, Silver Problem 2. Bovine Genomics

## My Work

#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ofstream fout;
ifstream fin;
#define ll long long
#define pi (3.141592653589)
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

int main()
{
fast;
fin.open("cownomics.in");
fout.open("cownomics.out");

int n, m;
fin >> n >> m;

vector<string> p(n), s(n); //plain,spotted

//input
for (int i = 0; i < n; i++)
fin >> p[i];
for (int i = 0; i < n; i++)
fin >> s[i];

int ans = 0;

//iterate for every triplet
for (int i = 0; i < m; i++)
{
for (int j = i + 1; j < m; j++)
{
for (int k = j + 1; k < m; k++)
{
unordered_set<string> plain, spot;

//add the three genes as string to a set for every cow - plain and spotted
for (int l = 0; l < n; l++)
{

string pp = "";
pp += p[l][i];
pp += p[l][j];
pp += p[l][k];

string ss = "";
ss += s[l][i];
ss += s[l][j];
ss += s[l][k];

plain.insert(pp);
spot.insert(ss);
}

//if none of plain gene is in spotted then increment ans
bool flag = false;
for (auto &it : plain)
{
if (spot.find(it) != spot.end())
{
flag = true;
break;
}
}

if (!flag)
ans++;
}
}
}

fout << ans;

return 0;
}


This code as per my analysis is O(N*M^3) which is also the complexity of official solution on usaco,
I have used unordered_set to check if the plain cows and spotted cows have any gene triplet common.

This fails on the last test case, gives TLE

For the last case : N = 500 & M = 50

## What I’ve Tried

The only thing that is causing TLE in my code is the unordered_set.

## Question

What is causing the TLE here?
Can I not assume O(1) time complexity for set operations here ?

No, that’s only if the elements you are inserting have size O(1).

So, since I am inserting strings of length 3 in the unordered_set here, does that insertion operation takes 3*O(1) ?

My bad, I misread the solution. unordered_set is just slow (and 500\cdot 50^3 is not small).

2 Likes