vamaddur's blog

By vamaddur, history, 7 years ago, In English

Problem Link

Editorial Link

"An alternative is to consider all O(2^B) valid values for A in an outer loop. If one indexes not by the full signature but by a 64-bit hash of it, then the runtime becomes O(2^BN), but in the unlikely event of two different signatures hashing to the same 64-bit value, the answer may be incorrect or must be verified. Many who wrote exponential solutions in B received time outs; on occasion a low constraint is a red herring and hides an easily implemented more efficient solution."

I tried this approach in my solution here, but I get TLE with a complexity that has an added factor of B * log N (due to the map and hash computation). How can I prune my current solution down to the intended complexity?

Please help, and thanks in advance!

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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Get rid of the added factor of B log N