haiender288's blog

Getting TLE while doing binary search on segment tree
By haiender288, history, 2 years ago, In English

The problem that I'm doing: 1548B - Integers Have Friends

My submission: 167895313

Basically what I'm doing is finding the maximum length of the subarray in the "diff" array, where their GCD is greater than or equal to 2. I made a GCD segment tree and consider for every index i, I will binary search the greatest j where gcd(diff[i..j]) >= 2. The time complexity of this algorithm should be O(n log^2 n), but I got TLE (5 times with the same code). Is there anything that I'm missing? Thanks in advance.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The actually time complexity for gcd(a, b) is O(log(min(a, b)), so the time complexity of your solution should be O(n log n log 1e18)

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

Time complexity of your solution is $$$\mathcal{O}(n \log^2 n \log MAX)$$$ because of gcd. It gets accepted with C++ 20 and pragmas though.

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

    It can be proven that the complexity is O(n log n * (log n + log MAX))

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

Replacing segment tree with RMQ gets AC pretty comfortably. Here's my solution 167921793

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

(edited)

→ Reply