### rachitiitr's blog

By rachitiitr, history, 7 years ago,

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!

• +86

| Write comment?
 » 7 years ago, # |   0 Can we use binary search? Associate a random large value for each distinct element. Precompute prefix xor of these associated values going by order of the given array. compare xor of left and right halves of both the query segments. At most one of the two halves can differ.
•  » » 7 years ago, # ^ |   0 But for binary search to work you need your left and right parts to be SORTED. Isn't it?
•  » » » 7 years ago, # ^ |   0 That's where persistent segment tree comes in.
•  » » » » 7 years ago, # ^ |   0 Yes, that will work :) This is similar to what Himanshu Jaju commented on the blog link.
•  » » » 7 years ago, # ^ |   0 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
•  » » » 7 years ago, # ^ |   0 You are right.
 » 7 years ago, # |   +15 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
•  » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   0 Why will it be only true for one mismatch?
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   0 I used BIT where bit[i] is an ordered multiset.
 » 7 years ago, # |   +28 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.
•  » » 7 years ago, # ^ |   0 Thanks sidhant. Not sure about the downvotes. :|
 » 7 years ago, # |   +3