Filikec's blog

How does this code TLE aka Iteration over set/multiset not linear?
By Filikec, history, 10 hours ago, In English

I submitted this 311120546 solution to the recent contest Educational Codeforces Round 176 (Rated for Div. 2).

I was pretty sure my solution is N^2, and I didn't see a reason why it should TLE. Right after submitting I was a bit surprised that the solution took like 1.5s but I thought whatever, there's no way it gets TLE.

How come this code takes over 2s? The only explanation I can see is that the iteration over multiset is not linear which is what I thought for quite a long time.

UPD1: The TLE is because of using a list??? When I use a vector instead, it passes in 500ms

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

»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Filikec (previous revision, new revision, compare).

→ Reply
»
7 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

[redacted because i was wrong]

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

    But I'm not sorting the list

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

      I take that back apparently sorting lists is actually $$$O(n\log{n})$$$ time

      → Reply
»
6 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

Why would someone ever use lists in CP when vectors do exist?

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

    To be honest I never found a problem that can be solved with a list and not be solved with the other data structures.

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

      Thats because there are so low amount of problems that can be solved w lists

      → Reply
»
5 hours ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Generally if a problem can be solved in much lesser time complexity then there will be a test — case that pushes the unoptimized codes/approaches to TLE. It was supposed to be done in O(n log n), using either sorting or Max-Heap. N^2 is much more complex. That's why it resulted in TLE.

Also about list vs vector, list uses linked list which has higher access complexity. Vector has O(1) due to indexing.

→ Reply
»
56 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

The main reason for TLE here is not that “iteration over multiset” is itself nonlinear, but that the algorithm has many container operations implemented via structures with logarithmic overhead and poor cacheability. While it takes O(1) per step to search through the elements in a container (e.g., multiset), the insert, delete, and search operations in these structures (based on balanced trees) take O(log n) time. If you search k elements in each pass of the outer loop (and k can be comparable to n), the total complexity increases to about O(n*k*log n) or even O(n²) in the worst case.

→ Reply