Complexity of erase and insert function of vector?

general
,
1

I was solving this problem. Its a clear cut implicit treap problem but I saw many people commented just STL was needed. So I googled a bit and found this solution. But isn’t erase and insert function at worst case O(N)? Here also it is given it’s O(N). And I even doubt testcases to be weak as setter is Morass. Is there something I am missing or are the testcases really weak? Also according to hodobox’s comment there is some nifty trick that can solve it without using complicated structures which i assume is treaps. Does anyone know any other relatively easier method to solve it? Thanx.

1 Like
2

I’m not completely sure, but I think that this problem could be solved with Square Root Decomposition approach (\sqrt{M} double linked lists or vectors). My implicit key treap solution ACed in 8 secs (and I use language with range checks, garbage collector and with all compiler optimizations flags disabled on SPOJ).

1 Like
3

@avm_ can you please look into the code and tell me where i can optimize it? I’ve used your idea of sqrt decomposition. I’ve tried a lot (tried to change the size of blocks) but keep on getting TLE on test 15.

my code : http://rextester.com/NQIKZH15207

4

you sure about sqrt dec? Spoj has strict T.Ls. And generally sqrt dec solutions do not pass unless intended itself is sqrt dec. Btw any idea why that code got AC? Insert and Erase are O(N) per query. Maybe some compiler reasons like using vectors is makes a code vv fast as compared to complicated structures? Also any reason for that?

5

@pk301, at least you prove that both my guesses weren’t wright:

  1. sqrt decomp is easier to write (impicit heap code 170 lines of code with debug vs 250 of yours)
  2. sqrt decomp could pass the tests
    @soham1234, actually memory access has more cost than CPU evaluations, so I don’t think that compiler optimizations can make code very fast.
    https://stackoverflow.com/questions/25218880/why-is-stdvectorinsert-complexity-linear-instead-of-being-constant
6

@avm_ yes, at first look I thought it is much simpler but when I code it I feel how difficult this is. Btw can you give me a better implementation of sqrt implementation (I mean short code)?