WaifuSlayer's blog

By WaifuSlayer, history, 3 months ago, In English

I solved this problem using both sorting and a set; but the sorting solution passes but the set solution TLEs. I'm curious if this is by design since the problem is marked under "sorting" or if hashing is just that much slower in this case.

problem: https://cses.fi/problemset/task/1621/

my code: https://cses.fi/paste/e9ace6fc0fc91742778f0f/

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

https://cses.fi/paste/6b9842c9b46ce28d778f8d/

add elements to the set and print size of a set, since you can't have duplicates in the set. (I don't know python so code is probably bad, but it works)

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

I would assume your solution using set only failed on test 13, which is an anti-hash-test designed specifically to make python's set TLE. You can read more about it here (general info about anti-hash-table hacks and details related to c++) and here (details related to python).