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

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 (https://www.codechef.com/problems/PTMSSNG)
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!!!

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

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