speedster's blog

offline solution
By speedster, history, 9 years ago, In English

How to solve this: given multiple query of type : x l r , we need to find the frequency of x in the range r to l. There are no updation so basically calls out for an offline algorithm .

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

Comments Comments (7)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think it can be solved by Mo algorithm

Sort queries by this comp: 

bool comp(Query x, Query y) {
    if (x.l!=y.l) return x.l < y.l;

    return x.r < y.r; 
}

Let freq[i] be the frequency of number i, you can now solve the problem by shifting the previous L,R query to the curL, curR and then answer the query.

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

    What your comparing function does is not what Mo's algorithm is supposed to. You can't simply sort the queries as pairs and expect this to work fast. The correct function goes here:

    bool comp(Query x, Query y) {
    if (x.l/(int)(sqrt(n))!=y.l/(int)(sqrt(n))) return x.l < y.l;

    return x.r < y.r; 
}

    For example, if N=9 and there are queries (1,9), (2,4) and (3,6), then they should be in order (2,4), (3,6), (1,9) or (1,9), (3,6), (2,4) but your function will sort them like (1,9), (2,4), (3,6).

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

      Oh you're right, that was my mistake, thanks.

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

      I know this is probably just an example code but I want to point out that sqrt(n) would return a double, and most probably x.l / sqrt(n) will be converted to a double itself, so the "!=" comparison may not produce correct results.

      Use (int)sqrt(n) instead :)

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

        Oh, that was a stupid mistake. I usually use int sq=sqrt(n); and then use sq in comparisons just because of that casting but this time I somehow forgot the (int), thanks for the correction! :)

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

for each number in the input array, store the indices where it's present in a vector. for each query x l r, the answer will be upper_bound(r) — lower_bound(l).

what is an offline algorithm?

try this problem: https://www.hackerrank.com/contests/codeagon/challenges/sherlock-and-subarray-queries

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

sorting query with square-root decomposition gives O( n ^ 1.5 )

There is online solution with O ( n lg ^ 2 n )

first, store each step of merge sort such as

3 1 4 1 5 9 2 6

( 1 3 ) ( 1 4 ) ( 5 9 ) ( 2 6 )

( 1 1 3 4 ) ( 2 5 6 9 )

 ( 1 1 2 3 4 5 6 9 )

then, [l, r] can be decomposed to O (log n) intervals with 2^k sizes. for example, [3, 6] (0-based, inclusive) can be decomposed to [3,3], [4, 5], [6, 6] you can add up all upper_bound(x) — lower_bound(x) for each interval and that is answer.

→ Reply