vMortex's blog

Binary search in Integers have friends pblm.
By vMortex, history, 3 years ago, In English

One of the tags for Integers have friends problem is binary search but I am not able to figure out how to apply binary search without using segment tree and sparse table.(since i'm a beginner i actually don't know segment tree and sparse table). I want to do it using only binary search if it's possible. My approach: For a value X check if it's possible that max size of friend group is less than or equal to X, if i'm able to do this in O(n) then it's solved but i don't know how to do this in O(n). Am i missing something is there any other way to do it using binary search?

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

Comments Comments (11)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The idea is that you need to binary search a range GCD and find the largest possible range from the leftmost position to the rightmost. (essentially the largest friend group) In order to do this in O(NlogN) time, you need a sparse table (O(1) query and O(NlogN) construction) or segment tree (which may even be too slow). I don't think it's possible without a RMQ/Sparse Table

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

I think this solution does not make use of segment tree, sparse table https://codeforces.com/contest/1549/submission/124572982

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

there is a way to do it without binary search or DS entirely, which is just to maintain the points where the GCD changes as you loop right endpoints from $$$1$$$ to $$$n$$$. The GCD can only change $$$\approx \log{N}$$$ times so you can do this with a vector or something, then just pick the leftmost endpoint that isn't $$$1$$$.

I didn't remember the code entirely during contest so I just used sparse table template code for my solution.

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

    should i calculate a running gcd? could you explain a bit more. I think this uses exactly what you said https://codeforces.com/contest/1549/submission/124572982 but i'm not sure about the time complexity.

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

      It looks like you are keeping every GCD in the map (even ones that are no longer 'relevant').

      Maybe it is hackable.

      UPD: NVM, I did not see the assignment of the new map, I think your solution is fine, but is $$$log^2$$$ instead of $$$log$$$ because of the map.

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

The idea is to fix the left pointer and then binary search the right pointer with log n steps, using either a segment tree (log n) or a sparse table (nearly constant time), a fenwick tree (much harder to do and I don't recommend), a treap, or whatever. At the end of the day, the complexity will be nearly the same. Then the answer will be the length of this subarray.

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

    Afaik fenwick trees can only be used for prefix-based operations. I think you won't be able to use a fenwick tree to find range-GCD.

    → Reply