sandbag's blog

Sparse table queries making my solution 5x slower?
By sandbag, 3 months ago, In English

I'm trying to solve this problem on LeetCode and my solution is going just a little over the time limit. My idea is to place the first two rooks, then determine the third rook as the maximum rook below them such that it is not on either of their columns. With DP, this should be O(N^3). Using a sparse table on a suffix maximum array should work. However, when I add the sparse table queries to the solution, the code seems to slow down by 5x. This seems a little excessive to me since the query should be O(1).

Is this really just the overhead of a constant time array access or is something else going on?

Full code

When my function queries the sparse table, the time taken for a N=500 testcase is 2509 ms.

Function

But when my function doesn't query the sparse table, the time taken for a N=500 testcase is 515 ms.

Function
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

You do around 5 operations each query and the runtime is going up by about 5 times. It makes enough sense to me. Also why sparse table if the limits are up to $$$500$$$, you can just precalculate all ranges in $$$O(n \cdot m^2)$$$

→ Reply