AnestheticCoder's blog

Getting TLE on test 45 using same logic as mentioned in editorial.
By AnestheticCoder, history, 2 years ago, In English

Hello everyone, I was solving problem C of a div 3 contest 1702C - Поезд и запросы and I just used 2 hash maps to stores the first and last occurence of each station, but on test case 45 its saying TLE.

165981690

Then i read the editorial and tried to using just one hashmap but still it says TLE.

165982877

Please Help.

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

Comments Comments (3)
| Write comment?
»
2 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

Only replace unordered_map with map

map: 165985542

unordered map: 165981690

and after adding fast I/O it will work in 576 ms instead of 2043 ms.

Fast I/O code: 165987488

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May be due to slow I/O. Please try to add ios_base::sync_with_stdio(false); cin.tie(nullptr); at the beginning.

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

worst case complexity of searching, insertion, deletion in std::unordered_map is $$$O(n)$$$

- How to save yourself from getting hacked?

After some searching around we run into unordered_map.h. Inside the file $$$...$$$

$$$...$$$ Armed with this knowledge, we can insert lots of multiples of one of these primes to the map in order to get $$$n^2$$$ blow-up

You can read the full thing here.

- Over 350 hacks by beethoven97 on this one problem

You can see many people got hacked in that contest due to this same issue.

→ Reply