sandbag's blog

Sparse table queries making my solution 5x slower?
By sandbag, 4 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

Full text and comments »

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

LC Weekly Contest — Construct String with Minimum Cost, time complexity analysis?
By sandbag, 6 months ago, In English

I recently came across this problem in the LC weekly, and came up with a dp+hashing solution. However, most accepted users, as well as the the intended solution, use a trie and iterates through the string n times. I discarded any N^2 ideas because I thought the constraint of 5e4 would be too large for N^2. Do you believe this is a result of weak testcases or is it actually reasonable to consider N^2 solutions with the constraints given? I always thought the rule of thumb for N^2 was 1e4, and believe these solutions would not survive if there was a hacking phase.

Problem: https://leetcode.com/problems/construct-string-with-minimum-cost/

Edit: As one user pointed out, the input: "aaa..." (length 50k) ["aaa..." (length 25k), "a"] [1,1], results in N^2 complexity in the worst case and would likely TLE most if not all of the trie DP solutions.

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it