Time Complexity 0.5 sec

help
1

What order of time algorithm works for a time limit of 0.5 s?
I am unable to find good reliable documentation for this.

4 Likes
2

It depends on the constraints.

If N <= 10^6, an O(N log N) solution would easily pass.

(Based on the assumption 10^8 operations take 1 second)

2 Likes
3

Not necessarily true. The constant for c++ set / map is pretty big and n=10^6 for O(nlogn) won’t easily pass. (You can think of it like each set operation takes 10logn operations).

11 Likes
4

so only O(N) solution passes for sure,
btw consider complexity for #T .
if T = 10 it’d be 0.05 seconds per test case.

5

I see…

So only an O(N log N) solution with no constants or coefficients would pass.

6

For example, nlogn with n=10^6 seems reasonable for binary search / binary indexed tree, both of which have low constants.

1 Like
7

I am not able to understand this question EXPCH. Can any one explain the example test case ? Is it right to ask clarification of the question when the long challenge is still going on?

8

Yeah, EXPCH does not really explain the test case very much at all; you have to rely on reading the explanation carefully.

Hopefully you know what is meant by a multiplicative modular inverse. Plenty of articles on that here.