An intresting debugging incidence in a beginner's(my) CF journey — Hashmap Blowup

Revision en1, by do4z, 2023-01-27 14:58:36

I was solving Train and Queries and my submission 190745271 got TLE in test case 19(I know space complexity is bad but it's beacuse i wanted to solve it with priority queue only). I was calculating time complexity of my code again and again but it was all ok in code according to me because i was considering time complexity of operations of hashmap O(1) ( which is true for most of the cases) . Then i watched tutorial and seen the same core approach as mine,but i didn't copy that solution because i wanted to know what was wrong in my code. Then i noticed 18th test case(previous one of the failed test case) and that test case passed by using same size of array and number of queries that of failed test case. Then i came to know that TLE is not because of size of array and number of queries,instead it's due to elements of the array and then had intuition that there is something wrong with hashmap and i searched for it and then i found a valuable blog of neal (Blowing up Unordered_map) . Really it was so intresting and filled with deep topics. Then i came to know that 19th test case was blowing up my hashmap and i changed hashmap to tree map in submission 190747739 . Bingo ! it passed all test cases. More than solving a problem i learnt such an intresting topic today . A special thanks to neal .

Tags hashmap, debugging, debug, learning, treemap, unordered_map, map, coding

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English do4z 2023-01-27 14:58:36 1647 Initial revision (published)