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

Автор faiyaz26, история, 8 лет назад, По-английски

Is it possible to have update query on mo's algorithm ?

In exact I want to know that whether it is possible to solve this problem by using mo's algorithm ?

I am the setter of the problem, but I have used 2d Interval tree to solve the problem. The code is big and quite messy.

Looking for simpler solution. Can anyone help with some clear explanation ?

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

»
8 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Why this is not normal segment tree ? Only in first step in parts where numbers is not divisible by 3 you should put 0 instead of that value.

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

Since Mo's method shuffles the query for speedup, it's intuitively impossible to to solve problems with update. (maybe some fancy method can deal it, but idk)

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

Mo's algorithm is able to solve problems with update too.

Set sizes of blocks to n2 / 3.

So queries [li, ri] can be grouped into at most blocks.

For each block, deal with query operations which belong to this block and all update operations.

Total complexity is O(n5 / 3).

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

    Can you please explain this in some more detail? If there are some 1e5 operations (including queries and updates), and for each of them, l=1 and r=n? (So all queries belong to same block) I did not understand what you meant by "deal with query operations which belong to this block". The final complexity you mentioned is based on handling each block in O(n) time (please correct me if I'm wrong). How do we do that?

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

    how is no. of blocks equal to n^2/3 when size of each block is n^2/3. Also how do you update. Can you please elaborate your explanation. It is not that helpful for beginners.

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

      We group queries based on both endpoints Li and Ri.

      Both Li and Ri can belong to one of n1 / 3 blocks.

      So queries can belong to one of (n1 / 3)2 = n2 / 3 blocks.

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

        And then how do you perform the query? I have got l and r and I want to update all elements between l and r on which update operation was made and count no. of distinct multiples of 3 between l and r. How to do that? Mo's just sorts queries based on blocks in which l is there, but you want to sort queries based on which block both l and r are situated?

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

          You don't need sort queries.

          You may just deal with queries that both L and R belong to same block respectively together.

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

            Ok, I don't sort it. But still how to do update and find answer. If my L and R both belong to same block (which is of size n^2/3) then and if they do not belong to same block then what to do? Also how is this similar to Mo's algorithm?

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

              I mean let's deal with queries Li, Ri that all Li belong to block x and all Ri belong to block y together(Not x=y).

              Then it's almost same with Mo's algorithm with no updates.

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

                Ok. So you are processing all queries together such that L is in block x and R is in block y. Now how do you find the answer for some L to R, given that you also have update queries to be performed? And what benefit are we gaining by processing all queries which belong to same block together?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 лет назад, # ^ |
                  Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

                  Imagine the naive approach. To process a query [l..r] you'd add all the values V[l..r] in a set and count its size. Now, in order to optimize that, we have grouped queries that are close together, such that when going from a query to a closer one we have fewer insertions / deletions in the set.

                  It's similar to Mo's Algorithm in the sense that you solve the queries such as to minimize the distance between two adjacent ones (measured in terms of insertions/deletions). It's different from Mo's because it does not need the queries to be solved in some order. Only in more (N2 / 3, to be exact) passes of the queries.

                  It's kind of fascinating, to be fair.

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

    Could you please elaborate further on your idea? All your comments seem to be very short and I find it hard to understand it. Perhaps if you could provide a practical example such as a problem you have solved using this method and the code, then we would be able to understand the solution much better. What do you do after you create these blocks? How do you support the update queries when they have to be processed chronologically?

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

      What I have understood from above comments (I myself have not used it, so correct me if I am wrong somewhere): I think it is a modified form of Sqrt Decomposition:

      1. Break the array into blocks of size n2 / 3, so you have n1 / 3 blocks.

      2. Consider a subarray starting at the start of block x and ending at the end of block y. We can precompute such answer for all subarrays such that 0 <= x <= y < n1 / 3. So if we can compute answer for a subarray in linear time, this will take O(n * n2 / 3) -> O(n5 / 3) time.

      3. For each update occuring at pos, update the precomputed answer for all subarray's in which pos lies. If we can update in O(1) time for a subarray, this will take O(n2 / 3) time per update.

      4. For query L,R: find the largest precomputed subarray which lies completely inside L,R, and update answer for all remaining elements, which will be O(n2 / 3) in worst case.

      All operations have become similar to Mo's algorithm's "add" and "delete" operations. We have O(n5 / 3) precomputation, and O(n2 / 3) per query and update, provided we can update answer for changing one element in a subarray in O(1) time.

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

        In the 4th step, how exactly do you compute the query in O(n^2/3). I don't get that step. I mean,how do you calculate distinct element query in that time?

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +28 Проголосовать: не нравится

      A problem: Candy Park

      And accepted submissions here.

      Brief description:

      You're given a tree with n nodes.

      There is candies on each node. Node i supplies candies of kind c_i only.

      We know the value of the ith kind candy is v_i.

      If a visitor tastes the same kind candy for the ith time, the weight is w_i.

      And his happiness will be sum of w_i*v_j over all candies he tasted.

      Queries are: given x and y, answer happiness of a visitor if he walks from node x to node y. He will taste candies on each node he passes exactly once.

      Updates are: given x, change c_x to y.

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

I'm still baffled as to why they had to throw the extra "divisible by 3" restriction to the problem...

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

Hi Everyone!
I made a video editorial on Mo's algorithm with updates. Here is the link:

https://youtu.be/gUpfwVRXhNY

It talks about how we can sort the queries offline with an example and time complexity analysis.
Feel free to ping me in (the very likely) case that you have doubts or suggestions.

Cheers!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my favourite algorithm.