Return to Answer

Case I ($\tau(A)<n/3):$ Let $s=\tau(A)$ and $\ell = a_s - a_1$. Recursively compute $I=\mathcal{A}(A[1:s+1],B)$. One observation is that if $i,j\in I$, and $b_j - b_i = \ell$, the index sets can be concatenated to show $i\in \mathcal{A}(A[1:2s],B)$. This is a simple consequence of $A$ being $s$ periodic, and the overlap of $1$ between two solutions makes sure that the offsets are equal. Let $$R[i] = \lvert\{j \in I\colon j>i, b_j - b_i \text{ divisible by } \ell\}\rvert$$ Then, $R[i]$ can be computed based on $R[i']$ that $i'>i$, and the new index set $I'$, is the indices that $R[i]\ge n/s$ (for simplicity, we've assumed that $n$ is divisible by $\ell$). The cost for this step is bounded by $O(m)$.

Overall Complexity At each step of the recursion, we pay $O(m)$. The periodicity $\tau(A)$ can also be computed in $O(n)$, by computing the longest suffix which is also prefix, of $diff(A)$, that is the increment array $A[2:n]-A[1:n-1]$. However, the size of the problem reduces by at least $1/2$ in each recursive step. There will be $\log n$ steps in worst case, which implies the time complexity is bounded by $O(m \log n)$. Adding the sorting costs, and since $m>n$, the overall complexity is bounded by the sorting time $O(m\log m)$

