mihajlovskijr's blog

Question about time complexity of two problems from today's contest
By mihajlovskijr, history, 7 months ago, In English

I spent really a lot of time during the today's contest trying to make my E solution faster, even though it should have O($$${n^2}logn$$$) complexity, which is with n <= 5000 should pass the 3 second limit. The only thing that helped me was changing long long to int, but even so, it's still very slow. Does anyone have any idea why my E solution is so slow (below is the final one)? And a similar question is about D as well, because I can't see any clear reasons why it is so slow:

E: 255741981
D: 255675779

Sorry about how code in E looks like, I don't know why it shifted, because for me it was totally normal when I was sending it.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I think in problem D it was better to use an unordered map.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Unordered map can cause your code to give TLE due to antihashing tests (O(n) instead of O(1)). Yes, it is possible to use unordered_map without worrying about it, but I hadn't the prewritten code needed for it

    → Reply
»
7 months ago, # |
  Vote: I like it +12 Vote: I do not like it

In problem E: You use ordered_set which is slow, you can use Fenwick tree

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I thought that it should be pretty fast. I suppose it has a large constant then? Because the complexity of all operations of ordered_set should be O(logn)

    → Reply
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

E can be solved in O(n^2), checking every k from n to 1 in O(n).

→ Reply
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

D is solvable with zipped/global array with faster: 255734995

E is solvable with difference array in $$$O(n^2)$$$: 255678366

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

    Oh, well, yeah, these are pretty smart optimizations, and I didn't think about them at first. Thank you!

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

Fallen C :(

→ Reply
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Use a Fenwick Tree instead of an ordered set for E. Ordered set has a pretty high constant factor, which (I'm assuming) is why you TLE'd.

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Actually, you do not need neither ordered set nor fenwick tree. Look at this.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Oh this is a nice approach. Definitely cleaner than abusing a Fenwick tree on this problem like I did.

      → Reply
»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

D: Use array size of $$$ 10^{6}$$$ ,to clean array just do for with in $$$O(n+m)$$$

E: simple scanline

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

The code is shifted, because for indentation you use spaces and tabs interchangeably, and length of tabs in you IDE and on Codeforces is not the same. Better set in your IDE "always use spaces for indentation".

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I never used tabs in my IDE, the only thing I've done with this particular code whas editing inside the codeforces send code window.. Maybe this added them

    → Reply