The 3SUM problem is defined as follows. Given an array A[1...n] of numbers, determine whether there exist $i,j,k\in \{1,\cdots, n\}$ so that $A[i] + A[j]+A[k] = 0$.
The 3ARR-ARITH problem is defined as follows. Given three arrays $A[1..n], B[1..n], C[1...n]$ of numbers, determine whether there exist $i,j,k \in \{1,\cdots, n\}$ so that $B[j] - A[i] = C[k] - B[j].$
When reducing from problem P1 to problem P2, you assume you have a subroutine that solves problem P2 and use this subroutine to solve P1.
Determine a linear time reduction from 3SUM to 3ARR-ARTIH.
Determine a linear time reduction from 3ARR-ARITH to 3SUM.
I know a linear time reduction from 3ARR-SUM to 3SUM, where 3ARR-SUM is defined as follows: Given three arrays $A[1...n], B[1...n], C[1...n]$ of numbers, determine whether there exist $i,j,k$ so that $A[i]+B[j]+C[k] = 0$.
The reduction can be described by the following algorithm, where 3SUM is a subroutine that solves the 3SUM problem:
3ARR-SUM(A[1...n], B[1...n], C[1...n]):
for i = 1 to n do
X[i] = 10 * A[i] + 2
Y[i] = 10 * B[i] + 4
Z[i] = 10 * C[i] - 6
let A' be an array of 3n 0's
for i = 1 to 3n do
if (i <= n)
A'[i] = X[i]
else if (i <= 2n)
A'[i] = Y[i]
else
A'[i] = Z[i]
if 3SUM(A'[1...3n]) returns (i,j,k) then
sort (i,j,k) so that i <= j <= k
return (i, j - n, k - 2n)
I tried rearranging the expressions for 3SUM and 3ARR-ARITH, but it doesn't seem like that helps. I can't think of something similar to the above either. How would I obtain a single array that 3SUM can solve and for which calling 3SUM on the array will solve 3ARR-ARITH?
Also, I can't seem to figure out how to reduce 3SUM to 3ARR-ARITH. It doesn't seem like defining the arrays A,B,C as follows works: $A[i] = 10A'[i] + 1, B[j] = 10B'[j] + 2, C[k] = 10C'[k] + 3$. I have a single array $A'[1..n]$ and I want to obtain 3 arrays $A[1...n], B[1...n], C[1...n]$ so that if I call 3ARR-ARITH on these 3 arrays, I will get indices $i,j,k$ so that $B[j] - A[i] = C[k] - B[j] $ and $A'[i] + A'[j] + A'[k] = 0.$
