1
$\begingroup$

This is a made up question not seen somewhere so I am not sure if a good solution exists but here it is anyways.

Given an array $ A $ of $ N $ non-negative integers, find the longest non-decreasing subsequence of this array such that every adjacent pair in the subsequence is co-prime, ie. $ gcd(a_{i}, a_{i + 1}) = 1 \space \forall \space 0 <= i < K - 1 $ where $ K $ is length of subsequence.

Would it be possible to have a solution better than $ O(N^2) $ if each number is in range $0$ to $10^5$?

I was exploring solutions using segment trees but it's very tricky, compared to a different version where adjacent pairs should be strictly non-coprime which would be trivial.

If there is some way to make it more efficient I would like to know.

$\endgroup$
3
  • $\begingroup$ What goes wrong if you try adapting a standard algorithm for longest increasing subsequence? $\endgroup$
    – D.W.
    Commented Jun 16, 2023 at 19:09
  • $\begingroup$ @InuyashaYagami yes, non-negative integers, so $0$ to $10^5$ $\endgroup$ Commented Jun 16, 2023 at 19:53
  • $\begingroup$ @D.W. Usual DP solution is $O(N^2)$ which works easily here, but the optimal $O(n \log n)$ solution is difficult to adapt, one uses Binary Search which can't enforce co-prime condition, other uses Segment tree to find longest sequence ending at a smaller value, that too is difficult to adapt as we need to do range maximum query where index is co-prime to some number, I am not sure if that's doable. $\endgroup$ Commented Jun 16, 2023 at 19:57

1 Answer 1

1
$\begingroup$

I think there is a slightly better algorithm, depending on the relative sizes on the upper bound $B=10^5$ and $N$.

The proposed algorithm proceeds like the usual DP algorithm, scanning the array from left to right, and at each array position $i$ you it computes what is the array position $j < i$ that maximizes the value of $\text{dp}[j]$ subject to $A_j < A_i$ and $\gcd(A_j, A_i) = 1$.

To compute $\text{dp}[i]$ you don't actually need to compute $j$, it suffices to compute $\text{dp}[j]$. So we will find it using binary search. The binary search condition is, is there a $j < i$ such that $i$ can connect to $j$ and $dp[j] \geq k$?

We will actually count the number of such $j$ (and then check if its $0$ or $1$) doing inclusion exclusion. The formula for that number is $$\#\big\{j<i : \gcd(A_j, A_i) = 1, A_j < A_i \text{ and } \text{dp}[j] \geq k \big\} = \sum_{d|A_i} \mu(d) M_d^i(k)$$ Where $M_d^i(k)$ is the number of indices $j<i$ such that $d | A_j$, $A_j < A_i$ and $\text{dp}[j] \geq k$, and $\mu$ is the Mobius function.

If for each index $j$ such that $d | A_j$ we consider the 2d point $(A_j, \text{dp}[j])$ then $M_d^i(k)$ is a query of the form "How many points are there in this (shifted) quadrant of the plane?", which can be solved in $O(\log N \log B)$ using lazy creation 2d segment trees. We need to store a segment tree like this for each possible $d$ (which are the divisors of elements of the array). And each time we compute a new value of the DP, we need to insert a point in all the required datastructures (which correspond to all divisors of the value $A_i$).

If $D$ is a bound on the number of divisors for numbers less than $B$, then the complexity of this solution would be

$$O(N D \log^2 N \log B)$$

Note that $D$ grows slower than any polynomial with respect to $B$. In particular, for $B = 10^5$, $D < 240$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.