dumbguy's blog

By dumbguy, history, 3 years ago, In English

Hello guys,
I am facing difficulties solving DP problems. It's like i am not able to do even the easy ones.
I know some classical problems and have even solved other problems on DP but i am not improving i guess.
I don't get to the correct DP states even after thinking for a while.
Any advice would be appreciated. Thanks.

Read more »

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

By dumbguy, history, 3 years ago, In English

Hello guys,
Since a long time i was under the impression that STL unordered_map is faster due to its non ordering than STL map.
But in a problem when i submitted the solution using unordered_map i got TLE but with map i got AC.
Can anyone please provide an insight into this because i am not able to understand why this happened for this particular solution.

For reference, this is the solution using unordered_map : 33578534 and this one using map : 33578782.
This is the actual problem 776C - Molly's Chemicals
.

Read more »

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

By dumbguy, history, 4 years ago, In English

Suppose i only need to get the minimum element at every instance (there is constant addition and removal of items).
Which would be optimum in terms of time complexity? stl set or min_heap (implemented as priority_queue)
I know min_heap gets the minimum element in O(1). But what about stl set? Is it O(1) or more than O(1).
Thanks

Read more »

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