TLE in CHEFSQUA

general
,
1

I used the same approach for CHEFSQUA, as in the editorial, but I also used the #include for creating a hash table(for checking points in O(1) ) in C++ and used make_pair(long int, long int) for the co-ordinate key (x and y), everything gets wrapped up in O(N^2) but still I’m getting TLE

http://www.codechef.com/viewsolution/5136938

Help would be greatly appreciated…

2

use count/find function instead of [] operator…[] operator keeps on adding the elements into the map.

1 Like
3

First of all map is not a hash table. It is in fact an RB tree.
Therefore query time is rarely O(1) , it is O(log n).

Now for checking whether a value exists or not , you should not use the [] operator. The [] operator creates a new empty element every time it is used , as pointed out by rahul_nexus , therefore blowing up your complexity.

I suggest you read about ‘sets’ in c++ as their main motive is to answer queries that whether an element is present in the set or not ( which is specifically what you need , I suppose ).

If you want to use map , you should use the find function.

       if(mymap.find(x)!=mymap.end())
        {
          //the key x has been found
        }
2 Likes
4

hey can you explain its use, actually I learned hash tables yesterday only, thank you btw :slight_smile:

5

Wow thank you, never even heard of sets, will check them out

1 Like
6

Would like to add to the difference between insert and [] for inserting in the map, operator[] requires the default constructor because it needs to check whether the value for a particular key exists or not. If not, then the constructor maps the key with a default value. However, if my class doesnot have a default constructor, forcefully we have to use insert.

1 Like