2ndSequence's blog

Getting TLE + brief explanation.
By 2ndSequence, history, 4 years ago, In English

Hello..

I was solving this problem And i am getting TLE on test 29 but not sure why?

i believe the only reason is using map< pair<int, int>, int> but still the complexity should be log n for insertion and finding the item or am i wrong?..

The code is simple just look for the middle point and add the count of it to answer but not sure if that's the reason.

If anyone can confirm the complexity of using map< pair<int, int>, int> would be nice.

Thanks in advance.

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
← Rev. 6   Vote: I like it +5 Vote: I do not like it

.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Yes thank you so much for that!!..

    But do you think that you know what's wrong with using map? complexity should pass i think?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      .

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Please do not use unordered_map except if you know what you are doing. Unordered_map is a very dangerous data structure. The reason that is because it stores its contents by hashing. Hashing is a method to convert large values into small ones. But in the process, sometimes two large values when they change into small values, they can have the same small values. In that case, if you are searching for that value, it will take $$$O(2)$$$ this time not only $$$O(1)$$$. Now, if you are in a recent contests(mostly educational rounds and Div 3/4), there is hacking. People can easily hack you by making all numbers collide with each other causing an explosion of $$$O(n)$$$ search time. Refer to this blog by neal where he explains how to secure your unordered_map. Also, you don't need map or unordered_map to solve that problem. Think how you can use frequency arrays. If there is a negative value, you can shift it so it can become $$$>=0$$$. Frequency arrays will be the fastest between unordered_map and map as it uses stack memory instead of heap.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Using a map here is not efficient, better use a 2D array. And there is no need to count the points, since "It is guaranteed that all given points are different.".

Instead move all index values to positive range by adding 1000 to x and y, so the values are within range 0,2000. Then you can use a vector<vector<bool>> vis(2001, vector<bool>(2001)); to store the info if an point exists or not.

Edit: Note also that the time consumption is not about searching the map, it is because you implicitly insert a huge amout of points into the map while searching for the middle points. It can be up to aprox 4e6 middle points checks, and each one creates an entry in the map.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you, I actually didn't notice the It is guaranteed that all given points are different. somehow..

    And yes i totally agree with you and i used a 2D array to get AC, But still i want to know the reason behind TLE because it should be n^2 log n.

    Suppose if the problem was with constraints -1e18 <= x <= 1e18 ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      See the edit note, you can use map.find instead of the [{x,y}] notation to not create a new entry on every search.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Look at this code ----- >

vector<pair<int, int> > a;
        for(int i=0; i<n; i++){
            cin >> x >> y;
            a.pb({x,y});
        }
        sort(all(a));
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                int x2,y2;
                x2 = (a[i].first + a[j].first)/2;
                y2 = (a[i].second + a[j].second)/2;
                if(a[i].first + a[j].first != 2*x2) continue;
                if(a[i].second + a[j].second != 2*y2) continue;
                if(binary_search(all(a),make_pair(x2,y2))) ans++;
            }
        }

Tips : 1.I think there is no need of map 2.As all points are distinct and we fix two points the third point gets fixed so we use binary_search() to search the third point

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, I guess you are correct, but binary search takes O(logn), but if we add the points to a map and the check if they exist it takes O(1). That is why I am trying to used map or did I miss something?

    Thanks!

    → Reply