Problem-TOTCRT : I need help understanding why there is a TLE on my solution

1

This is my solution- CodeChef: Practical coding for everyone
At the time of solving this I wasn’t sure how hashmaps or maps worked. So I implemented a naive solution of just going input by input. Not sure but I think my solution is of complexity O(NlogN) ( since find() function is logN). And from what I know nlogn shouldnt give tle on 2.10^4(or even 10^5).

2

std::find is O(N).

3

Oh… so the tle is because of that for sure right? And the only way to do this is through a hashmap? I can’t think of any other normal soln. Thanks for the quick reply btw :slight_smile:

4

Dunno :slight_smile: I haven’t looked a the problem in detail, but it looks like your solution would be O(N^2).

Or a std::map - maybe there are other solutions too.

5

Okayy ty for the help anyway : D

1 Like