_14_'s blog

Why TLE?
By _14_, history, 3 months ago, In English

In the last educational round, my below solution for the problem 2004D - Colored Portals got TLE.

TLE solution: 276676175

After the contest, I submitted the solution with only one line of change in code and it got AC.

AC solution: 276725505

The only difference between both the codes is:

In the TLE solution:

for (auto x : mp)

And in the AC solution:

for (auto x = mp.begin(); x != mp.end(); x++)

Anyone, please help me to find out the time complexity of each statement. And why this first one gives TLE?

Which statement should be preferred to avoid this type of situation?

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

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

Doing for(auto x : mp) makes you copy the whole map when processing it, thus increasing the complexity per query to $$$O(n)$$$ instead of $$$O(log(n))$$$. A solution would be using for(auto &x : mp).

→ Reply