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

Правка en1, от vamaddur, 2017-12-25 09:08:46

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!

Теги hash, usaco

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский vamaddur 2017-12-25 09:08:57 2 Tiny change: 'pid=436)\n[Editori' -> 'pid=436)\n\n[Editori'
en1 Английский vamaddur 2017-12-25 09:08:46 1030 Initial revision (published)