vamaddur's blog

Comparing Permutations of Subarrays Problem
By vamaddur, history, 7 years ago, In English

We are given an array of size N and Q queries (1 <= N, Q <= 100000). Each query has 4 parameters: index i, index j, length L, and differences D (0 <= D <= 1). We must answer "YES" if a permutation of the subarray from arr[i] to arr[i+L-1] differs from a permutation of the subarray from arr[j] to arr[j+L-1] in at most D places, and "NO" otherwise.

This sounds like an offline segment tree problem, but I am not sure how to start implementing it.

Can someone give me some hints to get me started and moving in the right direction?

Please help, and thanks in advance!

UPD: Just for the sake of it, I tried submitting a naive N^2 solution, which didn't make it in the time limit of 2 seconds, as expected.

UPD2: Original problem statement is here.

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

Comments Comments (15)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Can you give me link to problem statement? This statement is unclear

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

I didn't understand the permutation part clearly, but you can do the queries for any array (No need to be permutation) in O(D * lg(n)) by hash.

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

    Can you further describe this approach?

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

      First you will hash the whole array : hash[i] = hash[i - 1] * BASE + a[i] .

      Now you can calculate the hash for each subarray in O(1) and two subarrays are different if and only if their hashes are different numbers.

      Also you can find LCP (Longest Common Prefix) of two subarrays in O(lg(n)) by using binary search.

      Now you can solve the problem by finding LCP, D + 1 times : 

      cin>>l1>>r1>>l2>>r2;
while(d+1)
    x=LCP(l1,l2);
    l1+=x+1;
    l2+=x+1;
    d--;
return (l1>=r1+2 && l2>=r2+2);

      Tell if I made a mistake or completely misunderstood the problem :)

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

        @Batman That solves the problem for D = 0, but I am kind of unclear on how to compute the hash in constant time.

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

          That code I sent works for D>0 too.

          The hash for subarray [l,r] would be this : hash[r] - hash[l - 1] * BASE(r - l + 1) .

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

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

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

How to compare two multisets A = {a1, ..., ak} and B = {b1, ..., bk}? Take a random function f. If , most probably A and B are the same multisets. Otherwise they are different.

How to check if A and B differs only by one element? Suppose that and . We can get y - x by comparing sums. We can also get y2 - x2 by comparing square sums. Now we know x and y, and we can compare and .

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

    What kind of function are we talking about here? I assume a polynomial with at least degree 2 and prime coefficients?

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

      In the first part, he is talking about functions in a general way. A constant function or any other that would not allow us to distinguish two numbers would not work, so we are looking for a bijection or a "almost" bijection.

      On the second part of the answer he specifies two functions f(x) = x and f(x) = x*x. These functions let you find x and y. Of course you can use other functions if they allow you to solve the equations for x and y.

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

        How can we prove what rng_58 has proposed ?

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

          In general, you can't. He is using hash functions to compare sets. So there's always a probability that his method fails.

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

quite similar to this problem:https://www.codechef.com/JUNE17/problems/CLONEME

You can take a look of the AC codes. Hope it helps.

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

A O(n sqrt(n)) solution.

(No hash)

Step 1:divide the elements into sqrt(n) intervals.

Step 2:divide the queries into O(n) parts according to the intervals the leftmost&rightmost elements are in

Step 3:deal with the queries like this:

vector<pair<int,int> > query[SQRT_N][SQRT_N];
//......
int l=0,r=0; //[l,r)
for(int i=0;i<sqrt(n);i++)for(int j=0;j<sqrt(n);j++)for(int k=0;k<query[i][j].size();k++){
    int cl=query[i][j][k].first,cr=query[i][j][k].second;
    while(l<cl)DEL_ELEMENT(l),l++;
    while(r<cr)ADD_ELEMENT(r),r++;
    while(l>cl)l--,ADD_ELEMENT(l);
    while(r>cr)r--,DEL_ELEMENT(r);
//......

Now,we just need to ADD_ELEMENT/DEL_ELEMENT in O(1) time

Declare an array diff[MAX_ARR],which shows the difference of the times each numbers appears between arr[l,l+L) and arr[r,r+L) (possible negetive),and a variable DIFF which equals to the sum of all of the ABS(arr[k])),and it can also mean the minimum elements that 'a permutation of the subarray from arr[i] to arr[i+L-1] differs from a permutation of the subarray from arr[j] to arr[j+L-1]'

When adding/removing elements,we just change two of them,so the change of arr[] and DIFF can all be O(1) (I'm sorry I don't have a complete code)

Sorry for my poor English :)

UPD: I've found the English name of this algorithm: Mo's algorithm

→ Reply