I have some N co-ordinates (x1,y1), (x2,y2) and so on… The constraints are -10^6<x, y<10^6.
Now, I wish to find whether a point (a,b) was given to me or not, in constant time.
My initial approach was to use a 2d array as a plane, add 10^6 to the coordinates, and mark points on the plane, but that approach failed, because I cannot make an array of 2 million* 2 million size, so how do I go about the problem??
I am looking for a new approach, pls help me out.
1 Like
You cant do that. It’ll consume a whole lot of memory. More than 1500 MB. Change your approach. Think!
2 Likes
As promised, i’ll help you out now. I was facing the same situation as you! That big a multi dimensional array is impossible. Then i learnt a hash table. A hash table is useful when you have a lest number of points but the universe of those points is large. Which is exactly the case in this problem. The points can vary from -10^6 to 10^6 but there are only 2000 points. I exploited this nature of the problem.
Coming to the hash table, its similar to an array. The only difference here is you actually compute the index in which you are going to store your data using a hashfunction. I made an array of 2*10^6 which is the range of the points. And then stored the y coordinates in the array, by computing the hashfunction for the x coordinate. But as u myt think, one x-coordinate can have two y- coordinates associated with it. Example 2,4 and 2,3. So to avoid these type of collisions i made a linked list on each of the index. Searching and inserting in a hash table is a very very fast issue. Almost O(1) as it is almost like an array. Here is the link to my solution.
CodeChef: Practical coding for everyone I would be more than happy to help if you dont understand anything in my code or explanation 
Best of luck!
1 Like
How come I got a downvote?? only asked for the concept 
Yes, but the problem is I have ran out of ideas, i dont know the first thing about hash tables too, and I suspect thats the way to go, need help with the thinking part
There is a fairly simple way as well, if u can just think it. Try it or wait until the competition ends, i’ll tell u the way.
1 Like
okay, I’ll wait, thank you.
great!! I also learnt the hash table yesterday and implemented it in C++, with the help of make_pair for two keys(one x and one y) but I still got TLE, can you tell me why?? CodeChef: Practical coding for everyone
@shiva1k95_10 man, u dont need to check for j from j=0 to j=n. You are wasting time this way. U just check it from j=i+1 to j=n. Saves quite a lot of time. Try this! And tell me if it still gives u a tle. For now i believe thts the reason!
@pranjalranjan I was using the wrong function in map.h, i shouldve used find, i got CA now, thanks, the syntax cost me one problem in long challenge, well it was my first challenge, so i guess foiur isnt bad 
Oh well, even i dont know much about maps 
So cudn’t figure out! And yea, u did excellent. I started with 2. This time i did 7. So really not bad to start with
1 Like