Блог пользователя 2ndSequence

Getting TLE + brief explanation.
Автор 2ndSequence, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 6   Проголосовать: нравится +5 Проголосовать: не нравится

.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      .

      → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      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.

      → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 ?

    → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить