rajat1603's blog

SPOJ FREQUENT — Frequent values using MO's Algorithm
By rajat1603, 9 years ago, In English

http://www.spoj.com/problems/FREQUENT/ . I solved this question using segment tree but i was wondering if it can be solved with MO's algorithm . Does anyone have an idea of how to apply MO's algorithm on this and keep track of the most frequent value along with it . Thanks in Advance.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It can be solved using Mo's alorithm. We need a structure that can handle the following operations:

1) Insert a number

2) Delete a number

3) Get the most frequent number

It turns out that std::set does the job. In our set we will store a structure (Number, Occurrences). Of course, our set will sort the elements by Occurrences and the answer is the first/last element in the set. When we need to insert/delete a number we just find it and erase it from the set, then increase/decrease its number of occurrences and then insert back into the set.

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

    cant it be solved without using a set or anything that consumes O(log(n) ) ?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I am not sure about this... Maybe somebody smarter than me can help you, sorry :(

      The bad thing here is that if you don't know how to eliminate the O(log N) you can't prove that it is impossible...

      BTW, the problem is about finding the maximum number in a set online and I think that there is no better algorithm than O(log N) per query using priority queue or set.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Instead of std::set, store them in continious arrays, each of size (BLOCK). Every (BLOCK) queries, reconstruct all the arrays.

      To answer "find" query, just see last element in last array. \ To answer "insert" query, find array, find position in the array, then insert it in O(number_of_elements_in_array). \ Delete -- same as insert.

      With help of reconstructions, number_of_elements_in_array <= 2 * BLOCK. BLOCK = sqrt(N).

      Complexity: O(N*sqrtN)

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

        I don't understand why is it O(N * sqrtN). Isn't it O(N * sqrtN * sqrtN) which is O(N^2)?

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

          Overall reconstructions: O(M / sqrtN + sqrtN) = O(sqrtN) -- reconstruct: O(n) Overall insertions\deletions: M -- insert\delete: O(sqrtN + sqrtN) (first — to find array, second — to find position) Overall find: M -- find: same as insert\delete.

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

          I keep (occurrences, number) pairs sorted, if that's what confused you. But that involves using associative array :((, and adds M*logN, which, though, does not affect N*sqrtN complexity. P.S. Sorry for log.

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

      http://ideone.com/b7rbPr Here is my sqrt(n) * n code .

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    I m getting tle with MO's algorithm using set ..

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This blog entry is exactly what you need.

→ Reply