6*10^7 operations gets TLE C++ — Contest 402 DIV 2 Problem E

Revision en1, by VLamarca, 2017-03-02 23:36:51


My solution to this problem E implements the same ideia as the editorial. But first I used a O(m*n*lgn) solution here (for m=1000 and n=5000, which is ~6*10^7) that got TLE. I used map in this one which made it slower. Then I tried using map only in the beggining instead of using all the way in the code (as shown here). This means that first I mapped the string to the index that gives the element that the map would represent. Accessing the element this way is O(1), therefore the solution was O(m*n) which got accepted.

But shouldnt the 3 second limit be enough for less the 10^8 operations in the first solution? I though that 1 second meant 10^9 operations.

Sorry for the begginer's doubt. Possibly it's because I used many operations per iteration, but how should I know? what do you consider as the boundary, 10^7 per second?

PS: actually in the first solution the map is deleted and remade in every iteration, which means that its size is not always the maximun n, which is actually faster than what I considered in this post.


  Rev. Lang. By When Δ Comment
en1 English VLamarca 2017-03-02 23:36:51 1319 Initial revision (published)