rachitiitr's blog

A Superb Problem on Hashing + Queries on Array [CodeChef]
By rachitiitr, history, 8 years ago, In English

http://rachitiitr.blogspot.in/2017/06/a-superb-problem-on-hashing-queries-on.html

This was my favorite problem from the recent long contest from CodeChef.
I solved the problem by building up a solution from scratch, and feel it's worth sharing.
Here is what other things you can learn from this post:
1. How to check whether two sets are identical using hashing.
2. An easy data structure to find the number of elements less than K in subarray A[L...R].
3. A variant of BIT i.e fenwick tree. We can use BITs for a lot of purposes :)

Have a good day!

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

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

Can we use binary search?

  1. Associate a random large value for each distinct element.
  2. Precompute prefix xor of these associated values going by order of the given array.
  3. compare xor of left and right halves of both the query segments. At most one of the two halves can differ.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But for binary search to work you need your left and right parts to be SORTED. Isn't it?

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

      That's where persistent segment tree comes in.

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

        Yes, that will work :) This is similar to what Himanshu Jaju commented on the blog link.

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

      You can use persistent segment tree to this. I couldn't see the idea of the xor, instead I used persistent segment tree to hash(multiplying) and binary search, in a brief description, inserting the elements in the tree from the smaller to large in value, will make possible have the hash of a ordered segment of the queries, you can find the first element that mismatch in the binary search, if exists, after you can use another binary search for find the second, to see if they are the same, is just multiply the element that mismatch in the first with the hash of the interval of the second and the element that mismatch in the second with the hash of the interval of the first. https://www.codechef.com/viewsolution/14056539

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

      You are right.

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

Hey why you are doing so much for computing mismatched value x,y ? compute prefix square sum and prefix sum ! if you subtract the prefix square sum of two ranges you will get =x^2 - y^2 if you subtract prefix sum you get = x-y now you you can easily find x and y !

AC Code

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

    Because I couldn't think of this during the contest time, and felt peaceful after implementing a difficult solution during which I learnt other things too.

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

    Why will it be only true for one mismatch?

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

What is the idea you used to find rank of the found values x and y in the corresponding subarray? I used sorting. It can lead to TLE but my code is giving WA even for small system tests. I have used prefix sum to find mismatch. It will be great if someone can help. I have wasted around 4 hours.

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

I am the author of this problem and I am glad that people liked this problem.

I am also surprised by all the different kinds of solutions that came in. Including sqrt, persistence, xor, etc since I myself knew only 1 — 2 different type of solutions.

Kudos to Rachit for figuring out the unique xor way for obtaining x and y.

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

→ Reply