Блог пользователя Filikec

Автор Filikec, история, 19 часов назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
17 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
16 часов назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

[redacted because i was wrong]

»
15 часов назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    14 часов назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 часов назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 часов назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
10 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.