Muhammad_mhs's blog

Need help , Please! [ CF Round #736(Div. 2) — D ]
By Muhammad_mhs, history, 3 years ago, In English

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.

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

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

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.

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

    Total time complexity is $$$O(nlognlog(max {{a_i}} ))$$$ for initializing the Spharse Table, and $$$O(nlog(max {{a_i}} ))$$$ for getting the answer.

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

      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)$$$.

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

    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.

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

    Can you explain the O(NlogN) method? I think the gcd operator will add an additional logN into the total time complexity.

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

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.

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

    Thanks a lot, dear.

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

    Thanks for the explanation.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

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

      It's a very nice observation.

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

      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.

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

      Can you please elaborate on the GCD complexity?

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

Can anyone tell how to get rid of Memory Limit Exceeded. I have implemented a segment tree with two pointer approach.

My Submission:124646523

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

    Your query function return int type data. but range gcd can be cross int limit.

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

      Actually in my code i have defined int as long long, although it is not a good practice.

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

    And also there is a corner case that is n = 1. You have to fix this case.

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

      Could you share your segment tree accepted solution, it will help a lot.

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

        your code doesn't work for n = 1.

        My Solution: 124641397

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

          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.

          → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The same code passes in 1950ms if you choose language GNU C++17 (64 bit)

Link

→ Reply