Filikec's blog

How does this code TLE aka Iteration over set/multiset not linear?
By Filikec, history, 9 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

»
6 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
»
6 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

[redacted because i was wrong]

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

    But I'm not sorting the list

    → Reply
    • »
      »
      »
      6 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
»
5 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
  • »
    »
    4 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
»
4 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