Case I ($\tau(A)<n/3):$ Let $s=\tau(A)$ and $\ell = a_s - a_1$. Recursively compute $I=\mathcal{A}(A[1:s],B)$. One observation is that if $i,j\in I$, corresponding to index sets $J_i, J_j$, and $b_j - b_i = \ell$, the index sets $J_i, J_j$ can be concatenated to show $i\in \mathcal{A}(A[1:2s],B)$. This is a simple consequence of $A$ being $s$ periodic, and $b_j = b_i + \ell$ ensures that the index set $J_j$ starts where $J_i$ ends. Let $$R[i] = \lvert\{j \in I\colon j>i, b_j - b_i \text{ divisible by } \ell\}\rvert$$ Then, $R[i]$ can be computed based on $R[i']$ that $i'>i$, and the new index set $I'$, is the indices that $R[i]\ge n/s$. The cost for this step is bounded by $O(m)$.

Overall Complexity At each step of the recursion, we pay $O(m)$. The periodicity $\tau(A)$ can also be computed in $O(n)$, by computing the longest suffix which is also prefix, of $\mathrm{diff}(A)$, that is the increment array $a_2-a_1, \dots, a_n-a_{n-1}$. However, the size of the problem reduces by at least $1/2$ in each recursive step. There will be $\log n$ steps in worst case, which implies the time complexity is bounded by $O(m \log n)$. Adding the sorting costs, and since $m>n$, the overall complexity is bounded by the sorting time $O(m\log m)$

The recursion, however, depends on how close $A$ is to an arithmetic progression. Formally, let perdiodicity $\tau(A)$ be defined as: $$\tau(A) = \min \{s>0: \exists C\ \forall i\le n-s: a_{i+s}= a_i + C \} $$ In words, this means elements of $A$, are periodic with a minimum cycle $\tau(A)$, up to some offset.

Case I $\tau(A)<n/3$ Let $s=\tau(A)$ and $\ell = a_s - a_1$. Recursively compute $I=\mathcal{A}(A[1:s+1],B)$. One observation is that if $i,j\in I$, and $b_j - b_i = \ell$, the index sets can be concatenated to show $i\in \mathcal{A}(A[1:2s],B)$. This is a simple consequence of $A$ being $s$ periodic, and the overlap of $1$ between two solutions makes sure that the offsets are equal. Let $$R[i] = \lvert\{j \in I\colon j>i, b_j - b_i \text{ divisible by } \ell\}\rvert$$ Then, $R[i]$ can be computed based on $R[i']$ that $i'>i$, and the new index set $I'$, is the indices that $R[i]\ge n/s$ (for simplicity, we've assumed that $n$ is divisible by $\ell$). The cost for this step is bounded by $O(m)$.

Case II $\tau(A)>n/3$: By definition, for $s=n/3$ there should be an index $i$ that $a_{i+1}-a_i \neq a_{i+1+s}-a_{i+s}$. If $i\le n/3$, we will have $i,i+s\le 2n/3$ which certifies that $\tau(A[1:2n/3])>n/3$. Otherwise, $i>n/3$ implies that $\tau(A[n/3:n])>n/3$.

The recursion, however, depends on how close $A$ is to an arithmetic progression. Formally, let periodicity $\tau(A)$ be defined as: $$\tau(A) = \min \{s\in\mathbb{N}^+: a_{i+s+1}-a_{i+s}= a_{i+1} - a_i \text{ for all valid } i, s\} $$ In words, this means elements of $A$, are periodic with a minimum cycle $\tau(A)$, up to some offset.

Case I ($\tau(A)<n/3):$ Let $s=\tau(A)$ and $\ell = a_s - a_1$. Recursively compute $I=\mathcal{A}(A[1:s+1],B)$. One observation is that if $i,j\in I$, and $b_j - b_i = \ell$, the index sets can be concatenated to show $i\in \mathcal{A}(A[1:2s],B)$. This is a simple consequence of $A$ being $s$ periodic, and the overlap of $1$ between two solutions makes sure that the offsets are equal. Let $$R[i] = \lvert\{j \in I\colon j>i, b_j - b_i \text{ divisible by } \ell\}\rvert$$ Then, $R[i]$ can be computed based on $R[i']$ that $i'>i$, and the new index set $I'$, is the indices that $R[i]\ge n/s$ (for simplicity, we've assumed that $n$ is divisible by $\ell$). The cost for this step is bounded by $O(m)$.

Case II ($\tau(A)>n/3$): By definition, for $s=n/3$ there should be an index $i$ that $a_{i+1}-a_i \neq a_{i+1+s}-a_{i+s}$. If $i\le n/3$, we will have $i,i+s\le 2n/3$ which certifies that $\tau(A[1:2n/3])>n/3$. Otherwise, $i>n/3$ implies that $\tau(A[n/3:n])>n/3$.

The recursion, however, depends on how close $A$ is to an arithmetic progression. Formally, let periodicity $\tau(A)$ be defined as: $$\tau(A) = \min \{s: a_{i+1}-a_i = a_{i+1+s}-a_{i+s} \text{ for all valid $i$ }\} $$ In words, this means elements of $A$ are periodic with a minimum cycle $\tau(A)$, up to some offset.

Now we choose one of two algorithms, according to whether $\tau(A)<n/3$ or not.

Case I ($\tau(A)<n/3$): Recursively compute $I=\mathcal{A}(A[1:s],B)$. Construct the new feasible index set $I'$ by selecting all indices $i\in I$ for which $i+s,i+2s,\dots, i+(n/s)\in I$. This holds because of the periodic pattern in $A$. This computation can be done by DP: Let $$R[i] = \lvert\{j\colon i+js\in I\}\rvert$$ Then, $R[i]$ can be computed based on $R[i+s]$ and $I$. $I'$ will correspond to indices for which $R[i]\ge n/s$. The computation of $I'$ will cost $O(m)$ overall.

Case II ($\tau(A)>n/3$): By definition, for $s=n/3$ there should be an index $i$ that $a_{i+1}-a_i \neq a_{i+1+s}-a_{i+s}$. If $i\le n/3$, we will have $i,i+s\le 2n/3$ which certifies that $\tau(A[1:2n/3])>n/3$. Otherwise, $i>n/3$ implies that $\tau(A[n/3:n])>n/3$.

The recursion, however, depends on how close $A$ is to an arithmetic progression. Formally, let perdiodicity $\tau(A)$ be defined as: $$\tau(A) = \min \{s>0: \exists C\ \forall i\le n-s: a_{i+s}= a_i + C \} $$ In words, this means elements of $A$, are periodic with a minimum cycle $\tau(A)$, up to some offset.

Case I $\tau(A)<n/3$ Let $s=\tau(A)$ and $\ell = a_s - a_1$. Recursively compute $I=\mathcal{A}(A[1:s+1],B)$. One observation is that if $i,j\in I$, and $b_j - b_i = \ell$, the index sets can be concatenated to show $i\in \mathcal{A}(A[1:2s],B)$. This is a simple consequence of $A$ being $s$ periodic, and the overlap of $1$ between two solutions makes sure that the offsets are equal. Let $$R[i] = \lvert\{j \in I\colon j>i, b_j - b_i \text{ divisible by } \ell\}\rvert$$ Then, $R[i]$ can be computed based on $R[i']$ that $i'>i$, and the new index set $I'$, is the indices that $R[i]\ge n/s$ (for simplicity, we've assumed that $n$ is divisible by $\ell$). The cost for this step is bounded by $O(m)$.

Case II $\tau(A)>n/3$: By definition, for $s=n/3$ there should be an index $i$ that $a_{i+1}-a_i \neq a_{i+1+s}-a_{i+s}$. If $i\le n/3$, we will have $i,i+s\le 2n/3$ which certifies that $\tau(A[1:2n/3])>n/3$. Otherwise, $i>n/3$ implies that $\tau(A[n/3:n])>n/3$.