USACO 2014 Gold US Open Fair Photography: How to Achieve Suggested Complexity in Editorial

Revision en2, by vamaddur, 2017-12-25 09:08:57

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!

Tags hash, usaco

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vamaddur 2017-12-25 09:08:57 2 Tiny change: 'pid=436)\n[Editori' -> 'pid=436)\n\n[Editori'
en1 English vamaddur 2017-12-25 09:08:46 1030 Initial revision (published)