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
Thanks in advance.
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
Thanks in advance.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | maroonrk | 133 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
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.
Total time complexity is $$$O(nlognlog(max {{a_i}} ))$$$ for initializing the Spharse Table, and $$$O(nlog(max {{a_i}} ))$$$ for getting the answer.
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)$$$.
Ahh,yes. I forgot that.
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.
Can you explain the O(NlogN) method? I think the gcd operator will add an additional logN into the total time complexity.
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.
Thanks a lot, dear.
Thanks for the explanation.
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.
It's a very nice observation.
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.
Can you please elaborate on the GCD complexity?
This should help.
That was really helpful, thanks :)
Can anyone tell how to get rid of Memory Limit Exceeded. I have implemented a segment tree with two pointer approach.
My Submission:124646523
Your query function return int type data. but range gcd can be cross int limit.
Actually in my code i have defined int as long long, although it is not a good practice.
And also there is a corner case that is n = 1. You have to fix this case.
Could you share your segment tree accepted solution, it will help a lot.
your code doesn't work for n = 1.
My Solution: 124641397
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.
The same code passes in 1950ms if you choose language GNU C++17 (64 bit)
Link
Could you please tell me why it doesn't pass GNU C++17?
You need to optimize the code, my solution with same logic passes 124697813.
I have used two pointers technique and got AC.