By Muhammad_mhs, history, 2 months ago,

My approach to solving this problem was the segment tree with O(n(logn)^2) complexity. but It gives me TLE.

My Submission: 124635301

Please, anyone, help me why this solution gives me TLE

• +3

 » 2 months ago, # |   0 In my opnion $O(nlog^2n)$ is too slow for this problem. And the constant time complexity is naturally bigger for Segment Tree.Why not try using the Spharse Table? And binary searching the solution of each start i is unnecessary. You can simply use a two-pointer method to get the maximum right segment point of each start i.If you insist your method, then I recommend you use a quicker input method, instead of cin.This is my code.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Total time complexity is $O(nlognlog(max {{a_i}} ))$ for initializing the Spharse Table, and $O(nlog(max {{a_i}} ))$ for getting the answer.
•  » » » 2 months ago, # ^ |   0 You need to note that, for both Sparse Table and Segment Tree, the complexity will have additional factor of $log(MAX)$ because combining function is $gcd(x, y)$.
•  » » » » 2 months ago, # ^ |   0 Ahh,yes. I forgot that.
•  » » 2 months ago, # ^ |   0 I have used ios::sync_with_stdio(0);cin.tie(0); for quicker input method. I have got my mistake. Now, I will try that with the sparse table.Thanks a lot.
•  » » 2 months ago, # ^ |   0 Can you explain the O(NlogN) method? I think the gcd operator will add an additional logN into the total time complexity.
 » 2 months ago, # |   0 Since gcd is built into the segment tree, each range query actually has a complexity of O(logn log1e18), which when combined with the binary search, results in a total time complexity of O(n (log n)^2 log1e18). This ends up being too slow. If you still wish to use a segment tree approach, consider changing the binary search to a 2-pointers approach that reduces it to O(n logn log 1e18), which passes under the time limit.
•  » » 2 months ago, # ^ |   +1 Thanks a lot, dear.
•  » » 2 months ago, # ^ |   0 Thanks for the explanation.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 No, you are wrong. GCD is in fact $O(log(min(a, b) / ans))$, thus the answering each query with segtree is $O(log(n) + log(max_A))$ which turns out to be good enough for doing binary search. Here's my in contest submission which passed the system tests. $O(n \cdot log(n) \cdot (log(n) + log(max_A)))$: 124574566.
•  » » » 2 months ago, # ^ |   0 It's a very nice observation.
•  » » » 2 months ago, # ^ |   0 That is a very careful observation. Nevertheless, given the large constant factor of a segment tree, it might be best to avoid using binary search, which fails when not using 64-bit.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Can you please elaborate on the GCD complexity?
•  » » » » 2 months ago, # ^ |   0 This should help.
•  » » » » » 2 months ago, # ^ |   0 That was really helpful, thanks :)
 » 2 months ago, # |   0 Can anyone tell how to get rid of Memory Limit Exceeded. I have implemented a segment tree with two pointer approach.My Submission:124646523
•  » » 2 months ago, # ^ |   0 Your query function return int type data. but range gcd can be cross int limit.
•  » » » 2 months ago, # ^ |   0 Actually in my code i have defined int as long long, although it is not a good practice.
•  » » 2 months ago, # ^ |   0 And also there is a corner case that is n = 1. You have to fix this case.
•  » » » 2 months ago, # ^ |   0 Could you share your segment tree accepted solution, it will help a lot.
•  » » » » 2 months ago, # ^ |   +1 your code doesn't work for n = 1.My Solution: 124641397
•  » » » » » 2 months ago, # ^ |   0 Thanks for the help, it got accepted. The problem was that i was creating new array for every testcase, just fixed it and also the n==1 corner case.
 » 2 months ago, # | ← Rev. 2 →   0 The same code passes in 1950ms if you choose language GNU C++17 (64 bit) Link
•  » » 2 months ago, # ^ |   0 Could you please tell me why it doesn't pass GNU C++17?
•  » » » 2 months ago, # ^ |   0 You need to optimize the code, my solution with same logic passes 124697813.
•  » » » » 2 months ago, # ^ |   0 I have used two pointers technique and got AC.