Problem with HashMaps, Time Complexity, O(N) fails while O(N^2) works!?

help
, , , , ,
1

I am always sceptical while using hashmaps in c++, because they have an amortized time complexity of O(1).
Nonetheless, here is a problem that should easily be solved using HashMaps in O(N) time complexity. We won’t even have collisions in this case.

Problem: PTMSSNG (PTMSSNG Problem - CodeChef)
My Solution: https://www.codechef.com/viewplaintext/35218886
(* The solution is very basic and doesn’t even require an explanation. *)

Yes this problem can be solved with Bit Manipulation, but can someone suggest why the above solution gives TLE!!!.
I mean it is O(N), I submitted yet another solution which was based on sorting the vector and that was accepted, which was O(NlogN).
HELP!!!

2

Because of collisions in unordered map. Setter has deliberately put some TC to make it O(n) (worst case for unordered map) per query.

3

No, they have an average complexity of O(1) i.e. assuming random input. Their worst case complexity is O(N) for some important operations.

Oh? :slight_smile:

To expand on @sebastian’s answer, I think the following creates a valid testcase:

#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>
#include <cassert>
using namespace std;

const int N = 2e5;

int main() {
    // On my system, an unordered_map will eventually grow to have p buckets.
    const auto p = 26267;
    const auto maxCoordVal = 1'000'000'000;
    const auto maxCoordMultiplier = maxCoordVal / p;

    struct Vertex
    {
        int x = -1;
        int y = -1;
        bool operator<(const Vertex& other) const
        {
            if (x != other.x)
                return x < other.x;
            return y < other.y;
        }
    };
    struct Rectangle
    {
        Vertex vertices[4];
    };
    vector<Rectangle> rectangles;
    set<Vertex> vertices;

    // Should generate valid rectangles with distinct vertices, where each vertex coord in a multiple of
    // p, and does not exceed maxCoordVal.
    // Since all coordinates are multiples of p, when the unordered_map grows to have p buckets, 
    // the coordinates will all end up in the same bucket.
    for (int i = 0 ; i < maxCoordMultiplier / 2; i += 2)
    {
        for (int j = 0; j < maxCoordMultiplier / 2; j += 2)
        {
            // Should be a non-degenerate rectangle.
            const Vertex topLeft = {(i * 2) * p, (j * 2) * p};
            const Vertex topRight = {(i * 2 + 1) * p, (j * 2) * p};
            const Vertex bottomLeft = {(i * 2) * p, (j * 2 + 1) * p};
            const Vertex bottomRight = {(i * 2 + 1) * p, (j * 2 + 1) * p};

            Rectangle rectangle { topLeft, topRight, bottomLeft, bottomRight };
            rectangles.push_back(rectangle);

        }
        if (rectangles.size() > 2e5)
            break;
    }

    while (rectangles.size() > 2e5)
        rectangles.pop_back();

    const int numRectangles = rectangles.size();
    // Verify coords are unique.
    for (const auto& rectangle : rectangles)
    {
        for (const auto& vertex : rectangle.vertices)
        {
            assert(vertices.find(vertex) == vertices.end());
            vertices.insert(vertex);
        }
    }
    // Mark one random vertex as not-to-be-printed.
    auto& vertexToOmit = rectangles[rand() % rectangles.size()].vertices[rand() % 4];
    cerr << "Will omit the vertex: " << vertexToOmit.x << " " << vertexToOmit.y << endl;
    vertexToOmit.x = -1;
    vertexToOmit.y = -1;

    cout << 1 << endl;
    cout << numRectangles << endl;
    for (const auto& rectangle : rectangles)
    {
        for (const auto& vertex : rectangle.vertices)
        {
            if (vertex.x == -1 && vertex.y == -1)
                continue;
            cout << vertex.x << " " << vertex.y << endl;
        }
    }
}

(The setter’s solution handles the generated testcase in about .25 secs on my machine; yours … doesn’t ;))

4 Likes