Riyad_Hossain's blog

Unexpected TLE in O(NlogN) Algorithm with N = 2e5
By Riyad_Hossain, history, 6 months ago, In English

Hello coders,

I've recently encountered a perplexing issue while working on a problem where the input size (N) is up to 200,000. Despite my algorithm's O( n log n ) complexity, it consistently hits a Time Limit Exceeded (TLE) error on the 8th test case. I've optimized my code to the best of my ability and ensured it's running in O(NlogN) time complexity, but the problem persists. Can anyone help me to debug this problem?

Problem: 1955D - Inaccurate Subsequence Search

Submission: 267829049

Additional: I managed to solve this problem by replacing the multiset. Here is my second submission: 267810516. But I'm very much curious about why the n log n solution didn't work. Did I miscalculate the time complexity or miss something crucial?

Main Code of first submission: Iterate over n and log n for counting element in multiset

    int cnt = 0;
    map<int, int> mpp;
    for (int i = 0; i < m; i++)
    {
        mpp[a[i]]++;
        if (ms.count(a[i]) >= mpp[a[i]])
            cnt++;
    }
 
    int ans = cnt >= k;
    for (int i = 0; i < n - m; i++)
    {
        mpp[a[i]]--;
        if (ms.count(a[i]) > mpp[a[i]])
            cnt--;
 
        mpp[a[i + m]]++;
        if (ms.count(a[i + m]) >= mpp[a[i + m]])
            cnt++;
        ans += cnt >= k;
    }
 
    print(ans);
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

multiset::count is linear in the number of matches link

→ Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

multiset.count(x) is not log(N), this is O(logN + freq of x)

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, then we can sort an array in $$$O(N)$$$, congratulations!

    Spoiler
    → Reply
»
6 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

If you want a multiset count that works in O(logn) you can check out ordered_set. From cppreference: https://en.cppreference.com/w/cpp/container/multiset/count, note that the complexity is "Logarithmic in the size of the container plus linear in the number of elements found". https://codeforces.net/blog/entry/111217 mentioned this as "Mistake 22".

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Using std::map<T, size_t> is also a way to solve the problem easily in O(log n).

    For example:

    • Insert an element x to a: a[x] += 1.
    • Erase an element x in a: a[x] -= 1.
    • Count the number of x in a: a[x].
    → Reply