In the Contest Codeforces Round #843 (Div. 2) Problem B. Gardener and the Array I got TLE for the Code in Which I used a Vector of size 200007 vector p(200007, 0); and after contest I tried Submitting the same solution using Map in place of vector map<int, int>p; and the solution got accepted, The Time Complexity of Both the codes is O(N). Seriously Vector takes less time than map and I don't know why and how can a Map beat Vector in TC. If anyone know the reason behind this please explain. Thank you for your time.
Both the submissions 1) Using Vector: 188741557 2) Using Map: 188778187
After Seeing Solution of Map getting Accepted I was quite enraged, as in some contests for some problem I got TLE because of using Map instead of Vector and This time I didn't think of Map and it satisfied the TC. Please explain the reason behind this and when should we use map and vector when both data structures can be used.
Edit: Got the reason behind TLE, Due to initialization of vector I got TLE as it takes additional 2e5 for initialization to 0 every time. Cant get over it Emotional Damage ;-;
ok homie quick explanation. so your problem here is when t = 2e5 and each time you iterate 2e5 times to set each value of the vector to 0. But with the map tho, this isn't a problem.
p.s. if it passed the time limit somehow, you would've gotten MLE.
Thank you so much for the explanation. I really forgot about the initialization but vector should beat map. really cant get over it ;-;
And 2e5 should satisfy memory limit isn't it?
vectors access and set values in O(1). that's where they beat a map, which does both in O(logN). But with a map, you don't have to initialize values.
But aren't we clearing the vector every time. Doesn't it get cleared from memory after completion of loop.
yes you are right, I don't think it will create a memory limit problem because the vector is cleared every time.
us moment bro
Thanks for the Explanation. Went to my roommate expecting a explanation, he said get lost! I would have not slept today because of this question !!!
I know that you understand why it is wrong so I just want to add one thing since I have had this same problem before.
One thing that you can do if you still want to use vector instead of map is to declare a global vector that is the same over all testcases. Then what you can do is, for every testcase, store every index of the vector that you have changed. Then after you have finished the testcase, change only the indices which you have changed back to 0. This will definitely satisfy the time constraint.
However, this is a lot of extra code which I think is not worth it considering the relatively small benefit of switching from map to vector. But if you get TLE from map, then you may want to consider this method.
I think so I can feel your pain because same happened with me(actually instead of vector , I was initializing array)
but thankfully somehow I got my mistake during the contest and got accepted
Haha, I got 4 TLE in practice and got frustrated after map got AC in 1. This is new to me!