TLE even when having the required time complexity

Debugging Help
#1

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

image
image1102×120 8.95 KB

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 ?

#2

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

#3

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

#4

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

2 Likes