udoy07's blog

for using hashing vector is better than map while accessing the hashing data in a nested loop?
By udoy07, history, 12 months ago, In English

problem link:https://codeforces.net/contest/1352/problem/E

sol link with vctor :https://codeforces.net/contest/1352/submission/214450956

sol link with map :https://codeforces.net/contest/1352/submission/214450292

your valuable opinion will surely help others who's are like me. and if does not make any sense than please comment section is available, i will delete it.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

While using vector your time complexity is approximately : O((n^2).1) = O(n^2) , and in case of map it is: O((n^2).log(n)) (since accessing time in map is O(log(n))) . N is given max 8000, so for vector TC: 6.4 X 1e7 and in case of map its 8.3 X 1e8, so solution using the map is bound to give TLE here.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    exactly, being a newbie i didnt think for a sec, then i realize how it leads me to tle, for further solving any problem i will keep it in my mind, thanks for the calculated explanation.

    → Reply