A Superb Problem on Hashing + Queries on Array [CodeChef]

Revision en1, by rachitiitr, 2017-06-14 11:53:05

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rachitiitr 2017-06-14 11:53:05 643 Initial revision (published)