tacocat's blog

By tacocat, history, 4 months ago, In English

Link to the problem: https://mirror.codeforces.com/contest/741/problem/D

I came up with a solution using Small To Large and Xor Hashing, but my time complexity is O(nlog2(n)26), which is still not optimized enough. It got the extra log from using map, and I'm not sure of how to get rid of the map. Can someone help me pls?

My Code (I switched to unordered_map and it still TLEs)

EDIT: Got rid of the map, not sure how to explain it tho. And the solution above would've WAed test 32 because i forgot to make the default value of the map to be -INF

Accepted solution: https://mirror.codeforces.com/contest/741/submission/287930415

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

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

Have you tried gp_hash_table?

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

nice handle

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

Just use sack with an array, avoid using map or unordered_map for problem with large constants.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tacocat (previous revision, new revision, compare).

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

what's ur handle bro