TLE in SPOJ - FREQUENT using O((n+q)*sqrt(n)) approach

general
, , ,
1

Problem Link: http://www.spoj.com/problems/FREQUENT

The approach I am using to solve this problem is described here. This is an O((N+Q)\sqrt{N}) approach. But I am getting TLE.

In short, my approach was to use Mo’s Algorithm to sort the queries in the required order, but then I couldn’t figure out how to perform the following operations in optimal time:

  • add a single element
  • remove a single element
  • find answer of a range

All I could think was O(log(n)) for the above operations. But then I read Fcdkbear’s comment and tried to implement it the way he explained it. But, I still get TLE.

My code: https://ideone.com/E9kNVs

Can anyone explain how to do this or whether I am doing something wrong in my approach?

1 Like
2

Instead of declaring S to be vector <unordered_set <int> >, you can just declare it as vector <int>. The thing is, S[i] stores the elements that have frequency i. You don’t need to store the elements, you can just store the number of elements having frequency i. That will improve the complexity a bit.

This may work because the complexity of different operations on unordered_set is amortized O(1).

1 Like
3

Instead of calculating occurance of a number from i to j first calculate all the occcurance from -100000 to +100000 then print according to the query …u can even use square root decomposition

4

Yes, it worked. Thanks!

5

Can you elaborate a bit?