saar2119's blog

By saar2119, history, 3 years ago, In English,

Today one of my myths was broken.
I used to believe that unordered_map is better in time-complexity than map in C++. But today while I was doing a problem(Molly's Chemicals), I got time-limit exceeded. After a lot of guess-work(because I thought my solution was correct), I tried using a map instead of an unordered_map and as a surprise I got it accepted. Then I realised that though the amortised time-complexity of using an unordered_map is O(1) while that of a map is O(log n), there are cases in which due to a lot of collisions unordered_map can have a big constant multiplier which will increase its actual complexity to greater than that of a map.
(Any corrections are welcomed...)

Can someone enlighten me more by clearing the doubt that where should unordered_map be used and where not?
What are the cases in which a map would perform better than an unordered_map?

Here are the tle and aced solution links if someone wants to verify:
TLE Solution(TLE after 2500 ms)
Accepted Solution(Accepted in 499 ms)

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

By saar2119, history, 3 years ago, In English,

Hey everyone, I am asking this question as I am new to TopCoder and having some issues with knowing the test cases on which my system testing failed. I know how to find the cases in the Applet but in the College I am behind proxy server. That is why it is easier to use Web Arena while I am in the college. Does anyone know how to find test cases where the system testing failed on Web Area?

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By saar2119, history, 4 years ago, In English,

Hello everyone, Actually i recently studied LIS nlog(n) approach and tried SPOJ LIS2. It is running well on sample cases but giving WA at #1(don't know why??). Can someone please point out the mistake.. The link to my solution is http://ideone.com/ya5gsw .

Read more »

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