pavitra.eee's blog

By pavitra.eee, history, 4 weeks ago, In English,

Problem

MY CODE

At each node of the segment tree I am storing a hashmap to facilitate frequency count of each element in that interval. I am getting TLE and need some help from the community.

 
 
 
 

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe try reserving the size of HashMap to prevent rehashing? This will make your program quite a bit faster.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that the problem is your update query, because every time you go up in the segment tree you merge the left and right child with complexity O(n). Thus your complexity per update is something like O(n*log(n)) which gives you time limit.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah oorviziel is right, instead of "merging them" think of it as a path going down, and you do mp[thing]++ for every node in the path.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And now I'm looking at his code again. He does the same thing in his query function. So again the complexity for both update and query function is O(n*log(n)).

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please explain your solution in a bit detail , I am starting to learn Segment trees and need some help.:(

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

without merging 2 child map in parent map at every node,you can assign the larger map in parent(coming from left/right child) then merge the other map with the parent node

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You have to code it faster.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me it's been 9 days since I posted this?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Interesting problem. Will try it later, maybe tomorrow. Hopefully, I would be able to help you.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let's try to define the structure of each node in the segment tree. Consider the node responsible for the segment from L to R. We can keep two data structures for the elements in this segment:
    1. A map map1 of frequencies called freq, where freq[x] stores the no. of times x is present in the segment. The key in this map is the element x.
    2. A map map2 of elements with a specified frequency. The key in this map is the frequency freq[x] of element x, and the corresponding value is a set of all elements x with this frequency.

    All queries of type 1 will update both these maps efficiently.

    How will we find the dominator in a single node in the segment tree? We simply look at the largest key in map2, and if this key is at least (R-L+2)/2, we say that this segment has a dominator. Therefore, we figured how to find whether or not a dominator is present in a single node.

    The situation is complicated for type 2 queries, because while querying the segment tree for arbitrary segments, multiple nodes are reached, and checking only the largest key isn't enough, as the elements corresponding to largest frequency will change from node to node. Notice that each query in a segment tree executes the terminating condition at most log(n) times. Therefore, we only need to check log(n) largest keys in map2. As there are log(n) nodes, and log(n) keys are checked per node, we run the queries in log^2(n), which should be sufficiently good.

    Notice that as the keys of map2 denote distinct frequencies, it's size can be at most sqrt(length of segment). Why? Because, the smallest distinct sizes having only 1 element each are 1,2,3,....,sqrt(R-L+1) such that their sum is R-L+1.

    As there are log(n) nodes, the total complexity is Q * log(n) sqrt(n)

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Notice that map2 actually gives the value of the dominator itself. Since the problem only asks for Yes/No answers, we can just keep a count of elements with that particular frequency(the key in map2) as value in map2 instead of a set as value.