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

Автор vamaddur, история, 5 месяцев назад, По-английски,

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.

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

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

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

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

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

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

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.

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

    Can you further describe this approach?

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

      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 :)

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

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

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

          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) .

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

I give you a code very different from your approach. The problem with your code is that you are using the original string in order to add periods and remove Do My Essay vowels and so produce the output string. What you have to do is produce an output string having no vowels defined according to your assignment and having a period prior to each consonant. In case you find a consonant you have to append + consonant to your output string else omit output.

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

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

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

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 .

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

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

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

      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.

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

        How can we prove what rng_58 has proposed ?

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

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

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

      One simple approach that would hopefully work is Zobrist hashing.

      • Assign each element x a random (64-bit) number zob[x].
      • The hash of a range a[i..j] is zob[a[i]]^zob[a[i+1]]..^zob[a[j]].
      • Use a segment tree over the xorsum of the zobrist values, to calculate the hash of an arbitrary range in logarithmic time.

      Edit: Actually, you don't even need a segment tree, a prefix array should be enough (thanks to the properties of the xor operator, i.e. hash(a[i..j]) = hash(a[0..j]) ^ hash(a[0..i-1])).

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

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

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

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

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

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

Stages happen, in pretty much unmistakable courses, in practically every territory of arithmetic. They regularly emerge when diverse orderings on certain limited sets are considered, conceivably simply because one needs to disregard such orderings and has to know what number of designs are consequently recognized. Batman Leather Jacket

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

Yeah Amm..!! According To Me You Should Just Go And F**k Yourself You B**ch...!!

Arrow Bomber Black Outfit S2 Oliver

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

my teacher gives me the same assignment work which i haven't done on time then i realize that there are many assignment writer online who can help me then i found reliable writing service — Assignment Ninja help with assignment.

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

I am making the assignment on the same topic and this post is really useful for me. I am trying to make my assignment by myself but if I could not make it. I will take the university essay help UK for this assignment.

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

Take the primary detail. You've were given your first subarray. Do you've got a second detail? Add that one too, there you have got a 2d one. If there may be a third upload that one, and so on. We do that till we've got the very last subarray it is technically the whole array of length n. But now we go returned two positions, and skip the n-1 detail and you do add the nth detail... You get a new subarray. Write My Essay For Me

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

Thank you for uploading this because I had been doing research on comparing permutations and I was unable to find a good information regarding this. Academic Writing