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!
Can we use binary search?
But for binary search to work you need your left and right parts to be SORTED. Isn't it?
That's where persistent segment tree comes in.
Yes, that will work :) This is similar to what Himanshu Jaju commented on the blog link.
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
You are right.
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^2if you subtract prefix sum you get =x-ynow you you can easily find x and y !AC Code
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.
Why will it be only true for one mismatch?
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.
I used BIT where bit[i] is an ordered multiset.
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.
Thanks sidhant. Not sure about the downvotes. :|