Блог пользователя rajat1603

SPOJ FREQUENT — Frequent values using MO's Algorithm
Автор rajat1603, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится

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

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

This blog entry is exactly what you need.

→ Ответить