Alwoosh's blog

A new approach to solve online MO problems
By Alwoosh, history, 26 hours ago, In English

In the last Educational Round, I implemented next solution for G problem(2043-G - Problem with Queries), and never seen before, solution like this, for online MO problems.

298356157

In the problems, we have to find number of pairs of unequal values in the some range. Also, we have updates, and queries — online.

Firstly, I change our task to find pairs of equal values, and imediatelly think about MO(offline solution of problem). Instead of one supported MO segment, I decided to support 500 MO segments. In the updates, I just update MO segments that have that value inside of segment. And for the second type of queries, firstly I find MO segment that needed less iterations to reach the range from the query.

Update: the solution has been hacked, and I have added a new way to optimize code, if we have a MO segment that needed less than 3000 iterations to reach the range from the query, then we can just pick that MO segment. In another case, if we have less than 500 created MO segments, we create a new segment. If we have create 500 MO segments already and no one don't reached by 3000 iterations, just pick a segment with less iterations(like in the first solution).

298386140

I am curious whether it should pass the tests and about its complexity. Also, have you seen this technique before? Personally, I did not encounter any blogs about this.

  • Vote: I like it
  • +64
  • Vote: I do not like it

»
25 hours ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by Alwoosh (previous revision, new revision, compare).

→ Reply
»
25 hours ago, # |
  Vote: I like it +13 Vote: I do not like it

50 отрезков почти за такое же время работают

→ Reply
»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Alwoosh (previous revision, new revision, compare).

→ Reply
»
21 hour(s) ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Cool technique! Looks like its complexity is amortized $$$O\left(\dfrac{n}{\sqrt{k}}\right)$$$ per query and $$$O(k)$$$ per update, where $$$n$$$ is the length of initial array and $$$k$$$ is the number of so-called "MO segments".

→ Reply
  • »
    »
    21 hour(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Your solution is very similar to this: split initial array into $$$O\left(\sqrt{k}\right)$$$ blocks and calculate "MO segment" between each pair of blocks. Then for each query use appropriate "MO segment" to answer it in guaranteed $$$O\left(\dfrac{n}{\sqrt{k}}\right)$$$ and then return this "MO segment" back to initial state. Even though it works in guaranteed time, it is probably slower in practice then your amortized solution.

    → Reply
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hacked

→ Reply